Cryptology ePrint Archive: Report 2016/599

Obfuscation from Low Noise Multilinear Maps

Nico Döttling and Sanjam Garg and Divya Gupta and 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.

Category / Keywords: Public-Key Cryptography / Obfuscation, Multi-linear Maps, Noise Growth

Date: received 6 Jun 2016, last revised 7 Sep 2018

Contact author: peihan at berkeley edu

Available format(s): PDF | BibTeX Citation

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

Version: 20180907:235308 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]