Paper 2017/997

Hash Proof Systems over Lattices Revisited

Fabrice Benhamouda, Olivier Blazy, Léo Ducas, and Willy Quach


Hash Proof Systems or Smooth Projective Hash Functions (SPHFs) are a form of implicit arguments introduced by Cramer and Shoup at Eurocrypt'02. They have found many applications since then, in particular for authenticated key exchange or honest-verifier zero-knowledge proofs. While they are relatively well understood in group settings, they seem painful to construct directly in the lattice setting. Only one construction of an SPHF over lattices has been proposed in the standard model, by Katz and Vaikuntanathan at Asiacrypt'09. But this construction has an important drawback: it only works for an ad-hoc language of ciphertexts. Concretely, the corresponding decryption procedure needs to be tweaked, now requiring $q$ many trapdoor inversion attempts, where $q$ is the modulus of the underlying Learning With Errors (LWE) problem. Using harmonic analysis, we explain the source of this limitation, and propose a way around it. We show how to construct SPHFs for standard languages of LWE ciphertexts, and explicit our construction over a tag-IND-CCA2 encryption scheme à la Micciancio-Peikert (Eurocrypt'12). We then improve our construction and our analysis in the case where the tag is known in advance or fixed (in the latter case, the scheme is only IND-CPA) with a super-polynomial modulus, to get a stronger type of SPHF, which was never achieved before for any language over lattices. Finally, we conclude with applications of these SPHFs: password-based authenticated key exchange, honest-verifier zero-knowledge proofs, and a relaxed version of witness encryption.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Hash Proof SystemsSPHFLatticesLearning With ErrorsHarmonic Analysis
Contact author(s)
fabrice benhamouda @ normalesup org
2017-10-11: received
Short URL
Creative Commons Attribution


      author = {Fabrice Benhamouda and Olivier Blazy and Léo Ducas and Willy Quach},
      title = {Hash Proof Systems over Lattices Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2017/997},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.