Paper 2018/1129
On Kilian's Randomization of Multilinear Map Encodings
Jean-Sebastien Coron and Hilder V. L. Pereira
Abstract
Indistinguishability obfuscation constructions based on matrix branching programs generally proceed in two steps: first apply Kilian's randomization of the matrix product computation, and then encode the matrices using a multilinear map scheme. In this paper we observe that by applying Kilian's randomization after encoding, the complexity of the best attacks is significantly increased for CLT13 multilinear maps. This implies that much smaller parameters can be used, which improves the efficiency of the constructions by several orders of magnitude. As an application, we describe the first concrete implementation of non-interactive Diffie-Hellman key exchange secure against existing attacks. Key exchange was originally the most straightforward application of multilinear maps; however it was quickly broken for the three known families of multilinear maps (GGH13, CLT13 and GGH15). Here we describe the first implementation of key exchange based on CLT13 that is resistant against the Cheon et al. attack. For N=4 users and a medium level of security, our implementation requires 18 GB of public parameters, and a few minutes for the derivation of a shared key.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- A minor revision of an IACR publication in ASIACRYPT 2019
- Keywords
- Multilinear mapskey-exchangeApproximate-GCD problemGCD attackslattice attacks
- Contact author(s)
- jscoron @ gmail com
- History
- 2021-06-24: last of 4 revisions
- 2018-11-29: received
- See all versions
- Short URL
- https://ia.cr/2018/1129
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2018/1129, author = {Jean-Sebastien Coron and Hilder V. L. Pereira}, title = {On Kilian's Randomization of Multilinear Map Encodings}, howpublished = {Cryptology {ePrint} Archive, Paper 2018/1129}, year = {2018}, url = {https://eprint.iacr.org/2018/1129} }