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

被引:68
作者
Ananth, Prabhanjan [1 ]
Sahai, Amit
机构
[1] Univ Calif Los Angeles, Ctr Encrypted Funct, Los Angeles, CA 90095 USA
来源
ADVANCES IN CRYPTOLOGY - EUROCRYPT 2017, PT I | 2017年 / 10210卷
基金
美国国家科学基金会;
关键词
PREDICATE ENCRYPTION;
D O I
10.1007/978-3-319-56620-7_6
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
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.
引用
收藏
页码:152 / 181
页数:30
相关论文
共 56 条
[1]  
Abdalla M., 2016, Paper 2016/011
[2]   Simple Functional Encryption Schemes for Inner Products [J].
Abdalla, Michel ;
Bourse, Florian ;
De Caro, Angelo ;
Pointcheval, David .
PUBLIC-KEY CRYPTOGRAPHY - PKC 2015, 2015, 9020 :733-751
[3]   On the Practical Security of Inner Product Functional Encryption [J].
Agrawal, Shashank ;
Agrawal, Shweta ;
Badrinarayanan, Saikrishna ;
Kumarasubramanian, Abishek ;
Prabhakaran, Manoj ;
Sahai, Amit .
PUBLIC-KEY CRYPTOGRAPHY - PKC 2015, 2015, 9020 :777-798
[4]  
Ananth P., 2016, 20161097 CRYPT EPRIN
[5]   From Selective to Adaptive Security in Functional Encryption [J].
Ananth, Prabhanjan ;
Brakerski, Zvika ;
Segev, Gil ;
Vaikuntanathan, Vinod .
ADVANCES IN CRYPTOLOGY, PT II, 2015, 9216 :657-677
[6]   Indistinguishability Obfuscation from Compact Functional Encryption [J].
Ananth, Prabhanjan ;
Jain, Abhishek .
ADVANCES IN CRYPTOLOGY, PT I, 2015, 9215 :308-326
[7]  
Ananth Prabhanjan., 2015, IACR Cryptol. ePrint Arch., V2015, P730
[8]  
[Anonymous], 2015, FOCS
[9]  
[Anonymous], IACR CRYPTOLOGY EPRI
[10]  
[Anonymous], 2014, IACR CRYPTOLOGY EPRI