International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 13 November 2014

Dan Boneh, David J. Wu, Joe Zimmerman
ePrint Report ePrint Report
In recent work Cheon, Han, Lee, Ryu, and Stehle presented an attack on the multilinear map of Coron, Lepoint, and Tibouchi (CLT). They show that given many low-level encodings of zero, the CLT multilinear map can be completely broken, recovering the secret factorization of the CLT modulus. The attack is a generalization of the \"zeroizing\" attack of Garg, Gentry, and Halevi.

We first strengthen the attack of Cheon, Han, Lee, Ryu, and Stehle by showing that CLT can be broken even without low-level encodings of zero. This strengthening is sufficient to show that the subgroup elimination assumption does not hold for the CLT multilinear map.

We then present a generic defense against this type of \"zeroizing\" attack. For an arbitrary asymmetric composite-order multilinear map (including CLT), we give a functionality-preserving transformation that ensures that no sequence of map operations will produce valid encodings (below the zero-testing level) whose product is zero. We prove security of our transformation in a generic model of composite-order multilinear maps. Our new transformation rules out \"zeroizing\" leaving no currently known attacks on the decision linear assumption, subgroup elimination assumption, and other related problems for the CLT multilinear map. Of course, in time, it is possible that different attacks on CLT will emerge.

Expand

Additional news items may be found on the IACR news page.