Transparent Error Correcting in a Computationally Bounded World

Ofer Grossman; Justin Holmgren; Eylon Yogev

Paper 2020/1411

Transparent Error Correcting in a Computationally Bounded World

Ofer Grossman, Justin Holmgren, and Eylon Yogev

Abstract

We construct uniquely decodable codes against channels which are computationally bounded. Our construction requires only a public-coin (transparent) setup. All prior work for such channels either required a setup with secret keys and states, could not achieve unique decoding, or got worse rates (for a given bound on codeword corruptions). On the other hand, our construction relies on a strong cryptographic hash function with security properties that we only instantiate in the random oracle model.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A minor revision of an IACR publication in TCC 2020
Keywords: error correcting codes list decodable random oracle model
Contact author(s): eylony @ gmail com
History: 2020-11-17: last of 2 revisions; 2020-11-15: received; See all versions
Short URL: https://ia.cr/2020/1411
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1411,
      author = {Ofer Grossman and Justin Holmgren and Eylon Yogev},
      title = {Transparent Error Correcting in a Computationally Bounded World},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1411},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1411}},
      url = {https://eprint.iacr.org/2020/1411}
}