Paper 2016/1097

Projective Arithmetic Functional Encryption and Indistinguishability Obfuscation From Degree-5 Multilinear Maps

Prabhanjan Ananth and Amit Sahai

Abstract

In this work, we propose a variant of functional encryption called projective arithmetic functional encryption (PAFE). Roughly speaking, our notion is like functional encryption for arithmetic circuits, but where secret keys only yield partially decrypted values. These partially decrypted values can be linearly combined with known coefficients and the result can be tested to see if it is a small value. We give a degree-preserving construction of PAFE from multilinear maps. That is, we show how to achieve PAFE for arithmetic circuits of degree d using only degree-d multilinear maps. Our construction is based on an assumption over such multilinear maps, that we justify in a generic model. We then turn to applying our notion of PAFE to one of the most pressing open problems in the foundations of cryptography: building secure indistinguishability obfuscation (iO) from simpler building blocks. iO from degree-5 multilinear maps. Recently, the works of Lin [Eurocrypt 2016] and Lin-Vaikuntanathan [FOCS 2016] showed how to build iO from constant-degree multilinear maps. However, no explicit constant was given in these works, and an analysis of these published works shows that the degree requirement would be in excess of 30. The ultimate "dream" goal of this line of work would be to reduce the degree requirement all the way to 2, allowing for the use of well-studied bilinear maps, or barring that, to a low constant that may be supportable by alternative secure low-degree multilinear map candidates. We make substantial progress toward this goal by showing how to leverage PAFE for degree-5 arithmetic circuits to achieve iO, thus yielding the first iO construction from degree-5 multilinear maps.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
Indistinguishability Obfuscationconstant degree multilinear mapsarithmetic functional encryption
Contact author(s)
prabhanjan va @ gmail com
History
2016-11-22: received
Short URL
https://ia.cr/2016/1097
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/1097,
      author = {Prabhanjan Ananth and Amit Sahai},
      title = {Projective Arithmetic Functional Encryption and Indistinguishability Obfuscation From Degree-5 Multilinear Maps},
      howpublished = {Cryptology ePrint Archive, Paper 2016/1097},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/1097}},
      url = {https://eprint.iacr.org/2016/1097}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.