Paper 2016/599

Obfuscation from Low Noise Multilinear Maps

Nico Döttling, Sanjam Garg, Divya Gupta, Peihan Miao, and Pratyay Mukherjee

Abstract

Multilinear maps enable homomorphic computation on encoded values and a public procedure to check if the computation on the encoded values results in a zero. Encodings in known candidate constructions of multilinear maps have a (growing) noise component, which is crucial for security. For example, noise in GGH13 multilinear maps grows with the number of levels that need to be supported and must remain below the maximal noise supported by the multilinear map for correctness. A smaller maximal noise, which must be supported, is desirable both for reasons of security and efficiency. In this work, we put forward new candidate constructions of obfuscation for which the maximal supported noise is polynomial (in the security parameter). Our constructions are obtained by instantiating a modification of the Lin's [EUROCRYPT 2016] obfuscation construction with composite order variants of the GGH13 multilinear maps. For these schemes, we show that the maximal supported noise only needs to grow polynomially in the security parameter. We prove the security of these constructions in the weak multilinear map model that captures \emph{all known} vulnerabilities of GGH13 maps. Finally, we investigate the security of the considered composite order variants of GGH13 multilinear maps from a cryptanalytic standpoint.

Note: Corrected a few typos and clarified a minor issue in a proof.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
ObfuscationMulti-linear MapsNoise Growth
Contact author(s)
peihan @ berkeley edu
History
2018-09-07: last of 11 revisions
2016-06-07: received
See all versions
Short URL
https://ia.cr/2016/599
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/599,
      author = {Nico Döttling and Sanjam Garg and Divya Gupta and Peihan Miao and Pratyay Mukherjee},
      title = {Obfuscation from Low Noise Multilinear Maps},
      howpublished = {Cryptology ePrint Archive, Paper 2016/599},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/599}},
      url = {https://eprint.iacr.org/2016/599}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.