2021/11/07 by Meghal Gupta, Gupta, Meghal, Yael Tauman Kalai +3
Computer Science · #Coding theory and cryptography #Cryptographic Implementations and Security #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · pdf · doi:10.48550/arxiv.2111.04181
openalex publication_date 2021/11/07 · openalex created_date 2021/11/22 · openalex updated_date 2026/07/28
An error correcting code (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, ECCs have been extensively studied, one of the main goals being to maximize the fraction of errors that the ECC is resilient to. For adversarial erasure errors (over a binary channel) the maximal error resilience of an 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 (iECC) and constructing an 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 iECC to adversarial erasures. In the bit flip setting, we prove an impossibility bound of \frac27.