Paper 2014/483

Disjunctions for Hash Proof Systems: New Constructions and Applications

Michel Abdalla and Fabrice Benhamouda and David Pointcheval

Abstract

Smooth Projective Hash Functions (SPHFs), also known as Hash Proof Systems, were first introduced by Cramer and Shoup (Eurocrypt'02) as a tool to construct efficient INDCCA secure encryption schemes. Since then, SPHFs have been used in various applications, including password authenticated key exchange, oblivious transfer, and zero-knowledge arguments. What makes SPHFs so interesting and powerful is that they can be seen as implicit proofs of membership for certain languages. As a result, by extending the family of languages that they can handle, one often obtains new applications or new ways to understand existent schemes. In this paper, we show how to construct SPHFs for the disjunction of languages defined generically over cyclic, bilinear, and multilinear groups. Among other applications, this enables us to construct the most efficient one-time simulation-sound (quasi-adaptive) non-interactive zero-knowledge arguments for linear languages over cyclic groups, and the first one-round group password-authenticated key exchange without random oracles.