Abstract
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.
Chapter PDF
Similar content being viewed by others
Keywords
- Signature Scheme
- Information Rate
- High Error Rate
- Message Authentication Code
- Maximum Distance Separability
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Goldreich, O., Goldwasser, S., Micali, S.: How to construct random functions. J. ACM 33(4), 792–807 (1986)
Goldwasser, S., Micali, S., Rivest, R.L.: A digital signature scheme secure against adaptive chosen-message attacks. SIAM J. Comput. 17(2), 281–308 (1988)
Gopalan, P., Lipton, R.J., Ding, Y.Z.: Error correction against computationally bounded adversaries. Manuscript (October 2004)
Guruswami, V.: List decoding with side information. In: 18th IEEE Annual Conference on Computational Complexity, pp. 300–312 (2003)
Guruswami, V., Håstad, J., Sudan, M., Zuckerman, D.: Combinatorial bounds for list decoding. In: Proceedings of the 38th Annual Allerton Conference on Communication, Control and Computing (2000)
Guruswami, V., Sudan, M.: Improved decoding of reed-solomon and algebraic-geometric codes. In: IEEE Symposium on Foundations of Computer Science, pp. 28–39 (1998)
Guruswami, V., Sudan, M.: List decoding algorithms for certain concatenated codes. In: Proceedings of the thirty-second annual ACM symposium on Theory of computing, pp. 181–190. ACM Press, New York (2000)
Langberg, M.: Private codes or succinct random codes that are (almost) perfect. In: Proceedings of the forty-fifth annual IEEE Symposium on Foundations of Computer Science (2004)
Lipton, R.J.: A new approach to information theory. In: Proceedings of the 11th Annual Symposium on Theoretical Aspects of Computer Science, pp. 699–708. Springer, Heidelberg (1994)
Rompel, J.: One-way functions are necessary and sufficient for secure signatures. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 387–394. ACM Press, New York (1990)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Micali, S., Peikert, C., Sudan, M., Wilson, D.A. (2005). Optimal Error Correction Against Computationally Bounded Noise. In: Kilian, J. (eds) Theory of Cryptography. TCC 2005. Lecture Notes in Computer Science, vol 3378. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-30576-7_1
Download citation
DOI: https://doi.org/10.1007/978-3-540-30576-7_1
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-24573-5
Online ISBN: 978-3-540-30576-7
eBook Packages: Computer ScienceComputer Science (R0)