Cryptology ePrint Archive: Report 2013/821

Errorless Smooth Projective Hash Function based on LWE

Olivier Blazy and Céline Chevalier and Léo Ducas and Jiaxin Pan

Abstract: Smooth Projective Hash Functions are one of the base tools to build interactive protocols; and this notion has lead to the construction of numerous protocols enjoying strong security notions, such as the security in the Bellare-Pointcheval-Rogaway (BPR) model or even Universal Composability (UC).

Yet, the construction of SPHF has been almost limited to discrete-logarithm or pairing type assumptions up to now. This stands in contrast with domains such as homomorphic encryption or functional encryption, where Lattice Based Cryptography has already caught up and overtook discrete-log/pairing based cryptography. So far, work in the direction of UC based on lattices is almost restricted to a paper from Peikert, Vaikuntanathan, and Waters (Crypto 2008) dealing with Oblivious Transfer in the UC framework, and work in the direction of password-authenticated key exchange protocols (PAKE) to one from Katz and Vaikuntanathan (Asiacrypt 2009) on a 3-round Password-Authenticated Key Exchange, but restraining itself to the BPR model. It seems that dealing with errors in those contexts is not as easy as it is for encryption. In this work, we identify the problem at its source, namely, the lattice version of Diffie-Hellman key exchange protocol: the key greement is only approximate. We explicit a simple folklore trick to obtain true, errorless, one-round key exchange from LWE. We then show that this trick can be adapted to various lattice encryption schemes, leading, with some technicalities, to errorless SPHF's. From there, we derive three new results, namely the first lattice-based following protocols: a one-round PAKE secure in the BPR model, a 3-round PAKE secure in the UC model, and a UC commitment scheme, all of them based on SIS and LWE assumptions.

Category / Keywords: cryptographic protocols / LWE encryption, Lattices, Universal Composability, Password-Authenticated Key-Exchange, UC Commitment, Smooth Projective Hash Functions

Date: received 4 Dec 2013, last revised 2 Jan 2014

Contact author: olivier blazy at rub de

Available format(s): PDF | BibTeX Citation

Version: 20140102:220821 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]