**CSI-RAShi: Distributed key generation for CSIDH**

*Ward Beullens and Lucas Disson and 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.

**Category / Keywords: **public-key cryptography / Isogeny-based cryptography, distributed key generation, secret sharing, class group action, CSIDH, QROM

**Date: **received 22 Oct 2020, last revised 22 Oct 2020

**Contact author: **ward beullens at esat kuleuven be, lucas disson@ens-lyon fr, robi pedersen@esat kuleuven be, frederik vercauteren@esat kuleuven be

**Available format(s): **PDF | BibTeX Citation

**Version: **20201023:084819 (All versions of this report)

**Short URL: **ia.cr/2020/1323

[ Cryptology ePrint archive ]