CryptoDB
Leveraging Linear Decryption: Rate-1 Fully-Homomorphic Encryption and Time-Lock Puzzles
| Authors: | |
|---|---|
| Download: | |
| Abstract: | 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. |
BibTeX
@article{tcc-2019-30002,
title={Leveraging Linear Decryption: Rate-1 Fully-Homomorphic Encryption and Time-Lock Puzzles},
booktitle={Theory of Cryptography},
series={Lecture Notes in Computer Science},
publisher={Springer},
volume={11892},
pages={407-437},
doi={10.1007/978-3-030-36033-7_16},
author={Zvika Brakerski and Nico Döttling and Sanjam Garg and Giulio Malavolta},
year=2019
}