Cryptology ePrint Archive: Report 2015/162

New Multilinear Maps over the Integers

Jean-Sebastien Coron and Tancrede Lepoint and Mehdi Tibouchi

Abstract: In the last few years, cryptographic multilinear maps have proved their tremendous potential as building blocks for new constructions, in particular the first viable approach to general program obfuscation. After the first candidate construction by Garg, Gentry and Halevi (GGH) based on ideal lattices, a second construction over the integers was described by Coron, Lepoint and Tibouchi (CLT). However the CLT scheme was recently broken by Cheon et al.; the attack works by computing the eigenvalues of a diagonalizable matrix over Q derived from the multilinear map.

In this paper we describe a new candidate multilinear map over the integers. Our construction is based on CLT but with a new arithmetic technique that makes the zero-testing element non-linear in the encoding, which prevents the Cheon et al. attack. Our new construction is relatively practical as its efficiency is comparable to the original CLT scheme. Moreover the subgroup membership and decisional linear assumptions appear to hold in the new setting.

Category / Keywords: public-key cryptography / Multilinear maps, Cheon et al. attack, CLT scheme

Original Publication (with minor differences): IACR-CRYPTO-2015

Date: received 25 Feb 2015, last revised 16 May 2015

Contact author: jean-sebastien coron at uni lu

Available format(s): PDF | BibTeX Citation

Note: Removed extension to GGH, due to security concern.

Version: 20150516:083005 (All versions of this report)

Short URL: ia.cr/2015/162

Discussion forum: Show discussion | Start new discussion