Cryptology ePrint Archive: Report 2019/635

Homomorphic Time-Lock Puzzles and Applications

Giulio Malavolta and Sri Aravinda Krishnan Thyagarajan

Abstract: Time-lock puzzles allow one to encrypt messages for the future, by efficiently generating a puzzle with a solution $s$ that remains hidden until time $T$ has elapsed. The solution is required to be concealed from the eyes of any algorithm running in (parallel) time less than $T$.

We put forth the concept of \emph{homomorphic time-lock puzzles}, where one can evaluate functions over puzzles without solving them, i.e., one can manipulate a set of puzzles with solutions $(s_1, \dots, s_n)$ to obtain a puzzle that solves to $f(s_1, \ldots, s_n)$, for any function $f$. We propose candidate constructions under concrete cryptographic assumptions for different classes of functions. Then we show how homomorphic time-lock puzzles overcome the limitations of classical time-lock puzzles by proposing new protocols for applications of interest, such as e-voting, multi-party coin flipping, and fair contract signing.

Category / Keywords: public-key cryptography / Time-Lock Puzzles, Homomorphic Encryption

Original Publication (with minor differences): IACR-CRYPTO-2019

Date: received 2 Jun 2019, last revised 3 Jun 2019

Contact author: giulio malavolta at hotmail it, sri aravinda krishnan thyagarajan at cs fau de

Available format(s): PDF | BibTeX Citation

Note: Full version of the work.

Version: 20190603:092059 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]