Paper 2019/720

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

Zvika Brakerski, Nico Döttling, Sanjam Garg, and 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-\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.

Available format(s)
Public-key cryptography
Publication info
Preprint. Minor revision.
Fully-Homomorphic EncryptionHigh-RateTime-Lock Puzzles
Contact author(s)
giulio malavolta @ hotmail it
nico doettling @ gmail com
sanjamg @ berkeley edu
zvika brakerski @ weizmann ac il
2019-06-18: revised
2019-06-18: received
See all versions
Short URL
Creative Commons Attribution


      author = {Zvika Brakerski and Nico Döttling and Sanjam Garg and Giulio Malavolta},
      title = {Leveraging Linear Decryption: Rate-1 Fully-Homomorphic Encryption and Time-Lock Puzzles},
      howpublished = {Cryptology ePrint Archive, Paper 2019/720},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.