Verifiable Sequential Work with Trusted Generator

Verifiable delay functions (VDF) proposed by Boneh et al. (Crypto’18) has several applications on blockchain based systems, random beacons and etc. Although the highly practical applications, less than a handful of constructions are known due to the need of efficient public verifiability. In the best of our knowledge, the only two constructions are from Pietrzak (EPRINT’ 18) and Wesolowski (EPRINT’ 18). In this paper, we define a VDF variant, which we denote by verifiable sequential work (VSW). The main idea is to take the sequential computations in VDF to reduce the difficulty of a hard problem to a moderated hard level. We construct a weakened VSW which needs a trusted third-party to run the generation phase: the VSW with trusted generator (VSWTG). The construction achieves a simple, one message and one group exponentiation publicly verifiable VSWTG. It is a more computational efficient verification procedure than the known VDF verification constructions. We regard the need for a trusted party as a necessary trade-off, however, we conjecture our variant may be easier to find other candidate constructions than the VDF definition. Finally, we formalize the idea of the Rivest-Shamir-Wagner (RSW) time-lock puzzle to a new primitive that we call trapdoor iterated sequential functions (TDISF) and investigate on its possible candidates.