Paper 2014/483

Disjunctions for Hash Proof Systems: New Constructions and Applications

Michel Abdalla, Fabrice Benhamouda, and David Pointcheval

Abstract

Hash Proof Systems were first introduced by Cramer and Shoup (Eurocrypt'02) as a tool to construct efficient chosen-ciphertext-secure encryption schemes. Since then, they have found many other applications, including password authenticated key exchange, oblivious transfer, and zero-knowledge arguments. One of the aspects that makes hash proof systems 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 existing schemes. In this paper, we show how to construct hash proof systems 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, the first one-round group password-authenticated key exchange without random oracles, the most efficient threshold structure-preserving chosen-ciphertext-secure encryption scheme, and the most efficient one-round password authenticated key exchange in the UC framework.

Note: 2015-10-02: mention of the fact that the core idea of diverse vector space was already present in the paper "Universal Hash Proofs and a Paradigm for Adaptive Chosen Ciphertext Secure Public-Key Encryption" from Cramer and Shoup (http://eprint.iacr.org/2001/085). 2015-03-03: transposition of all matrices to match notation in "An Algebraic Framework for Diffie-Hellman Assumptions" from Escala et al. (http://eprint.iacr.org/2013/377), and various editorial improvements.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in EUROCRYPT 2015
Keywords
Hash Proof SystemNon-Interactive Zero-Knowledge ProofGroup Password Authenticated Key ExchangeThreshold EncryptionLinearly Homomorphic SignatureStructure Preserving Primitive
Contact author(s)
fabrice ben hamouda @ ens fr
History
2015-10-02: last of 3 revisions
2014-06-23: received
See all versions
Short URL
https://ia.cr/2014/483
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/483,
      author = {Michel Abdalla and Fabrice Benhamouda and David Pointcheval},
      title = {Disjunctions for Hash Proof Systems: New Constructions and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2014/483},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/483}},
      url = {https://eprint.iacr.org/2014/483}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.