International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Hash Proof Systems over Lattices Revisited

Authors:
Fabrice Benhamouda
Olivier Blazy
Léo Ducas
Willy Quach
Download:
DOI: 10.1007/978-3-319-76581-5_22
Search ePrint
Search Google
Conference: PKC 2018
Abstract: 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.
BibTeX
@inproceedings{pkc-2018-28905,
  title={Hash Proof Systems over Lattices Revisited},
  booktitle={Public-Key Cryptography – PKC 2018},
  series={Public-Key Cryptography – PKC 2018},
  publisher={Springer},
  volume={10770},
  pages={644-674},
  doi={10.1007/978-3-319-76581-5_22},
  author={Fabrice Benhamouda and Olivier Blazy and Léo Ducas and Willy Quach},
  year=2018
}