Cryptographic multilinear maps and their applications
Abstract/Contents
- Abstract
- Cryptographic multilinear maps are a powerful tool that allows one to perform certain arithmetic operations on encoded values without being able to decode them. The study of multilinear maps was initiated by Boneh and Silverberg in 2003, but it was not until 2013, with the breakthrough works of Garg, Gentry, and Halevi and of Coron, Lepoint, and Tibouchi, that we knew of any candidate constructions. In this thesis, we show that multilinear maps can be used to give new constructions of a number of important cryptographic primitives. We begin with program obfuscation, an extremely powerful primitive that allows one to "scramble" the code of an arbitrary program, so that an adversary cannot learn anything about how it works except by running it. Unlike previous approaches, our construction operates directly on straight-line programs, rather than converting them to matrix branching programs. Because of this, our construction requires only poly(d, s) multilinear map operations for a circuit of depth d and size s---as opposed to previous constructions, for which the number of operations is exponential in d. We also use multilinear maps to construct order-revealing encryption (ORE) with best-possible security. ORE enables one to learn which of any pair of ciphertexts is greater, while leaking no other information. Prior to this work, the best known construction relied on general-purpose two-input functional encryption, which is not currently implementable due to the size of the parameters required. In this work, on the other hand, to compare two 16-bit encrypted values we only need a degree-9 multilinear map. We conclude with a discussion of the cryptanalysis of multilinear maps. In 2014, 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. In this thesis, we strengthen the attack of Cheon et al., by showing that CLT can be broken under some circumstances even without low-level encodings of zero. These new attacks, along with the other contributions of this thesis, further underscore the central importance of developing new kinds of multilinear maps.
Description
| Type of resource | text |
|---|---|
| Form | electronic; electronic resource; remote |
| Extent | 1 online resource. |
| Publication date | 2017 |
| Issuance | monographic |
| Language | English |
Creators/Contributors
| Associated with | Zimmerman, Joseph Paul |
|---|---|
| Associated with | Stanford University, Computer Science Department. |
| Primary advisor | Boneh, Dan |
| Thesis advisor | Boneh, Dan |
| Thesis advisor | Valiant, Gregory |
| Thesis advisor | Williams, Ryan (Richard Ryan) |
| Advisor | Valiant, Gregory |
| Advisor | Williams, Ryan (Richard Ryan) |
Subjects
| Genre | Theses |
|---|
Bibliographic information
| Statement of responsibility | Joseph Paul Zimmerman. |
|---|---|
| Note | Submitted to the Department of Computer Science. |
| Thesis | Thesis (Ph.D.)--Stanford University, 2017. |
| Location | electronic resource |
Access conditions
- Copyright
- © 2017 by Joseph Paul Zimmerman
- License
- This work is licensed under a Creative Commons Attribution 3.0 Unported license (CC BY).
Also listed in
Loading usage metrics...