MarriageTheoremのこと

_ 週末だというのにePrintが（また）大量に更新されている件。

_ IACR ePrint 2015/175まで確認済み、ECCC 2003年分まで確認済み

_ 気になった論文：New Multilinear Maps over the Integers, Jean-Sebastien Coron and Tancrede Lepoint and Mehdi Tibouchi, http://eprint.iacr.org/2015/162

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.