Cryptanalysis of Pseudorandom Error-Correcting Codes

Abstract. We present a cryptanalysis of pseudorandom error-correcting codes, which have been proposed as a building block for code-based cryptographic primitives. Pseudorandom codes aim to combine the error-correcting capability of structured codes with the pseudorandomness of random codes. We demonstrate that several proposed constructions of pseudorandom codes, particularly those based on LDPC (Low-Density Parity-Check) codes, can be distinguished from random codes using polynomial-time attacks. Our attacks exploit structural weaknesses in the code generation process, allowing an adversary to recover the secret code structure or distinguish the pseudorandom code from a truly random one. We provide theoretical analysis and experimental validation of our attacks, highlighting the challenges in designing secure pseudorandom code constructions for cryptographic applications.