Paper 2014/574

Security Analysis of Multilinear Maps over the Integers

Hyung Tae Lee and Jae Hong Seo

Abstract

At Crypto 2013, Coron, Lepoint, and Tibouchi~(CLT) proposed a practical Graded Encoding Scheme (GES) over the integers, which has very similar cryptographic features to ideal multilinear maps. In fact, the scheme of Coron~{\em et al.} is the second proposal of a secure GES, and has advantages over the first scheme of Garg, Gentry, and Halevi~(GGH). For example, unlike the GGH construction, the subgroup decision assumption holds in the CLT construction. Immediately following the elegant innovations of the GES, numerous GES-based cryptographic applications were proposed. Although these applications rely on the security of the underlying GES, the security of the GES has not been analyzed in detail, aside from the original papers produced by Garg~{\em et~al.} and Coron~{\em et~al.} We present an attack algorithm against the system parameters of the CLT GES. The proposed algorithm's complexity $\tilde\bO(2^{\rho/2})$ is exponentially smaller than $\tilde\bO(2^{\rho})$ of the previous best attack of Coron~{\em et al.}, where $\rho$ is a function of the security parameter. Furthermore, we identify a flaw in the generation of the zero-testing parameter of the CLT GES, which drastically reduces the running time of the proposed algorithm. The experimental results demonstrate the practicality of our attack.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2014
DOI
10.1007/978-3-662-44371-2_13
Keywords
multilinear mapsgraded encoding schemeapproximate common divisorscryptanalysis
Contact author(s)
jhsbhs @ gmail com
History
2014-07-24: received
Short URL
https://ia.cr/2014/574
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/574,
      author = {Hyung Tae Lee and Jae Hong Seo},
      title = {Security Analysis of Multilinear Maps over the Integers},
      howpublished = {Cryptology ePrint Archive, Paper 2014/574},
      year = {2014},
      doi = {10.1007/978-3-662-44371-2_13},
      note = {\url{https://eprint.iacr.org/2014/574}},
      url = {https://eprint.iacr.org/2014/574}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.