Paper 2015/162
New Multilinear Maps over the Integers
Jean-Sebastien Coron, 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.
Note: Removed extension to GGH, due to security concern.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in CRYPTO 2015
- Keywords
- Multilinear mapsCheon et alattackCLT scheme
- Contact author(s)
- jean-sebastien coron @ uni lu
- History
- 2015-05-16: revised
- 2015-02-27: received
- See all versions
- Short URL
- https://ia.cr/2015/162
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2015/162,
author = {Jean-Sebastien Coron and Tancrede Lepoint and Mehdi Tibouchi},
title = {New Multilinear Maps over the Integers},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/162},
year = {2015},
url = {https://eprint.iacr.org/2015/162}
}
