Skip to content
Preprint

Information Loss Is All You Need: $TC^0$ Pseudorandomness from Worst-Case Lattices

Nov 2026 · 0 citations
Computer Science

TL;DR

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.

View source

Similar papers

Preprint Oct 2026

Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions

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...

Ze-Kun Ye · 0 citations
Preprint Oct 2026

Provable Subexponential Algorithms for NIST Third-Round Lattice Families

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...

Yiming Gao, Xu-Yuan Han, Hong-Gang Hu · 0 citations
Preprint Oct 2026

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

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
Book Open access Nov 2026

On linearly derived quantum samples for LWE

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 · 0 citations
Preprint Oct 2026

From Symmetry to Secrecy: Covariant Classical--Quantum Wiretap Channels

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.

Masahito Hayashi, Farzin Salek · 1 citation
Preprint Oct 2026

No Escape from the Quadratic Barrier: Adaptive Attacks on Linear $\ell_2$ Sketches

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.