Candidate iO from Homomorphic Encryption Schemes

被引:37
作者
Brakerski, Zvika [1 ]
Doettling, Nico [2 ]
Garg, Sanjam [3 ]
Malavolta, Giulio [3 ,4 ,5 ]
机构
[1] Weizmann Inst Sci, Rehovot, Israel
[2] CISPA Helmoltz Ctr Informat Secur, Saarbrucken, Germany
[3] Univ Calif Berkeley, Berkeley, CA 94704 USA
[4] Carnegie Mellon Univ, Pittsburgh, PA 15213 USA
[5] Simons Inst Theory Comp, Berkeley, CA USA
来源
ADVANCES IN CRYPTOLOGY - EUROCRYPT 2020, PT I | 2020年 / 12105卷
基金
欧盟地平线“2020”; 以色列科学基金会;
关键词
D O I
10.1007/978-3-030-45721-1_4
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We propose a new approach to construct general-purpose indistinguishability obfuscation (iO). Our construction is obtained via a new intermediate primitive that we call split fully-homomorphic encryption (split FHE), which we show to be sufficient for constructing iO. Specifically, split FHE is FHE where decryption takes the following two-step syntactic form: (i) A secret decryption step uses the secret key and produces a hint which is (asymptotically) shorter than the length of the encrypted message, and (ii) a public decryption step that only requires the ciphertext and the previously generated hint (and not the entire secret key), and recovers the encrypted message. In terms of security, the hints for a set of ciphertexts should not allow one to violate semantic security for any other ciphertexts. Next, we show a generic candidate construction of split FHE based on three building blocks: (i) A standard FHE scheme with linear decrypt-and-multiply (which can be instantiated with essentially all LWE-based constructions), (ii) a linearly homomorphic encryption scheme with short decryption hints (such as the Damgard-Jurik encryption scheme, based on the DCR problem), and (iii) a cryptographic hash function (which can be based on a variety of standard assumptions). Our approach is heuristic in the sense that our construction is not provably secure and makes implicit assumptions about the interplay between these underlying primitives. We show evidence that this construction is secure by providing an argument in an appropriately defined oracle model. We view our construction as a big departure from the state-of-the-art constructions, and it is in fact quite simple.
引用
收藏
页码:79 / 109
页数:31
相关论文
共 55 条
[11]   Sum-of-Squares Meets Program Obfuscation, Revisited [J].
Barak, Boaz ;
Hopkins, Samuel B. ;
Jain, Aayush ;
Kothari, Pravesh ;
Sahai, Amit .
ADVANCES IN CRYPTOLOGY - EUROCRYPT 2019, PT I, 2019, 11476 :226-250
[12]  
Barak B, 2014, LECT NOTES COMPUT SC, V8441, P221, DOI 10.1007/978-3-642-55220-5_13
[13]  
Barak B, 2010, LECT NOTES COMPUT SC, V6110, P423
[14]  
Bellare Mihir, 1993, ACM CCS 1993, P62, DOI DOI 10.1145/168588.168596
[15]   From Cryptomania to Obfustopia Through Secret-Key Functional Encryption [J].
Bitansky, Nir ;
Nishimaki, Ryo ;
Passelegue, Alain ;
Wichs, Daniel .
THEORY OF CRYPTOGRAPHY, TCC 2016-B, PT II, 2016, 9986 :391-418
[16]   Indistinguishability Obfuscation from Functional Encryption [J].
Bitansky, Nir ;
Vaikuntanathan, Vinod .
2015 IEEE 56TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2015, :171-190
[17]   Multiparty Key Exchange, Efficient Traitor Tracing, and More from Indistinguishability Obfuscation [J].
Boneh, Dan ;
Zhandry, Mark .
ADVANCES IN CRYPTOLOGY - CRYPTO 2014, PT I, 2014, 8616 :480-499
[18]  
Brakerski Z., 2019, 2019720 CRYPT EPRINT
[19]  
Brakerski Z, 2014, LECT NOTES COMPUT SC, V8349, P1, DOI 10.1007/978-3-642-54242-8_1
[20]  
Brakerski Zvika., 2014, ITCS, P1, DOI DOI 10.1145/2554797.2554799