Paper 2006/214

Password-Authenticated Group Key Establishment from Smooth Projective Hash Functions

Jens-Matthias Bohli, Maria Isabel Gonzalez Vasco, and Rainer Steinwandt

Abstract

Password-authenticated key exchange (PAKE) protocols allow users sharing a password to agree upon a high entropy secret. In this paper, a provably secure password-authenticated pro- tocol for group key establishment in the common reference string (CRS) model is presented. Our protocol is quite efficient, as regardless of the number of involved participants it can be imple- mented with only three communication rounds. We use a (by now classical) trick of Burmester and Desmedt for deriving group key exchange protocols using a two-party construction as main building block. In our case, the two party PAKE used as a base is a one-round protocol by Katz and Vaikuntanatan, which in turn builds upon a special kind of smooth projective hash functions (KV-SPHFs). As evidenced by Benhamouda et al., KV-SPHFs can be instantiated on Cramer-Shoup ciphertexts, thus yielding very efficient (and pairing free) constructions.

Note: There are significant changes from the 2009 version, the most relevant being that now the underlying 2party protocol is the one proposed by Katz and Vaikuntanathan at TCC11. Not only do they deal with projections depending only on K -- as we did -- but further allow for projections to be chosen adaptively once the message x is known. (i.e., given x \alpha(k) might be constructed from x and yet H_k(x) will still look indistinguishable from random without a witness).