Paper 2021/1481

Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to $>\frac12$ Adversarial Corruption

Meghal Gupta, Yael Tauman Kalai, and Rachel Zhang

Abstract

An error correcting code ($\mathsf{ECC}$) allows a sender to send a message to a receiver such that even if a constant fraction of the communicated bits are corrupted, the receiver can still learn the message correctly. Due to their importance and fundamental nature, $\mathsf{ECC}$s have been extensively studied, one of the main goals being to maximize the fraction of errors that the $\mathsf{ECC}$ is resilient to. For adversarial erasure errors (over a binary channel) the maximal error resilience of an $\mathsf{ECC}$ is $\frac12$ of the communicated bits. In this work, we break this $\frac12$ barrier by introducing the notion of an interactive error correcting code ($\mathsf{iECC}$) and constructing an $\mathsf{iECC}$ that is resilient to adversarial erasure of $\frac35$ of the total communicated bits. We emphasize that the adversary can corrupt both the sending party and the receiving party, and that both parties' rounds contribute to the adversary's budget. We also prove an impossibility (upper) bound of $\frac23$ on the maximal resilience of any binary $\mathsf{iECC}$ to adversarial erasures. In the bit flip setting, we prove an impossibility bound of $\frac27$.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Contact author(s)
meghal @ mit edu
yael @ microsoft com
rachelyz @ mit edu
History
2021-11-08: received
Short URL
https://ia.cr/2021/1481
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1481,
      author = {Meghal Gupta and Yael Tauman Kalai and Rachel Zhang},
      title = {Interactive Error Correcting Codes Over Binary Erasure Channels Resilient to $>\frac12$ Adversarial Corruption},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1481},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1481}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.