Poster: Tight Short-Lived Signatures Arup Mondal Ashoka University Sonipat, Haryana, India arup.mondal phd19@ashoka.edu.in Ruthu Hulikal Rooparaghunath Vrije Universiteit Amsterdam, The Netherlands r.rooparaghunath@student.vu.nl Debayan Gupta Ashoka University Sonipat, Haryana, India debayan.gupta@ashoka.edu.in Abstract—A Time-lock puzzle (TLP) sends information into the future: a predetermined number of sequential computations must occur (i.e., a predetermined amount of time must pass) to retrieve the information, regardless of parallelization. Buoyed by the excitement around secure decentralized applications and cryptocurrencies, the last decade has witnessed numerous con- structions of TLP variants and related applications (e.g., cost- efficient blockchain designs, randomness beacons, e-voting, etc.). In this poster, we first extend the notion of TLP by formally defining the “time-lock public key encryption” (TLPKE) scheme. Next, we introduce and construct a “tight short-lived signatures” scheme using our TLPKE. Furthermore, to test the validity of our proposed schemes, we do a proof-of-concept implementation and run detailed simulations. Index Terms—Time-Lock Puzzle, Short-Lived Signatures. I. INTRODUCTION A short-lived signature (SLS) provides a verifier with two possibilities: either a generated signature σ on m is correct, or a user has expended a minimum predetermined amount of sequential work (T steps or time) to forge the signature. In other words, the signatures created remain valid for a short period of time T. Formally, we define the unforgeability period as the time starting from when a signer creates a signature for a message using their private signing information (or key) and the Sign algorithm. Once the unforgeability period T has elapsed, anyone can compute a forged signature using some public signing information and the ForgeSign algorithm. Recall that any party can compute a forged signature (using ForgeSign) after the unforgeability period T has passed. However, there is no guarantee that a party cannot generate a forged signature in advance. To ensure this, we use the same model used in [1]. The signature incorporates a random beacon value to ensure it was not created before a specific time T0. Suppose a verifier observes the signature within ˆT units of time after T0. In this case, they will believe it is a valid signature if ˆT < T because it would be impossible to have forged the signature within that time period. Once ˆT ≥T, the signature is no longer convincing as it may have been constructed through forgery. Brief Concurrent Work: Recently, Arun et al. [1] studied the variants notion of short-lived cryptographic primitives, i.e., short-lived proofs and signatures. Similar to our work, they make use of sequentially-ordered computations (T-sequential computation) as a means to enforce time delay during which signatures are unforgeable but become forgeable afterward ((1+c)·T-sequential computations). In this work, we use the same models as used in [1], however, we define and construct tight short-lived signatures, where the forged signatures can be generated in time not much more than sequentially bound T. In other words, tight short-lived signatures ensure that forged signatures can be generated in exactly T sequential computations. TABLE I: Complexity comparison of SLS schemes. Paper Setup & Sign Forge Sign Verify Tight Arun et al. [1] poly(λ) O((1 + c) · T ) VDF ([2], [3]) No Algorithm poly(λ) O(T ) O(1) Yes Short-lived cryptographic primitives have many real-life use cases; we refer to [1] for a detailed discussion of its applica- tions. Our main contributions are summarised as follows: • First, we extend the time-lock puzzle [4] by formally defining the “time-lock public key encryption” (TLPKE) scheme, and demonstrate a construction using a re- peated squaring assumption in a group of unknown order (Sec. III). • We introduce and construct a “tight short-lived signature” scheme from our TLPKE sche