Article Preview
Top1. Introduction
Cryptographic multilinear maps (Boneh & Silverberg, 2003) have found extensive applications in cryptography, including non-interactive multipartite key exchange protocol (Garg et al., 2013a), witness encryption (Garg et al., 2013b), broadcast encryption (Boneh & Zhandry, 2014), identitiy-based encryption (Garg et al., 2013b), attribute-based encryption (Garg et al., 2013c), indistinguishability obfuscation (Garg et al., 2013d; Zimmerman, 2015), deniable encryption (Sahai & Waters, 2014) and function encryption (Garg et al., 2013d). Boneh & Silverberg (2003) first introduced the notion of multilinear maps, which are an extension of bilinear maps. Until 2013, Garg, Gentry, and Halevi (Garg et al., 2013a) (GGH13) first described a construction of multilinear maps over ideal lattices. Building upon the GGH13 construction, Coron, Lepoint, and Tibouchi (2013) (CLT13) presented an alternate construction of multilinear maps over the integers. Recently, Gentry, Gorbunov and Halevi (2015) (GGH15) provided a new construction of graph-induced multilinear maps from lattices. The security of these constructions relines on new hardness assumptions.
However, current constructions (Garg et al., 2013a; Coron et al., 2013; Gentry et al., 2015) of multilinear maps suffer from the zeroizing attacks (Garg et al., 2013a; Cheon et al., 2015; Hu & Jia, 2015a) introduced by Garg, Gentry, and Halevi (2013). (1) The attack for CLT13. Cheon et al. (2015) completely broke the CLT13 construction using zeroizing attack. To avoid zeroizing attack on CLT13, Garg et al. (2014), and Boneh, Wu & Zimmerman (2014) presented two candidate fixes of multilinear maps over the integers. However, Coron et al. (2015) showed that two candidate fixes of CLT13 can also be defeated using extensions of the Cheon et al.’s Attack (Cheon et al., 2015). By modifying zero-testing parameter, Coron, Lepoint & Tibouchi (2015) (CLT15) proposed a new construction of multilinear map over the integers. Very recently, CLT15 was broken independently by Cheon, Lee & Ryu (2015), and Minaud & Fouque (2015). (2) The attack for GGH13. Hu & Jia (2015a) recently presented an efficient attack on the GGH13 map, which breaks the GGH13-based applications on multipartite key exchange (MPKE) and witness encryption (WE) based on the hardness of 3-exact cover problem. Cheon & Lee (2015) proposed an attack for the GGH13 map by computing a basis of secret ideal lattice. To immune GGH13 against zeroizing attack, Gentry, Halevi & Lepoint (2015) proposed a fix of GGH13 by replacing the linear zero-testing procedure from GGH13 with a quadratic (or higher-degree) zero-testing procedure. However, Brakerski et al. (2015) showed that this new variant of GGH13 failed to thwart zeroizing attack.