Paper 2020/1323

CSI-RAShi: Distributed key generation for CSIDH

Ward Beullens, Lucas Disson, Robi Pedersen, and Frederik Vercauteren

Abstract

We present an honest-majority Distributed Key Generation protocol (DKG) based on Shamir's $(k,n)$-threshold secret sharing in the setting of Very Hard Homogenous Spaces (VHHS). DKG's in the DLOG setting use Pedersen commitments, for which there is no known analogue in the VHHS setting. As a replacement, we introduce a new primitive called piecewise verifiable proofs, which allow a prover to prove that a list of NP-statements is valid with respect to a common witness, and such that the different statements can be verified individually. Our protocol is robust and actively secure in the Quantum Random Oracle Model. For $n$ participants, the total runtime of our protocol is\break $2+\lambda+n(1+4\lambda)$ group action evaluations, where $\lambda$ is the underlying security parameter, and is thus independent of the threshold $k$. When instantiated with CSIDH-512, this amounts to approximately $4.5+18n$ seconds.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Isogeny-based cryptographydistributed key generationsecret sharingclass group actionCSIDHQROM
Contact author(s)
ward beullens @ esat kuleuven be
lucas disson @ ens-lyon fr
robi pedersen @ esat kuleuven be
frederik vercauteren @ esat kuleuven be
History
2020-10-23: received
Short URL
https://ia.cr/2020/1323
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/1323,
      author = {Ward Beullens and Lucas Disson and Robi Pedersen and Frederik Vercauteren},
      title = {CSI-RAShi: Distributed key generation for CSIDH},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1323},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/1323}},
      url = {https://eprint.iacr.org/2020/1323}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.