Welcome to the resource topic for 2024/1425
Title:
New constructions of pseudorandom codes
Authors: Surendra Ghentiyala, Venkatesan Guruswami
Abstract:Introduced in [CG24], pseudorandom error-correcting codes (PRCs) are a new
cryptographic primitive with applications in watermarking generative AI models.
These are codes where a collection of polynomially many codewords is
computationally indistinguishable from random, except to individuals with the
decoding key. In this work, we examine the assumptions under which PRCs with
robustness to a constant error rate exist.
- We show that if both the planted hyperloop assumption introduced in
[BKR23] and security of a version of Goldreich’s PRG hold, then there exist
public-key PRCs for which no efficient adversary can distinguish a polynomial
number of codewords from random with better than o(1) advantage. - We revisit the construction of [CG24] and show that it can be based on a
wider range of assumptions than presented in [CG24]. To do this, we introduce a
weakened version of the planted XOR assumption which we call the weak planted
XOR assumption and which may be of independent interest. - We initiate the study of PRCs which are secure against space-bounded
adversaries. We show how to construct secret-key PRCs of length O(n) which
are \textit{unconditionally} indistinguishable from random by
\text{poly}(n) time, O(n^{1.5-\varepsilon}) space adversaries.
ePrint: https://eprint.iacr.org/2024/1425
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 .