Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions

We study error-detection and error-correction codes for computationally bounded adversarial channels. We consider seeded codes where the polynomial-time encoding and decoding procedures share a public random seed, but are otherwise deterministic. An adversarial channel gets this seed and can perform arbitrary polynomial-time computation to adaptively select both the message to be encoded and a bounded number of errors to be added to the resulting codeword. The goal is to detect or correct such errors with overwhelming probability, while achieving better trade-offs between rate and error tolerance than those possible for computationally unbounded channels. For large alphabets, prior work (ITCS ‘25) achieves essentially optimal parameters under minimal cryptographic assumptions. However, for the binary alphabet, prior works (TCC ‘20, EUROCRYPT ‘25) either only achieved a weaker notion of selective security under the learning with errors (LWE) assumption, or relied on non-standard cryptographic assumptions to get the full notion of adaptive security. In this work, we construct binary codes that achieve the full notion of adaptive security assuming trapdoor hashing, which can in turn be instantiated under a variety of standard cryptographic assumptions such as LWE, or Decisional DiffieHellman (DDH), or Quadratic Residuosity (QR), or Decisional Composite Residuosity (DCR). For error detection, our codes get essentially optimal rate $R \approx 1$ and relative error tolerance $p \approx \frac{1}{2}$. For error correction, they can uniquely correct $p\lt1 / 4$ fraction of errors with a rate R matching that of the best known list-decodable codes for this error tolerance. As a central technical tool of potentially independent interest, we construct multi-input correlation intractable hashing for “shifted output relations” under the standard cryptographic assumptions above.

Authors

• George Lu
• Jad Silbak
• Daniel Wichs

Keywords

• Computer science
• Correlation
• Binary codes
• Encoding
• Error correction codes
• Decoding
• Cryptography
• Standards
• Binary Code
• Error Detection
• Error Tolerance
• Standard Assumptions
• Codeword
• Forward Error Correction
• Notion Of Security
• Linear Function
• Efficient Algorithm
• Proof Of Theorem
• Hash Function
• Generator Matrix
• Formal Proof
• Input Length
• Linear Code
• Experimental Output
• Security Parameter
• Linear Shift
• Explicit Construction
• Message Length
• Collision-resistant
• Decoding Algorithm
• Explicit Code
• Random Oracle Model
• Public Key Infrastructure
• Random Oracle
• Non-negligible Probability
• Output Length
• Sparsity
• Random Code
• Error Correcting Codes
• Correlation Intractability