Paper 2026/2882

Limits of Pseudorandom Codes under Adaptive Corruption

Ganyuan Cao, Télécom Paris, Institut Polytechnique de Paris
Abstract

Pseudorandom codes (PRCs) hide messages in strings that look uniformly random to anyone without the decoder key. If the key may be stolen after some codewords have been sent, security requires that these codewords and the stolen key be indistinguishable from uniform strings, chosen independently of the messages, together with a key that decodes each of them to its message. Since such a string carries no information about its message, the key must store the link. We ask how many key bits this takes. We first isolate an information-theoretic object, \emph{$q$-use codes}, whose key and $q$ codewords are generated together and whose codewords are perfectly uniform. We show that every adaptively secure PRC yields a $q$-use code with the same key length, namely its opened key together with the uniform strings it opens. Lower bounds on the key length of $q$-use codes therefore apply to every adaptively secure PRC, and they hold unconditionally, since their proofs involve no hardness assumption. We then show that every opening costs key bits beyond the length of the opened message. Without errors, the key needs $\omega(\log\lambda)$ extra bits to decode the codeword itself; under random noise of correlation $\rho$, it needs $\frac{1}{\rho^2}\cdot\omega(\log\lambda)$ extra bits to decode most noisy copies; and if every error pattern up to a constant fraction of the length must be corrected, it needs, for every alphabet, a constant fraction of the codeword, which we call the robustness tax. Hence, as for non-committing encryption, adaptively secure PRCs need an a-priori bound on the number of openings, but each opening costs more. For non-committing encryption, the cost is the message length, whereas for PRCs, soundness and robustness add a cost on top. We give simple stateful codes that meet these bounds, showing that they are essentially tight, and turn them into stateful PRCs with perfect bounded adaptive security. We finally show that, unlike for non-committing encryption, a programmable random oracle cannot pay this cost under noise. Errors move the decoder's queries away from any reprogrammed point, so for decoders with non-adaptive random oracle queries, every opening must still be paid for in key bits or in reprogrammed points that the decoder reads on a noticeable fraction of inputs. The random oracle thus only relocates the cost.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
Pseudorandom CodesAdaptive CorruptionNon-Committing CodesLower BoundsIsoperimetry
Contact author(s)
ganyuan cao @ telecom-paris fr
History
2026-11-16: approved
2026-11-12: received
See all versions
Short URL
https://ia.cr/2026/2882
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2882,
      author = {Ganyuan Cao},
      title = {Limits of Pseudorandom Codes under Adaptive Corruption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2882},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2882}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.