Welcome to the resource topic for 2025/1877
Title:
Binary Codes for Computationally Bounded Errors Under Standard Crypto Assumptions
Authors: George Lu, Jad Silbak, Daniel Wichs
Abstract: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 Diffie-Hellman (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 < 1/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.
ePrint: https://eprint.iacr.org/2025/1877
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 .