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
ISBN: 9781450384544
Abstract
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
University of Montpellier / Université Montpellier
France (FR)
Université de Bordeaux
France (FR)
Max-Planck-Institut für Sicherheit und Privatsphäre / Max Planck Institute for Security and Privacy
Germany (DE)
France (FR)
Université de Bordeaux
France (FR)
Max-Planck-Institut für Sicherheit und Privatsphäre / Max Planck Institute for Security and Privacy
Germany (DE)
How to cite
APA:
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.
MLA:
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