Metraipolis › archive › dc_b3315469fdf3
Information Loss Is All You Need: $TC^0$ Pseudorandomness from Worst-Case Lattices — arXiv:2611.05136
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.05136
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-04T18:52:41.631Z
- SHA-256 of the archived text
85cfdd2d5d9df56d1dfd9a3363c758dc66157cc4ab4b14bfe32fc88d918479ac- Stable URL of this page
https://metraipolis.com/documento/dc_b3315469fdf3
How to cite
Information Loss Is All You Need: $TC^0$ Pseudorandomness from Worst-Case Lattices — arXiv:2611.05136 — arXiv (en), https://arxiv.org/abs/2611.05136 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_b3315469fdf3 (Metraipolis archive dc_b3315469fdf3, sha256 85cfdd2d5d9df56d1dfd9a3363c758dc66157cc4ab4b14bfe32fc88d918479ac)
BibTeX
@misc{dcb3315469fdf3,
title = {Information Loss Is All You Need: $TC^0$ Pseudorandomness from Worst-Case Lattices — arXiv:2611.05136},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.05136},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_b3315469fdf3; sha256 85cfdd2d5d9df56d1dfd9a3363c758dc66157cc4ab4b14bfe32fc88d918479ac},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.05136. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: fiducia digitale e crittografia (elenco arXiv cs.CR, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC) ; Cryptography and Security (cs.CR).
Pagina del lavoro: https://arxiv.org/abs/2611.05136 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-04T18:35:07.145Z dalla pagina https://arxiv.org/list/cs.CR/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).