Welcome to the resource topic for 2025/1021
Title:
Black-Box Crypto is Useless for Pseudorandom Codes
Authors: Sanjam Garg, Sam Gunn, Mingyuan Wang
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 using a black-box reduction from 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 an impossibility in the presence of “crypto oracles,” a notion recently introduced—and shown to be capable of implementing all the primitives mentioned above—by Lin, Mook, and Wichs (EUROCRYPT 2025).
ePrint: https://eprint.iacr.org/2025/1021
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .