This paper introduces learning with algebraic rounding (LAR), which applies an explicit integer rounding map to blocks of secret-dependent linear measurements and encodes the result in a lattice quotient, and yields the first post-quantum weak pseudorandom function with joint key-and-input evaluation in $TC^0.
Abstract
Can deterministic information loss yield post-quantum pseudorandomness with $TC^0$ evaluation? We show that deterministic rounding achieves this under quantum worst-case lattice hardness, with fixed polynomial parameters and no predetermined sample bound. We introduce learning with algebraic rounding (LAR), which applies an explicit integer rounding map to blocks of secret-dependent linear measurements and encodes the result in a lattice quotient. For one fixed family with polynomially bounded modulus and dimensions, deterministic labels on exactly uniform, secret-independent public matrices are computationally indistinguishable from independent uniform labels for every polynomial number of classical random examples. Our classical reduction from Gaussian LWE, combined with the quantum worst-case reduction to LWE, bases LAR on GapSVP and SIVP over general lattices at approximation factor $\widetilde{O}(q)$, where $q$ is the modulus. The proof uses source-independent affine transport: public affine maps sampled independently of the hidden errors transport the Gaussian error law close to uniform on the rounding map's zero-label fiber while preserving exactly uniform public matrices. For every fixed inverse-polynomial accuracy, we give a polynomial-time sampler for the same public parameter family. This yields the first post-quantum weak pseudorandom function with joint key-and-input evaluation in $TC^0$, secure against uniform quantum polynomial-time distinguishers given any polynomial number of classical uniform random examples. We also prove hardness of learning polynomial-size two-hidden-layer ReLU networks from noiseless uniform random examples, even for quantum polynomial-time improper learners.
We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This...
We give provable classical subexponential algorithms for secret recovery in growing parameter families associated with NIST third-round lattice candidates. For the Kyber/ML-KEM, FrodoKEM, SABER, NTRU LPRime, and Dilithium/ML-DSA families studied here, polynomial moduli and polylogarithmic coefficient scales yield recov...
In the quantum query model, it is shown that the honest sampler's ideal score acts as a Tsirelson bound for efficient devices and certified randomness and proves an earlier conjecture for Haar-random states and extends it to Fourier sampling.
Keshav Bhateja, Mehdi Esmaili, A. Mantri· 0 citations
It is known that the Learning with Errors (LWE) problem becomes easy using the Field Bernstein-Vazirani (FBV) quantum algorithm with access to quantum samples of the LWE function. We revisit a suggested route to approximate such a state: coherently superposing linear combinations of classical LWE samples and erasing th...
Niklas Pirnay, Jean-Pierre Seifert· Proceedings of the 2026 ACM...· 0 citations
This work constructs finite-block preprocessing schemes whose private information is an entropy difference evaluated at two distributions related by group convolution, and proves nonadditivity at an explicit channel parameter using a two-use encoder, an analytic single-use converse, and certified entropy bounds.
It is shown that the quadratic guarantee is optimal up to logarithmic factors, even with a computationally unbounded responder that knows the matrix, attack algorithm, history, and query distributions and may change its randomized rule after every query.
Edith Cohen, Uri Stemmer· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.