A Note on the Complexity of Breaking Okamoto-Tanaka ID-Based Key Exchange Scheme

摘要

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 equiv- alent 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.