An Improved Multilinear Map and its Applications

An Improved Multilinear Map and its Applications

Chunsheng Gu (School of Computer Engineering, Jiangsu University of Technology, Changzhou, China &State Key Laboratory of Information Security, Institute of Information Engineering, Chinese Academy of Sciences, Beijing, China)
DOI: 10.4018/IJITWE.2015070105
OnDemand PDF Download:
List Price: $37.50
10% Discount:-$3.75


Cryptographic multilinear maps have extensive applications. However, current constructions of multilinear maps suffer from the zeroizing attacks. For a candidate construction of multilinear maps described by Garg, Gentry, and Halevi (GGH13), Hu & Jia recently presented an efficient attack, which broke the GGH13-based applications of multipartite key exchange (MPKE) and witness encryption (WE) based on the hardness of 3-exact cover problem. By introducing random matrix, the author presents an improvement of the GGH13 map, which supports the applications for public tools of encoding in the GGH13 map, such as MPKE and WE. The security of the construction depends upon new hardness assumption. Moreover, the author's improvement destroys the structure of the ring element in the principal ideal lattice problem, and avoids potential attacks using algorithm of solving short principal ideal lattice generator.
Article Preview

1. 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.

Complete Article List

Search this Journal:
Volume 18: 1 Issue (2023): Forthcoming, Available for Pre-Order
Volume 17: 4 Issues (2022): 1 Released, 3 Forthcoming
Volume 16: 4 Issues (2021)
Volume 15: 4 Issues (2020)
Volume 14: 4 Issues (2019)
Volume 13: 4 Issues (2018)
Volume 12: 4 Issues (2017)
Volume 11: 4 Issues (2016)
Volume 10: 4 Issues (2015)
Volume 9: 4 Issues (2014)
Volume 8: 4 Issues (2013)
Volume 7: 4 Issues (2012)
Volume 6: 4 Issues (2011)
Volume 5: 4 Issues (2010)
Volume 4: 4 Issues (2009)
Volume 3: 4 Issues (2008)
Volume 2: 4 Issues (2007)
Volume 1: 4 Issues (2006)
View Complete Journal Contents Listing