Black-Box Crypto is Useless for Pseudorandom Codes
- URL: http://arxiv.org/abs/2506.01854v1
- Date: Mon, 02 Jun 2025 16:41:08 GMT
- Title: Black-Box Crypto is Useless for Pseudorandom Codes
- Authors: Sanjam Garg, Sam Gunn, Mingyuan Wang,
- Abstract summary: A pseudorandom code is a keyed error-correction scheme with the property that any number of encodings appear random to any computationally bounded adversary.<n>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.
- Score: 10.791880225915257
- License: http://creativecommons.org/licenses/by/4.0/
- 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).
Related papers
- Ideal Pseudorandom Codes [8.382679821011134]
Pseudorandom codes are error-correcting codes with the property that no efficient adversary can distinguish encodings from uniformly random strings.
Several constructions of pseudorandom codes have since been proposed, but none of them are robust to error channels that depend on previously seen codewords.
We show that any adaptively robust pseudorandom code for single-bit messages can be used to build a CCA-secure pseudorandom code.
arXiv Detail & Related papers (2024-11-08T20:22:14Z) - (Quantum) Indifferentiability and Pre-Computation [50.06591179629447]
Indifferentiability is a cryptographic paradigm for analyzing the security of ideal objects.
Despite its strength, indifferentiability is not known to offer security against pre-processing attacks.
We propose a strengthening of indifferentiability which is not only composable but also takes arbitrary pre-computation into account.
arXiv Detail & Related papers (2024-10-22T00:41:47Z) - Correcting Subverted Random Oracles [55.4766447972367]
We prove that a simple construction can transform a "subverted" random oracle which disagrees with the original one at a small fraction of inputs into an object that is indifferentiable from a random function.
Our results permit future designers of cryptographic primitives in typical kleptographic settings to use random oracles as a trusted black box.
arXiv Detail & Related papers (2024-04-15T04:01:50Z) - Real-Valued Somewhat-Pseudorandom Unitaries [5.294604210205507]
We show that even though real-valued unitaries cannot be completely pseudorandom, we can still obtain some pseudorandom properties without giving up on a real-valued unitary.
Our analysis shows that an even simpler construction: applying a random (binary) phase followed by a random computational-basis permutation, would suffice.
arXiv Detail & Related papers (2024-03-25T12:37:50Z) - Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
Sponge hashing is a widely used class of cryptographic hash algorithms.<n>Intrepid permutations have so far remained a fundamental open problem.<n>We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
arXiv Detail & Related papers (2024-03-07T18:46:58Z) - Pseudorandom Error-Correcting Codes [0.716879432974126]
We build pseudorandom codes that are robust to cryptographic substitution and deletion errors.
We present an undetectable watermarking scheme for outputs of random substitutions and deletions.
Our second application is to steganography, where a secret message is hidden in innocent-looking content.
arXiv Detail & Related papers (2024-02-14T18:17:45Z) - Revocable Cryptography from Learning with Errors [61.470151825577034]
We build on the no-cloning principle of quantum mechanics and design cryptographic schemes with key-revocation capabilities.
We consider schemes where secret keys are represented as quantum states with the guarantee that, once the secret key is successfully revoked from a user, they no longer have the ability to perform the same functionality as before.
arXiv Detail & Related papers (2023-02-28T18:58:11Z) - A Non-monotonic Self-terminating Language Model [62.93465126911921]
In this paper, we focus on the problem of non-terminating sequences resulting from an incomplete decoding algorithm.
We first define an incomplete probable decoding algorithm which includes greedy search, top-$k$ sampling, and nucleus sampling.
We then propose a non-monotonic self-terminating language model, which relaxes the constraint of monotonically increasing termination probability.
arXiv Detail & Related papers (2022-10-03T00:28:44Z) - Testing randomness of series generated in Bell's experiment [62.997667081978825]
We use a toy fiber optic based setup to generate binary series, and evaluate their level of randomness according to Ville principle.
Series are tested with a battery of standard statistical indicators, Hurst, Kolmogorov complexity, minimum entropy, Takensarity dimension of embedding, and Augmented Dickey Fuller and Kwiatkowski Phillips Schmidt Shin to check station exponent.
The level of randomness of series obtained by applying Toeplitz extractor to rejected series is found to be indistinguishable from the level of non-rejected raw ones.
arXiv Detail & Related papers (2022-08-31T17:39:29Z) - Cryptography from Pseudorandom Quantum States [6.164147034988822]
One-way functions imply the existence of pseudorandom states, but Kretschmer (TQC'20) recently constructed an oracle relative to which there are no one-way functions but pseudorandom states still exist.
We study the intriguing possibility of basing interesting cryptographic tasks on pseudorandom states.
A consequence of (a) is that pseudorandom states are sufficient to construct maliciously secure multiparty protocols in the dishonest majority setting.
arXiv Detail & Related papers (2021-12-18T22:53:16Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.