Cryptology ePrint Archive: Report 2015/023

Multilinear Maps Using Ideal Lattices without Encodings of Zero

Gu Chunsheng

Abstract: Garg, Gentry and Halevi (GGH) described the first candidate multilinear maps using ideal lattices. However, Hu and Jia recently presented an efficient attack for two applications based on the GGH map, multipartite Diffie-Hellman key exchange and an instance of witness encryption using 3-exact cover problem. In this paper, we describe a modification construction of multilinear maps from ideal lattices without encodings of zero by introducing random matrices to avoid the zeroing attack problem. The security of our construction depends upon new hardness assumption, which is seemingly closely related to hardness problems of lattices. Furthermore, we present multipartite Diffie-Hellman key exchange protocol using our construction, and an instance of witness encryption using 3-exact cover problem based on a variant of our construction.

Category / Keywords: Multilinear maps, Ideal lattices, Multipartite Diffie-Hellman key exchange, Witness Encryption, Zeroizing attack

Date: received 11 Jan 2015, last revised 26 May 2015

Contact author: chunsheng_gu at 163 com

Available format(s): PDF | BibTeX Citation

Version: 20150526:073309 (All versions of this report)

Short URL: ia.cr/2015/023

Discussion forum: Show discussion | Start new discussion