Paper 2010/068

Okamoto-Tanaka Revisited: Fully Authenticated Diffie-Hellman with Minimal Overhead

Rosario Gennaro and Hugo Krawczyk and Tal Rabin

Abstract

Okamoto-Tanaka Revisited: Fully Authenticated Diffie-Hellman with Minimal Overhead The Diffie-Hellman protocol (DHP) is one of the most studied protocols in cryptography. Much work has been dedicated to armor the original protocol against active attacks while incurring a minimal performance overhead relative to the basic (unauthenticated) DHP. This line of work has resulted in some remarkable protocols, e.g., MQV, where the protocol's communication cost is identical to that of the basic DHP and the computation overhead is small. Unfortunately, MQV and similar 2-message ``implicitly authenticated" protocols do not achieve full security against active attacks since they cannot provide forward secrecy (PFS), a major security goal of DHP, against active attackers. In this paper we investigate the question of whether one can push the limits of authenticated DHPs even further, namely, to achieve communication complexity as in the original DHP (two messages with a single group element per message), maintain low computational overhead, and yet achieve full PFS against active attackers in a provable way. We answer this question in the affirmative by resorting to an old and elegant key agreement protocol: the Okamoto-Tanaka protocol \cite{okta}. We present a variant of the protocol (denoted mOT) which achieves the above minimal communication, incurs a computational overhead relative to the basic DHP that is practically negligible, and yet achieves full provable key agreement security, including PFS, against active attackers. Moreover, due to the identity-based properties of mOT, even the sending of certificates (typical for authenticated DHPs) can be avoided in the protocol. As additional contributions, we apply our analysis to prove the security of a recent multi-domain extension of the Okamoto-Tanaka protocol by Schridde et al. and show how to adapt mOT to the (non id-based) certificate-based setting.