Leveraging Linear Decryption: Rate-1 Fully-Homomorphic Encryption and Time-Lock Puzzles

被引:47
作者
Brakerski, Zvika [1 ]
Doettling, Nico [2 ]
Garg, Sanjam [3 ]
Malavolta, Giulio [4 ]
机构
[1] Weizmann Inst Sci, Rehovot, Israel
[2] CISPA Helmholtz Ctr Informat Secur, Saarbrucken, Germany
[3] Univ Calif Berkeley, Berkeley, CA 94720 USA
[4] Simons Inst Theory Comp, Berkeley, CA 94720 USA
来源
THEORY OF CRYPTOGRAPHY, TCC 2019, PT II | 2019年 / 11892卷
基金
欧洲研究理事会; 美国国家科学基金会; 以色列科学基金会; 欧盟地平线“2020”;
关键词
D O I
10.1007/978-3-030-36033-7_16
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
We show how to combine a fully-homomorphic encryption scheme with linear decryption and a linearly-homomorphic encryption schemes to obtain constructions with new properties. Specifically, we present the following new results. (1) Rate-1 Fully-Homomorphic Encryption: We construct the first scheme with message-to-ciphertext length ratio (i.e., rate) 1 - sigma for sigma = o(1). Our scheme is based on the hardness of the Learning with Errors (LWE) problem and sigma is proportional to the noise-to-modulus ratio of the assumption. Our building block is a construction of a new high-rate linearly-homomorphic encryption. One application of this result is the first general-purpose secure function evaluation protocol in the preprocessing model where the communication complexity is within additive factor of the optimal insecure protocol. (2) Fully-Homomorphic Time-Lock Puzzles: We construct the first time-lock puzzle where one can evaluate any function over a set of puzzles without solving them, from standard assumptions. Prior work required the existence of sub-exponentially hard indistinguishability obfuscation.
引用
收藏
页码:407 / 437
页数:31
相关论文
共 32 条
[1]  
Alperin-Sheriff J, 2014, LECT NOTES COMPUT SC, V8616, P297, DOI 10.1007/978-3-662-44371-2_17
[2]   Homomorphic Secret Sharing from Lattices Without FHE [J].
Boyle, Elette ;
Kohl, Lisa ;
Scholl, Peter .
ADVANCES IN CRYPTOLOGY - EUROCRYPT 2019, PT II, 2019, 11477 :3-33
[3]   Breaking the Circuit Size Barrier for Secure Computation Under DDH [J].
Boyle, Elette ;
Gilboa, Niv ;
Ishai, Yuval .
ADVANCES IN CRYPTOLOGY - CRYPTO 2016, PT I, 2016, 9814 :509-539
[4]  
Brakerski Zvika, 2014, ACM Transactions on Computation Theory, V6, DOI 10.1145/2633600
[5]   Two-Message Statistically Sender-Private OT from LWE [J].
Brakerski, Zvika ;
Dottling, Nico .
THEORY OF CRYPTOGRAPHY, TCC 2018, PT II, 2018, 11240 :370-390
[6]  
Brakerski Z, 2013, LECT NOTES COMPUT SC, V7778, P1, DOI 10.1007/978-3-642-36362-7_1
[7]   Efficient Fully Homomorphic Encryption from (Standard) LWE [J].
Brakerski, Zvika ;
Vaikuntanathan, Vinod .
2011 IEEE 52ND ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2011), 2011, :97-106
[8]  
Brakerski Zvika., 2014, P 5 C INNOVATIONS TH, P1, DOI DOI 10.1145/2554797.2554799
[9]  
Canetti R, 2015, LECT NOTES COMPUT SC, V9015, P468, DOI 10.1007/978-3-662-46497-7_19
[10]  
Chor B, 1995, AN S FDN CO, P41, DOI 10.1109/SFCS.1995.492461