Cryptology ePrint Archive: Report 2020/1411

Transparent Error Correcting in a Computationally Bounded World

Ofer Grossman and 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.

Category / Keywords: foundations / error correcting codes, list decodable, random oracle model

Original Publication (with minor differences): IACR-TCC-2020

Date: received 12 Nov 2020, last revised 16 Nov 2020

Contact author: eylony at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20201117:002520 (All versions of this report)

Short URL: ia.cr/2020/1411


[ Cryptology ePrint archive ]