Abstract
This paper presents three methods for strengthening public key cryptosystems in such a way that they become secure against adaptively chosen ciphertext attacks. In an adaptively chosen ciphertext attack, an attacker can query the deciphering algorithm with any ciphertexts, except for the exact object ciphertext to be cryptanalyzed. The first strengthening method is based on the use of one-way hash functions, the second on the use of universal hash functions and the third on the use of digital signature schemes. Each method is illustrated by an example of a public key cryptosystem based on the intractability of computing discrete logarithms in finite fields. Two other issues, namely applications of the methods to public key cryptosystems based on other intractable problems and enhancement of information authentication capability to the cryptosystems, are also discussed.
Supported in part by the Australian Research Council under the reference numbers A49030136, A49130102 and A49131885.
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
M. Blum, P. Feldman, and S. Micali. Non-interactive zero-knowledge proof systems and applications. In Proceedings of the 20-th Annual ACM Symposium on Theory of Computing, pages 103–112, 1988.
M. Blum and S. Goldwasser. An efficient probabilistic public key encryption scheme which hides all partial information. In G. R. Blakeley and D. Chaum, editors, Advances in Cryptology — Proceedings of Crypto’84, Lecture Notes in Computer Science, Vol. 196, pages 289–299. Springer-Verlag, 1985.
M. Blum and S. Micali. How to generate cryptographically strong sequences of pseudo-random bits. SIAM Journal on Computing, 13(4):850–864, 1984.
J. Carter and M. Wegman. Universal classes of hash functions. Journal of Computer and System Sciences, 18:143–154, 1979.
I. Damgård. Towards practical public key systems secure against chosen ciphertext attacks. In J. Feigenbaum, editor, Advances in Cryptology — Proceedings of Crypto’91. Lecture Notes in Computer Science, Vol.576, pages 445–456. Springer-Verlag, 1992.
D. Dolev, C. Dwork, and M. Naor. Non-malleable cryptography. In Proceedings of the 23-rd Annual ACM Symposium on Theory of Computing, 1991.
W. Diffie and M. Hellman. New directions in cryptography. IEEE Transactions on Information Theory, IT-22(6):472–492, 1976.
T. ElGamal. A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Transactions on Information Theory, IT-31(4):469–472, 1985.
S. Goldwasser and S. Micali. Probabilistic encryption. Journal of Computer and System Sciences, 28(2):270–299, 1984.
S. Goldwasser, S. Micali, and R. Rivest. A digital signature scheme secure against adaptively chosen message attacks. SIAM Journal on Computing, 17(2):281–308, 1988.
N. Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48:203–209, 1987.
N. Koblitz. Hyperelliptic cryptosystems. Journal of Cryptology, 1(3):139–150, 1989.
B. A. LaMacchia and A. M. Odlyzko. Computation of discrete logarithms in prime fields. Designs. Codes and Cryptography, 1:47–62, 1991.
D. L. Long and A. Wigderson. The discrete logarithm hides O(log n) bits. SIAM Journal on Computing, 17(2):363–372, 1988.
S. Micali and C. P. Schnorr. Efficient, perfect polynomial random number generators. Journal of Cryptology, 3(3):157–172, 1991.
M. Naor and M. Yung. Public-key cryptosystems provably secure against chosen ciphertext attacks. In Proceedings of the 22-nd Annual ACM Symposium on Theory of Computing, pages 427–437, 1990.
R. Peralta. Simultaneous security of bits in the discrete log. In Franz Pichler, editor, Advances in Cryptology — Proceedings of EuroCrypt’85, Lecture Notes in Computer Science, Vol. 219, pages 62–72. Springer-Verlag, 1985.
S. C. Pohlig and M. E. Hellman. An improved algorithm for computing logarithms over GF(p) and its cryptographic significance. IEEE Transactions on Information Theory, IT-24(1):106–110, 1978.
M. Rabin. Digitalized signatures as intractable as factorization. Technical Report MIT/LCS/TR-212, MIT, Laboratory for Computer Science, 1979.
R. Rivest. Cryptography. In J. van Leeuwen, editor, Handbook of Theoretical Computer Science, Volume A, Algorithms and Complexity, chapter 13, pages 717–755. The MIT Press, Cambridge, Massachusetts, 1990.
C. Rackoff and D. Simon. Non-interactive zero-knowledge proof of knowledge and chosen-ciphertext attacks. In J. Feigenbaum, editor, Advances in Cryptology — Proceedings of Crypto’91, Lecture Notes in Computer Science, Vol.576, pages 433–444. Springer-Verlag, 1992.
G. J. Simmons. A survey of information authentication. Proceedings of IEEE, 76:603–620, 1988.
D. R. Stinson. Combinatorial techniques for universal hashing. Report Series # 127. Department of Computer Science, University of Nebraska, Lincoln, November 1990. (Also submitted to Journal of Computer and System Sciences).
M. Wegman and J. Carter. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences, 22:265–279, 1981.
Y. Zheng, T. Hardjono, and J. Seberry. A practical non-malleable public key cryptosystem. Technical Report CS91/28, Department of Computer Science, University College, University of New South Wales, 1991.
Y. Zheng and J. Seberry. Immunizing public key cryptosystems against chosen ciphertext attacks. Special Issue on Secure Communications, IEEE Journal on Selected Areas on Communications, 1993. (to appear).
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1993 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Zheng, Y., Seberry, J. (1993). Practical Approaches to Attaining Security against Adaptively Chosen Ciphertext Attacks. In: Brickell, E.F. (eds) Advances in Cryptology — CRYPTO’ 92. CRYPTO 1992. Lecture Notes in Computer Science, vol 740. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-48071-4_20
Download citation
DOI: https://doi.org/10.1007/3-540-48071-4_20
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-57340-1
Online ISBN: 978-3-540-48071-6
eBook Packages: Springer Book Archive