Cryptology ePrint Archive: Report 2003/171

Scalable Protocols for Authenticated Group Key Exchange

Jonathan Katz and Moti Yung

Abstract: We consider the fundamental problem of authenticated group key exchange among $n$ parties within a larger and insecure public network. A number of solutions to this problem have been proposed; however, all provably-secure solutions thus far are not scalable and, in particular, require $O(n)$ rounds. Our main contribution is the first {\em scalable} protocol for this problem along with a rigorous proof of security in the standard model under the DDH assumption; our protocol uses a constant number of rounds and requires only $O(1)$ ``full'' modular exponentiations per user. Toward this goal and of independent interest, we first present a scalable compiler that transforms any group key-exchange protocol secure against a passive eavesdropper to an \emph{authenticated} protocol which is secure against an active adversary who controls all communication in the network. This compiler adds only one round and $O(1)$ communication (per user) to the original scheme. We then prove secure --- against a passive adversary --- a variant of the two-round group key-exchange protocol of Burmester and Desmedt. Applying our compiler to this protocol results in a provably-secure three-round protocol for \emph{authenticated} group key exchange which also achieves forward secrecy.

Category / Keywords: cryptographic protocols / Key exchange

Publication Info: This is the full version of the paper appearing at Crypto 2003

Date: received 14 Aug 2003

Contact author: jkatz at cs umd edu

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

Version: 20030815:063027 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]