Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Designs, Codes and Cryptography
Published in: Designs, Codes and Cryptography 3/2017

16-08-2016

Cryptanalysis of multilinear maps from ideal lattices: revisited

Authors: Huiwen Jia, Yupu Hu

Published in: Designs, Codes and Cryptography | Issue 3/2017

Login to get access

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

Multilinear map is a central primitive in cryptography and Garg, Gentry and Halevi proposed the first approximate multilinear maps over ideal lattices (GGH13 map) at EUROCRYPT 2013. Ever since then, multilinear maps has caused the extensive concern and has found too numerous applications to name. Very recently, Hu and Jia put forward an efficient attack on the multipartite key exchange and witness encryption based on GGH13 map. In this paper, we describe another efficient cryptanalysis of GGH13 map, an augmented version of Hu and Jia’s attack on it. More specifically, we improve their attacking tools and propose a “downgrading” method, which enable us to get a low level encoding from a higher level encoding. As a result, we can break the multilinear computational Diffie–Hellman assumption in the GGH13 setting with great ease while Hu and Jia only dealt with the decisional version. Furthermore, by applying our augmented cryptanalysis straightforwardly, we break two schemes from GGH13 map published at CRYPTO 2013: attribute-based encryption for general circuits and identity-based aggregate signatures.
next article Doubly resolvable Steiner quadruple systems and related designs
Appendix
Available only for authorised users
Footnotes
1
As in [8], we write \(\mathbf{X }r\) as a shorthand for \(\sum _ir_ix_i\) as well.
 
Literature
1.
Boneh D., Silverberg A.: Applications of multilinear forms to cryptography. Contemp. Math. 324, 71–90 (2003).
2.
3.
Cheon J.H., Han K., Lee C., et al.: Cryptanalysis of the multilinear map over the integers. In: Oswald E., Fischlin M. (eds.) Proceedings of Advances in Cryptology—EUROCRYPT 2015 Part I, Sofia, Bulgaria, pp. 3–12 (2015).
4.
Cheon J.H., Fouque P.A., Lee C., et al.: Cryptanalysis of the new CLT multilinear map over the integers. In: Proceedings of Advances in Cryptology—EUROCRYPT 2016, Vienna, Austria (2016).
5.
Coron J.S., Lenpoint T., Tibouchi M.: Practical multilinear maps over the integers. In: Canetti R., Garay J.A. (eds.) Proceedings of Advances in Cryptology—CRYPTO 2013 Part I, Santa Barbara, CA, USA, pp. 476–493 (2013).
6.
7.
Coron J.S., Lenpoint T., Tibouchi M.: New multilinear maps over the integers. In: Gennaro R., Robshaw M. (eds.) Proceedings of Advances in Cryptology—CRYPTO 2015 Part I, Santa Barbara, CA, USA, pp. 267–286 (2015).
8.
Garg S., Gentry C., Halevi S.: Candidate multilinear maps from ideal lattices. In: Johansson T., Nguyen P.Q. (eds.) Proceedings of Advances in Cryptology—EUROCRYPT 2013, Athens, Greece, pp. 1–17 (2013).
9.
Garg S., Gentry C., Halevi S., et al.: Candidate indistinguishability obfuscation and functional encryption for all circuits. In: Shmoys D., Reingold O. (eds.) Proceedings of Foundations of Computer Science—FOCS2013, Berkeley, CA, USA, pp. 40–49 (2013).
10.
11.
Garg S., Gentry C., Halevi S., et al.: Attribute-based encryption for circuits from multilinear maps. In: Canetti R., Garay J.A. (eds.) Proceedings of Advances in Cryptology—CRYPTO 2013 Part II, Santa Barbara, CA, USA, pp. 479–499 (2013).
12.
Garg S., Gentry C., Halevi S., et al.: Witness encryption and its applications. In: Boneh D., Roughgarden T. (eds.) Proceedings of 45th ACM Symposium on Theory of Computing—STOC 2013, Palo Alto, California, USA, pp. 467–476 (2013).
13.
14.
Garg S., Gentry C., Halevi S., et al.: Functional encryption without obfuscation. In: Kushilevitz E., Alkin T. (eds.) Proceedings of Theory of Cryptography—TCC 2016 Part II, Tel Aviv, Israel, pp. 480–511 (2016).
15.
Gentry C., Gorbunov S., Halevi S.: Graph-induced multilinear maps from lattices. In: Dodis Y., Nielsen J.B. (eds.) Proceedings of Theory of Cryptography—TCC 2015 Part II, Warsaw, Poland, pp. 498–527 (2015).
16.
17.
18.
Hohenberger S., Sahai A., Waters B.: Full domain hash from (leveled) multilinear maps and identity-based aggregate signatures. In: Canetti R., Garay J.A. (eds.) Proceedings of Advances in Cryptology—CRYPTO 2013 Part I, Santa Barbara, CA, USA, pp. 494–512 (2013).
19.
Hu Y.P., Jia H.W.: Cryptanalysis of GGH map. In: Proceedings of Advances in Cryptology—EUROCRYPT 2016, Vienna, Austria (2016).
20.
Langlois A., Stéhl D., Steinfeld R.: GGHLite: more efficient multilinear maps from ideal lattices. In: Nguyen P.Q., Oswald E. (eds.) Proceedings of Advances in Cryptology—EUROCRYPT 2014, Denmark, Copenhagen, pp. 239–256 (2015).
21.
Metadata
Title
Cryptanalysis of multilinear maps from ideal lattices: revisited
Authors
Huiwen Jia
Yupu Hu
Publication date
16-08-2016
Publisher
Springer US
Published in
Designs, Codes and Cryptography / Issue 3/2017
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI
https://doi.org/10.1007/s10623-016-0266-8

Other articles of this Issue 3/2017

Designs, Codes and Cryptography 3/2017 Go to the issue

OriginalPaper

Quantum MDS codes with relatively large minimum distance from Hermitian self-orthogonal codes

OriginalPaper

Near-complete external difference families

OriginalPaper

Construction of low-hit-zone frequency hopping sequences with optimal partial Hamming correlation by interleaving techniques

OriginalPaper

Galois self-dual constacyclic codes

OriginalPaper

Higher order differentiation over finite fields with applications to generalising the cube attack

OriginalPaper

Doubly resolvable Steiner quadruple systems and related designs

Premium Partner

    Image Credits