Paper 2009/174

Making the Diffie-Hellman Protocol Identity-Based

Dario Fiore and Rosario Gennaro

Abstract

This paper presents a new identity based key agreement protocol. In id-based cryptography (introduced by Adi Shamir in \cite{shamir-idb}) each party uses its own identity as public key and receives his secret key from a master Key Generation Center, whose public parameters are publicly known. The novelty of our protocol is that it can be implemented over any cyclic group of prime order, where the Diffie-Hellman problem is supposed to be hard. It does not require the computation of expensive bilinear maps, or additional assumptions such as factoring or RSA. The protocol is extremely efficient, requiring only twice the amount of bandwith and computation of the {\em unauthenticated} basic Diffie-Hellman protocol. The design of our protcol was inspired by MQV (the most efficient authenticated Diffie-Hellman based protocol in the public-key model) and indeed its performance is competitive with respect to MQV (especially when one includes the transmission and verification of certificates in the MQV protocol, which are not required in an id-based scheme). Our protocol requires a single round of communication in which each party sends only 2 group elements: a very short message, especially when the protocol is implemented over elliptic curves. We provide a full proof of security in the Canetti-Krawczyk security model for key exchange, including a proof that our protocol satisfies additional security properties such as perfect forward secrecy, and resistance to reflection and key-compromise impersonation attacks.