Interactive error correcting codes over binary erasure channels resilient to > ½ adversarial corruption

DOI10.1145/3519935.3519980MaRDI QIDQ6083516zbMATH OpenOpenAlexWikidataFDO

Authors Yael Tauman Kalai, Rachel Yun Zhang

Publication date 8 December 2023

Published in Proceedings of the 54th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.04181

zbMATH Keywords

binary interactive protocolscoding for interactive communicationerror resilience

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: An error correcting code ($mathsfECC$) 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, $mathsfECC$s have been extensively studied, one of the main goals being to maximize the fraction of errors that the $mathsfECC$ is resilient to. For adversarial erasure errors (over a binary channel) the maximal error resilience of an $mathsfECC$ is $frac12$ of the communicated bits. In this work, we break this $frac12$ barrier by introducing the notion of an interactive error correcting code ($mathsfiECC$) and constructing an $mathsfiECC$ 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 $mathsfiECC$ to adversarial erasures. In the bit flip setting, we prove an impossibility bound of $frac27$.

Recommendations

• The optimal error resilience of interactive communication over binary channels
• scientific article; zbMATH DE number 7650863
• Secure Error-Correction Network Coding in a Randomized Setting
• On the Oblivious Transfer Capacity of Generalized Erasure Channels Against Malicious Adversaries: The Case of Low Erasure Probability
• Toward coding for maximum errors in interactive communication
• Decoding of Convolutional Codes Over the Erasure Channel
• Coding and Cryptography
• scientific article; zbMATH DE number 3478754
• Scrambling adversarial errors using few random bits, optimal information reconciliation, and better private codes
• The Decoding Error Probability of Linear Codes Over the Erasure Channel

This page was built for publication: Interactive error correcting codes over binary erasure channels resilient to > ½ adversarial corruption

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6083516)