Paper 2022/585

Towards Practical Homomorphic Time-Lock Puzzles: Applicability and Verifiability

Yi Liu
Qi Wang
Siu-Ming Yiu

Time-lock puzzle schemes allow one to encrypt messages for the future. More concretely, one can efficiently generate a time-lock puzzle for a secret/solution $s$, such that $s$ remains hidden until a specified time $T$ has elapsed, even for any parallel adversaries. However, since computation on secrets within multiple puzzles can be performed only when \emph{all} of these puzzles are solved, the usage of classical time-lock puzzles is greatly limited. Homomorphic time-lock puzzle (HTLP) schemes were thus proposed to allow evaluating functions over puzzles directly without solving them. However, although efficient HTLP schemes exist, more improvements are still needed for practicability. In this paper, we improve HTLP schemes to broaden their application scenarios from the aspects of \emph{applicability} and \emph{verifiability}. In terms of applicability, we design the \emph{first} multiplicatively HTLP scheme with the solution space over $\mathbb{Z}_n^*$, which is more expressible than the original one, \eg representing integers. Then, to fit HTLP into scenarios requiring verifiability that is missing in existing schemes, we propose three \emph{simple} and \emph{fast} protocols for both the additively HTLP scheme and our multiplicatively HTLP scheme, respectively. The first two protocols allow a puzzle solver to convince others of the correctness of the solution or the invalidity of the puzzle so that others do not need to solve the puzzle themselves. The third protocol allows a puzzle generator to prove the validity of his puzzles. It is shown that a puzzle in our scheme is only $1.25$KB, and one multiplication on puzzles takes simply $0.01$ms. Meanwhile, the overhead of each protocol is less than $0.6$KB in communication and $40$ms in computation. Hence, HTLP still demonstrates excellent efficiency in both communication and computation with these versatile properties.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. ESORICS 2022
Public-key cryptography (Homomorphic) time-lock puzzles Repeated modular squaring Zero-knowledge
Contact author(s)
liuy7 @ mail sustech edu cn
2022-08-17: last of 5 revisions
2022-05-17: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yi Liu and Qi Wang and Siu-Ming Yiu},
      title = {Towards Practical Homomorphic Time-Lock Puzzles: Applicability and Verifiability},
      howpublished = {Cryptology ePrint Archive, Paper 2022/585},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.