CryptoDB
Optimal Bounds on the Existence of Pseudorandom Codes
| Authors: |
|
|---|---|
| Download: | |
| Conference: | TCC 2025 |
| Abstract: | A pseudorandom code is a keyed error-correction scheme with the property that any polynomial number of encodings appear random to any computationally bounded adversary. We show that the pseudorandomness of any code tolerating a constant rate of random errors cannot be based on black-box reductions to almost any generic cryptographic primitive: for instance, anything that can be built from random oracles, generic multilinear groups, and virtual black-box obfuscation. Our result is optimal, as Ghentiyala and Guruswami (2024) observed that pseudorandom codes tolerating any sub-constant rate of random errors exist assuming just one-way functions. The key technical ingredient in our proof is the hypercontractivity theorem for Boolean functions, which we use to prove our impossibility in the random oracle model. It turns out that this easily extends to a separation of pseudorandom codes tolerating a constant rate of random errors from ``crypto oracles,'' a notion introduced and shown to be capable of implementing all the primitives mentioned above by Lin, Mook, and Wichs (EUROCRYPT 2025). |
BibTeX
@inproceedings{tcc-2025-36303,
title={Optimal Bounds on the Existence of Pseudorandom Codes},
publisher={Springer-Verlag},
author={Sam Gunn and Sanjam Garg and Mingyuan Wang},
year=2025
}