Towards Practical Homomorphic Time-Lock Puzzles: Applicability and Verifiability

Liu, Yi1,3; Wang, Qi1,2; Yiu, Siu-Ming3

10.1007/978-3-031-17140-6_21

2022

27th European Symposium on Research in Computer Security (ESORICS)

0302-9743

1611-3349

978-3-031-17139-0

LECT NOTES ARTIF INT

13554

SEP 26-30, 2022

Tech Univ Denmark,Copenhagen,DENMARK

GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND

SPRINGER INTERNATIONAL PUBLISHING AG

["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 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 applicability and verifiability. In terms of applicability, we design the first multiplicatively HTLP scheme with the solution space over Z*(n), which is more expressible than the original one, e.g., representing integers. Then, to fit HTLP into scenarios requiring verifiability that is missing in existing schemes, we propose three simple and 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.6KB in communication and 40 ms in computation. Hence, HTLP still demonstrates excellent efficiency in both communication and computation with these versatile properties."]

Public-key cryptography (Homomorphic) time-lock puzzles Repeated modular squaring Zero-knowledge

First ; Corresponding

English

CPCI-S

Computer Science ; Mathematics

Computer Science, Information Systems ; Computer Science, Theory & Methods ; Mathematics, Applied

WOS:000866560400021

Web of Science

1.Southern Univ Sci & Technol, Res Inst Trustworthy Autonomous Syst, Guangdong Prov Key Lab Braininspired Intelligent, Dept Comp Sci & Engn, Shenzhen 518055, Peoples R China
2.Southern Univ Sci & Technol, Natl Ctr Appl Math Shenzhen, NaCAM CETGC Network Informat Syst Modeling & Comp, Shenzhen 518055, Peoples R China
3.Univ Hong Kong, Dept Comp Sci, Hong Kong, Peoples R China

Liu, Yi,Wang, Qi,Yiu, Siu-Ming. Towards Practical Homomorphic Time-Lock Puzzles: Applicability and Verifiability[C]. GEWERBESTRASSE 11, CHAM, CH-6330, SWITZERLAND:SPRINGER INTERNATIONAL PUBLISHING AG,2022.