Abstract
We provide methods for transforming an encryption scheme susceptible to decryption errors into one that is immune to these errors. Immunity to decryption errors is vital when constructing non-malleable and chosen ciphertext secure encryption schemes via current techniques; in addition, it may help defend against certain cryptanalytic techniques, such as the attack of Proos [33] on the NTRU scheme.
When decryption errors are very infrequent, our transformation is extremely simple and efficient, almost free. To deal with significant error probabilities, we apply amplification techniques translated from a related information theoretic setting. These techniques allow us to correct even very weak encryption schemes where in addition to decryption errors, an adversary has substantial probability of breaking the scheme by decrypting random messages (without knowledge of the secret key). In other words, under these weak encryption schemes, the only guaranteed difference between the legitimate recipient and the adversary is in the frequency of decryption errors. All the above transformations work in a standard cryptographic model; specifically, they do not rely on a random oracle. We also consider the random oracle model, where we give a simple transformation from a one-way encryption scheme which is error-prone into one that is immune to errors.
We conclude that error-prone cryptosystems can be used in order to create more secure cryptosystems.
Chapter PDF
Similar content being viewed by others
Keywords
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
Ajtai, M., Dwork, C.: A public-key cryptosystem with worst-case/average-case equivalence. In: Proceedings 29th Annual ACM Symposium on the Theory of Computing, El Paso, TX, pp. 284–293 (1997)
Bellare, M., Boldyreva, A., Palacio, A.: A Separation between the Random-Oracle Model and the Standard Model for a Hybrid Encryption Problem, Cryptology ePrint Archive
Bellare, M., Desai, A., Pointcheval, D., Rogaway, P.: Relations among notions of security for public-key encryption schemes. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 26–45. Springer, Heidelberg (1998)
Bellare, M., Impagliazzo, R., Naor, M.: Does parallel repetition lower the error in computationally sound protocols? In: Proceedings 38th Annual IEEE Symposium on Foundations of Computer Science, Miami Beach, FL, pp. 374–383 (1997)
Bellare, M., Rogaway, P.: Optimal Asymmetric Encryption. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 92–111. Springer, Heidelberg (1995)
Boneh, D.: Simplified OAEP for the RSA and Rabin Functions. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 275–291. Springer, Heidelberg (2001)
Canetti, R., Dwork, C., Naor, M., Ostrovsky, R.: Deniable Encryption. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 90–104. Springer, Heidelberg (1997)
Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology. In: Proceedings 30th Annual ACM Symposium on the Theory of Computing, Dallas, TX, pp. 209–218 (1998)
Cramer, R., Shoup, V.: A practical public key cryptosystem provable secure against adaptive chosen ciphertext attack. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 13–25. Springer, Heidelberg (1998)
Cramer, R., Shoup, V.: Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption. In: Knudsen, L.R. (ed.) EUROCRYPT 2002. LNCS, vol. 2332, pp. 45–64. Springer, Heidelberg (2002)
Dolev, D., Dwork, C., Naor, M.: Non-malleable Cryptography. Siam J. on Computing 30, 391–437 (2000)
Dwork, C., Naor, M.: Zaps and Their Applications. In: Proc. 41st IEEE Symposium on Foundations of Computer Science, pp. 283–293. Full version: ECCC, Report TR02- 001, http://www.eccc.uni-trier.de/eccc/
Dwork, C., Naor, M., Reingold, O., Stockmeyer, L.J.: Magic Functions. In: Proc. IEEE FOCS 1999, pp. 523–534 (1999)
Fujisaki, E., Okamoto, T.: How to Enhance the Security of Public-Key Encryption at Minimum Cost. In: Imai, H., Zheng, Y. (eds.) PKC 1999. LNCS, vol. 1560, pp. 53–68. Springer, Heidelberg (1999)
Fujisaki, E., Okamoto, T., Pointcheval, D., Stern, J.: RSA-OAEP Is Secure under the RSA Assumption. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 260–274. Springer, Heidelberg (2001)
Goldreich, O.: Foundations of Cryptography, Cambridge (2001)
Goldreich, O.: Modern cryptography, probabilistic proofs and pseudorandomness. In: Algorithms and Combinatorics, vol. 17, Springer, Heidelberg (1998)
Goldreich, O., Goldwasser, S., Halevi, S.: Eliminating decryption errors in the Ajtai-Dwork cryptosystem. In: Kaliski Jr., B.S. (ed.) CRYPTO 1997. LNCS, vol. 1294, pp. 105–111. Springer, Heidelberg (1997)
Goldreich, O., Levin, L.: A hard-core predicate for all one-way functions. In: Proc. 21st Ann. ACM Symp. on Theory of Computing, pp. 25–32 (1989)
Goldwasser, S., Micali, S.: Probabilistic Encryption. Journal of Computer and System Sciences 28, 270–299 (1984)
Hoffstein, J., Pipher, J., Silverman, J.H.: NTRU: A Ring-Based Public Key Cryptosystem. In: Buhler, J.P. (ed.) ANTS 1998. LNCS, vol. 1423, pp. 267–288. Springer, Heidelberg (1998)
Hastad, J., Impagliazzo, R., Levin, L.A., Luby, M.: Construction of a pseudorandom generator from any one-way function. SIAM Journal on Computing 28(4), 1364–1396 (1999)
Howgrave-Graham, N., Nguyen, P., Pointcheval, D., Proos, J., Silverman, J.H., Singer, A., Whyte, W.: The Impact of Decryption Failures on the Security of NTRU Encryption. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 226–246. Springer, Heidelberg (2003)
Howgrave-Graham, N., Silverman, J.H., Singer, A., Whyte, W.: NAEP: Provable Security in the Presence of Decryption Failures, Available: http://www.ntru.com/cryptolab/pdf/NAEP.pdf
Impagliazzo, R., Luby, M.: One-way functions are essential to computational based cryptography. In: Proceedings 30th IEEE Symposium on the Foundation of Computer Science, Research Triangle Park, NC, pp. 230–235 (1989)
Lautemann, C.: BPP and the Polynomial-time Hierarchy. Information Processing Letters 17(4), 215–217 (1983)
Lindell, Y.: A Simpler Construction of CCA2-Secure Public-Key Encryption Under General Assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 241–254. Springer, Heidelberg (2003)
Naor, M.: Bit Commitment Using Pseudorandomness. J. of Cryptology 4(2), 151–158 (1991)
Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings 22nd Annual ACM Symposium on the Theory of Computing, Baltimore, MD, pp. 427–437 (1990)
Nguyen, P.Q., Pointcheval, D.: Analysis and Improvements of NTRU Encryption Paddings. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 210–225. Springer, Heidelberg (2002)
Okamoto, T., Pointcheval, D.: REACT: Rapid Enhanced-security Asymmetric Cryptosystem Transform. In: Naccache, D. (ed.) CT-RSA 2001. LNCS, vol. 2020, pp. 159–175. Springer, Heidelberg (2001)
Shoup, V.: OAEP Reconsidered. Journal of Cryptology 15(4), 223–249 (2002)
Proos, J.: Imperfect Decryption and an Attack on the NTRU Ecnryption Scheme, IACR Cryptlogy Archive, Report 02/2003
Sahai, A.: Non-Malleable Non-Interactive Zero Knowledge and Achieving Chosen-Ciphertext Security. In: Proc. 40th IEEE Symposium on Foundations of Computer Science, pp. 543–553 (1999)
Sahai, A., Vadhan, S.: A Complete Promise Problem for Statistical Zero-Knowledge. In: Proceedings of the 38th Annual Symposium on the Foundations of Computer Science, pp. 448–457 (1997); Full version: Electronic Colloquium on Computational Complexity TR00-084
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dwork, C., Naor, M., Reingold, O. (2004). Immunizing Encryption Schemes from Decryption Errors. In: Cachin, C., Camenisch, J.L. (eds) Advances in Cryptology - EUROCRYPT 2004. EUROCRYPT 2004. Lecture Notes in Computer Science, vol 3027. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24676-3_21
Download citation
DOI: https://doi.org/10.1007/978-3-540-24676-3_21
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-21935-4
Online ISBN: 978-3-540-24676-3
eBook Packages: Springer Book Archive