Improved Pseudorandom Codes Based on Permutation Puzzles

Researchers including Miranda Christ and Sam Gunn propose an improved pseudorandom error-correcting code (PRC) construction that can be used to add watermarks to AI-generated content with both quality preservation and strong robustness. A PRC is a pseudorandom encryption scheme whose decryption algorithm tolerates a high error rate; pseudorandomness ensures the watermark does not degrade content quality, and error-tolerant decryption corresponds to the watermark's ability to withstand content modifications. Several prior constructions (NeurIPS '24, RANDOM '25, STOC '25) were susceptible to quasi-polynomial-time distinguishing attacks, lacked robustness to edits over constant-size alphabets, and were difficult to make resistant to adversaries who know the detection key. The new construction simultaneously achieves three things: trusted sub-exponential pseudorandom security, robustness to worst-case edits over the binary alphabet, and robustness against computationally unbounded adversaries holding the detection key.