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.
Category / Keywords: public-key cryptography / Hash Proof Systems, SPHF, Lattices, Learning With Errors, Harmonic Analysis Date: received 9 Oct 2017 Contact author: fabrice benhamouda at normalesup org Available format(s): PDF | BibTeX Citation Version: 20171011:154136 (All versions of this report) Short URL: ia.cr/2017/997 Discussion forum: Show discussion | Start new discussion