Paper 2022/1189

CSI-SharK: CSI-FiSh with Sharing-friendly Keys

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

CSI-FiSh is one of the most efficient isogeny-based signature schemes, which is proven to be secure in the Quantum Random Oracle Model (QROM). However, there is a bottleneck in CSI-FiSh in the threshold setting, which is that its public key needs to be generated by using $k-1$ secret keys. This leads to very inefficient threshold key generation protocols and also forces the parties to store $k-1$ secret shares. We present CSI-SharK, a new variant of $\textit{CSI}$-FiSh that has more $\textit{Shar}$ing-friendly $\textit{K}$eys and is as efficient as the original scheme. This is accomplished by modifying the public key of the ID protocol, used in the original CSI-FiSh, to the equal length Structured Public Key (SPK), generated by a $\textit{single}$ secret key, and then proving that the modified ID protocol and the resulting signature scheme remain secure in the QROM. We translate existing CSI-FiSh-based threshold signatures and Distributed Key Generation (DKG) protocols to the CSI-SharK setting. We find that DKG schemes based on CSI-SharK outperform the state-of-the-art actively secure DKG protocols from the literature by a factor of about $3$, while also strongly reducing the communication cost between the parties. We also uncover and discuss a flaw in the key generation of the actively secure CSI-FiSh based threshold signature scheme $\textit{Sashimi}$, that can prevent parties from signing. Finally, we discuss how (distributed) key generation and signature schemes in the isogeny setting are strongly parallelizable and we show that by using $C$ independent CPU threads, the total runtime of such schemes can basically be reduced by a factor $C$. As multiple threads are standard in modern CPU architecture, this parallelizability is a strong incentive towards using isogeny-based (distributed) key generation and signature schemes in practical scenarios.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Isogeny-based cryptography Distributed Key Generation Threshold Schemes Secret Sharing CSIDH
Contact author(s)
shahla atapoor @ kuleuven be
baghery karim @ gmail com
daniele cozzo @ kuleuven be
robi pedersen @ esat kuleuven be
History
2022-09-09: approved
2022-09-09: received
See all versions
Short URL
https://ia.cr/2022/1189
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1189,
      author = {Shahla Atapoor and Karim Baghery and Daniele Cozzo and Robi Pedersen},
      title = {CSI-SharK: CSI-FiSh with Sharing-friendly Keys},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1189},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1189}},
      url = {https://eprint.iacr.org/2022/1189}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.