Immunizing Multilinear Maps Against Zeroizing Attacks

Authors: D. Boneh, D. Wu, and J. Zimmerman

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 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 specific type of "zeroizing" attack. In more recent work, Coron, Lepoint, and Tibouchi have further strengthened the original attacks of Cheon et al. With their stregthened attack, the mitigation we describe here is no longer sufficient to secure the original CLT multilinear map.

Cryptology ePrint Archive, Report 2014/930

Full paper: pdf