Efficient CCA Timed Commitments in Class Groups

Thyagarajan SAK, Castagnos G, Laguillaumie F, Malavolta G (2021)

Publication Type: Conference contribution

Publication year: 2021

Publisher: Association for Computing Machinery

Pages Range: 2663-2684

Conference Proceedings Title: Proceedings of the ACM Conference on Computer and Communications Security

Event location: Online KR

ISBN: 9781450384544

DOI: 10.1145/3460120.3484773


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.

Authors with CRIS profile

Involved external institutions

How to cite


Thyagarajan, S.A.K., Castagnos, G., Laguillaumie, F., & Malavolta, G. (2021). Efficient CCA Timed Commitments in Class Groups. In Proceedings of the ACM Conference on Computer and Communications Security (pp. 2663-2684). Online, KR: Association for Computing Machinery.


Thyagarajan, Sri Aravinda Krishnan, et al. "Efficient CCA Timed Commitments in Class Groups." Proceedings of the 27th ACM Annual Conference on Computer and Communication Security, CCS 2021, Online Association for Computing Machinery, 2021. 2663-2684.

BibTeX: Download