2005 | OriginalPaper | Buchkapitel
Optimal Error Correction Against Computationally Bounded Noise
verfasst von : Silvio Micali, Chris Peikert, Madhu Sudan, David A. Wilson
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. 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.