Paper 2021/1272

Efficient CCA Timed Commitments in Class Groups

Sri AravindaKrishnan Thyagarajan, Guilhem Castagnos, Fabien Laguillaumie, and Giulio Malavolta


Timed commitments [Boneh and Naor, CRYPTO 2000] are the timed analogue of standard commitments, where the commitment can be non-interactively opened after a pre-specified amount of time passes. Timed commitments have a large spectrum of applications, such as sealed bid auctions, fair contract signing, fair multi-party computation, and cryptocurrency payments. Unfortunately, all practical constructions rely on a (private-coin) trusted setup and do not scale well with the number of participants. These are two severe limiting factors that have hindered the widespread adoption of this primitive. In this work, we set out to resolve these two issues and propose an efficient timed commitment scheme that also satisfies the strong notion of CCA-security. Specifically, our scheme has a transparent (i.e. public-coin) one-time setup and the amount of sequential computation is essentially independent of the number of participants. As a key technical ingredient, we propose the first (linearly) homomorphic time-lock puzzle with a transparent setup, from class groups of imaginary quadratic order. To demonstrate the applicability of our scheme, we use it to construct a new distributed randomness generation protocol, where $n$ parties jointly sample a random string. Our protocol is the first to simultaneously achieve (1) high scalability in the number of participants, (2) transparent one-time setup, (3) lightning speed in the optimistic case where all parties are honest, and (4) ensure that the output random string is unpredictable and unbiased, even when the adversary corrupts $n-1$ parties. To substantiate the practicality of our approach, we implemented our protocol and our experimental evaluation shows that it is fast enough to be used in practice. We also evaluated a heuristic version of the protocol that is at least 3 orders of magnitude more efficient both in terms of communication size and computation time. This makes the protocol suitable for supporting hundreds of participants.

Note: Published at ACM CCS 2021

Available format(s)
Cryptographic protocols
Publication info
Preprint. Minor revision.
Timed CommitmentsDistributed Randomness Generation
Contact author(s)
t srikrishnan @ gmail com
2022-03-16: revised
2021-09-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sri AravindaKrishnan Thyagarajan and Guilhem Castagnos and Fabien Laguillaumie and Giulio Malavolta},
      title = {Efficient CCA Timed Commitments in Class Groups},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1272},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.