Paper 2014/609

SPOKE: Simple Password-Only Key Exchange in the Standard Model

Michel Abdalla and Fabrice Benhamouda and David Pointcheval

Abstract

In this paper, we propose a simple and efficient password-only authenticated key exchange (PAKE) protocol with a proof of security in the standard model. In its most efficient instantiation, the new protocol has only two flows of communication and a total of 7 group elements and its proof of security is based on the plain DDH assumption. To achieve this goal, we first propose a variant of the Gennaro-Lindell/Katz-Ostrovsky-Yung (GL/KOY) PAKE protocol, in which the encryption schemes used to generate the first- and second-flow messages are only required to be semantically secure against plaintext-checking attacks (INDPCA) and chosen-plaintext attacks (INDCPA), respectively. Unlike semantic security against chosen-ciphertext attacks (INDCCA), an INDPCA adversary is only given access to an oracle which says whether or not a given ciphertext encrypts a given message. Next, we design a more efficient variant of the Cramer-Shoup encryption scheme with shorter ciphertexts together with an associated hash proof system and we prove its INDPCA security under the plain DDH assumption. We believe that the new INDPCA scheme is of independent interest, since it can also replace the Cramer-Shoup encryption scheme in many other PAKE schemes in the standard model, and it yields the most efficient ``algebraic'' INDCCA encryption scheme, under plain DDH, for small messages.

Note: version 2014-08-15: added missing references