2005 | OriginalPaper | Chapter
Optimal Error Correction Against Computationally Bounded Noise
Authors : Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson
Published in: Theory of Cryptography
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
For computationally bounded adversarial models of error, we construct appealingly simple, efficient, cryptographic encoding and unique decoding schemes whose error-correction capability is much greater than classically possible. In particular:
1
For binary alphabets, we construct positive-rate coding schemes which are uniquely decodable from a 1/2 – γ
error rate for any constant γ
>
0.
2
For large alphabets, we construct coding schemes which are uniquely decodable from a
$1 - \sqrt{R}$
error rate for any information rate R
>
0.
Our results are qualitatively stronger than related work: the construction works in the public-key model (requiring no shared secret key or joint local state) and allows the channel to know everything that the receiver knows. In addition, our techniques can potentially be used to construct coding schemes that have information rates approaching the Shannon limit. Finally, our construction is qualitatively optimal: we show that unique decoding under high error rates is
impossible
in several natural relaxations of our model.