Paper 2023/740

Practical Robust DKG Protocols for CSIDH

Shahla Atapoor, imec-COSIC, KU Leuven
Karim Baghery, imec-COSIC, KU Leuven
Daniele Cozzo, IMDEA Software Institute, imec-COSIC, KU Leuven
Robi Pedersen, imec-COSIC, KU Leuven
Abstract

A Distributed Key Generation (DKG) protocol is an essential component of threshold cryptography. DKGs enable a group of parties to generate a secret and public key pair in a distributed manner so that the secret key is protected from being exposed, even if a certain number of parties are compromised. Robustness further guarantees that the construction of the key pair is always successful, even if malicious parties try to sabotage the computation. In this paper, we construct two efficient robust DKG protocols in the CSIDH setting that work with Shamir secret sharing. Both the proposed protocols are proven to be actively secure in the quantum random oracle model and use an Information Theoretically (IT) secure Verifiable Secret Sharing (VSS) scheme that is built using bivariate polynomials. As a tool, we construct a new piecewise verifiable proof system for structured public keys, that could be of independent interest. In terms of isogeny computations, our protocols outperform the previously proposed DKG protocols CSI-RAShi and Structured CSI-RAShi. As an instance, using our DKG protocols, 4 parties can sample a PK of size 4kB, for CSI-FiSh and CSI-SharK, respectively, 3.4 and 1.7 times faster than the current alternatives. On the other hand, since we use an IT-secure VSS, the fraction of corrupted parties is limited to less than a third and the communication cost of our schemes scales slightly worse with an increasing number of parties. For a low number of parties, our scheme still outperforms the alternatives in terms of communication.

Note: In the published version (at ACNS 2023), we compared the total outgoing communication cost within our protocols with the outgoing communication cost per party of the (structured) CSI-RAShi protocol. We amended this in the current version, leading to much more competitive communication costs when compared to the literature.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. ACNS 2023 - 21st International Conference on Applied Cryptography and Network Security
Keywords
Distributed Key GenerationCSIDHIsogeniesVerifiable Secret Sharing
Contact author(s)
shahla atapoor @ kuleuven be
baghery karim @ gmail com
daniele cozzo phd @ gmail com
robi pedersen @ esat kuleuven be
History
2023-05-25: approved
2023-05-23: received
See all versions
Short URL
https://ia.cr/2023/740
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/740,
      author = {Shahla Atapoor and Karim Baghery and Daniele Cozzo and Robi Pedersen},
      title = {Practical Robust DKG Protocols for CSIDH},
      howpublished = {Cryptology ePrint Archive, Paper 2023/740},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/740}},
      url = {https://eprint.iacr.org/2023/740}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.