Cryptology ePrint Archive: Report 2020/739

Generic Constructions of Incremental and Homomorphic Timed-Release Encryption

Peter Chvojka and Tibor Jager and Daniel Slamanig and Christoph Striecks

Abstract: Timed-release encryption (TRE) makes it possible to send information ``into the future'' such that a pre-determined amount of time needs to pass before the information can be decrypted, which has found numerous applications. The most prominent construction is based on sequential squaring in RSA groups, proposed by Rivest et al. in 1996. Malavolta and Thyagarajan (CRYPTO'19) recently proposed an interesting variant of TRE called homomorphic time-lock puzzles (HTLPs). Here one considers multiple puzzles which can be independently generated by different entities. One can homomorphically evaluate a circuit over these puzzles to obtain a new puzzle. Solving this new puzzle yields the output of a circuit evaluated on all solutions of the original puzzles. While this is an interesting concept and enables various new applications, for constructions under standard assumptions one has to rely on sequential squaring.

We observe that viewing HTLPs as homomorphic TRE gives rise to a simple generic construction that avoids the homomorphic evaluation on the puzzles and thus the restriction of relying on sequential squaring. It can be instantiated based on any TLP, such as those based on one-way functions and the LWE assumption (via randomized encodings), while providing essentially the same functionality for applications. Moreover, it overcomes the limitation of the approach of Malavolta and Thyagarajan that, despite the homomorphism, one puzzle needs to be solved per decrypted ciphertext. Hence, we obtain a ``solve one, get many for free'' property for an arbitrary amount of encrypted data, as we only need to solve a single puzzle independent of the number of ciphertexts. In addition, we introduce the notion of incremental TLPs as a particularly useful generalization of TLPs, which yields particularly practical (homomorphic) TRE schemes. Finally, we demonstrate various applications by firstly showcasing their cryptographic application to construct dual variants of timed-release functional encryption and also show that we can instantiate previous applications of HTLPs in a simpler and more efficient way.

Category / Keywords: public-key cryptography / (Homomorphic) time-lock puzzles, incremental time-lock-puzzles, timed-release encryption, generic constructions, public key cryptography

Date: received 17 Jun 2020

Contact author: chvojka at uni-wuppertal de, tibor jager@uni-wuppertal de, daniel slamanig@ait ac at, christoph striecks@ait ac at

Available format(s): PDF | BibTeX Citation

Version: 20200618:155104 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]