cispa_all_2969.pdf (449.56 kB)

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

Download (449.56 kB)
conference contribution
posted on 2023-11-29, 18:11 authored by Zvika Brakerski, Nico DöttlingNico Döttling, Sanjam Garg, Giulio Malavolta
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 − σ for σ = o(1). Our scheme is based on the hardness of the Learning with Errors (LWE) problem and σ 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.


Preferred Citation

Zvika Brakerski, Nico Döttling, Sanjam Garg and Giulio Malavolta. Leveraging Linear Decryption: Rate-1 Fully-Homomorphic Encryption and Time-Lock Puzzles. In: Theory of Cryptography Conference (TCC). 2019.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Theory of Cryptography Conference (TCC)

Legacy Posted Date


Open Access Type

  • Unknown


@inproceedings{cispa_all_2969, title = "Leveraging Linear Decryption: Rate-1 Fully-Homomorphic Encryption and Time-Lock Puzzles", author = "Brakerski, Zvika and Döttling, Nico and Garg, Sanjam and Malavolta, Giulio", booktitle="{Theory of Cryptography Conference (TCC)}", year="2019", }

Usage metrics


    No categories selected


    Ref. manager