Abstract
The rigorous security of Okamoto-Tanaka identity-based key exchange scheme has been open for a decade. In this paper, we show that (1) breaking the scheme is equivalent to breaking the Diffie-Hellman key exchange scheme over Z n, and (2) impersonation is easier than breaking. The second result is obtained by proving that breaking the RSA public-key cryptosystem reduces to breaking the Diffie-Hellman scheme over Z n with respect to the polynomial-time many-one reducibility.
Preview
Unable to display preview. Download preview PDF.
References
E. Bach, “Discrete logarithms and factoring,” Technical Report UCB/CSD 84/186, University of California, Computer Science Division (EECS) (1984).
K. S. McCurley, “A key distribution system equivalent to factoring,” J. Cryptology, Vol.1, pp.95–105 (1988).
E. Okamoto and K. Tanaka, “Key distribution system based on identification information,” IEEE J. Selected Areas in Communications, Vol.7, pp.481–485 (1989).
P. Ribenboim, “The Book of Prime Number Records,” Springer-Verlag (1988).
Z. Shmuely, “Composite Diffie-Hellman public-key generating systems are hard to break,” Technical Report No.356, Computer Science Department, Technion-Israel Institute of Technology (1985).
A. Shamir, “Identity-based cryptosystems and signature schemes,” Proc.Crypto'84, LNCS 196, Springer-Verlag, pp.47–53 (1985).
K. Sakurai and H. Shizuya, “Relationships among the computational powers of breaking discrete log cryptosystems,” Proc. Eurocrypt'95, LNCS 921, Springer-Verlag, pp.341–355 (1995). (J. Cryptology, Vol.11, pp.29–43 (1998).)
H. Woll, “Reductions among number theoretic problems,” Information and Computation, Vol.72, pp. 167–179 (1987).
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Mambo, M., Shizuya, H. (1998). A note on the complexity of breaking Okamoto-Tanaka ID-based key exchange scheme. In: Imai, H., Zheng, Y. (eds) Public Key Cryptography. PKC 1998. Lecture Notes in Computer Science, vol 1431. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054031
Download citation
DOI: https://doi.org/10.1007/BFb0054031
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64693-8
Online ISBN: 978-3-540-69105-1
eBook Packages: Springer Book Archive