Paper 2022/1469

Supersingular Curves You Can Trust

Andrea Basso, University of Birmingham
Giulio Codogni, University of Rome Tor Vergata
Deirdre Connolly, Zcash Foundation
Luca De Feo, IBM Research Europe
Tako Boris Fouotsa, École Polytechnique Fédérale de Lausanne
Guido Maria Lido, University of Rome Tor Vergata
Travis Morrison, Virginia Tech
Lorenz Panny, Academia Sinica
Sikhar Patranabis, IBM Research India
Benjamin Wesolowski, University of Bordeaux, French Institute for Research in Computer Science and Automation
Abstract

Generating a supersingular elliptic curve such that nobody knows its endomorphism ring is a notoriously hard task, despite several isogeny-based protocols relying on such an object. A trusted setup is often proposed as a workaround, but several aspects remain unclear. In this work, we develop the tools necessary to practically run such a distributed trusted-setup ceremony. Our key contribution is the first statistically zero-knowledge proof of isogeny knowledge that is compatible with any base field. To prove statistical ZK, we introduce isogeny graphs with Borel level structure and prove they have the Ramanujan property. Then, we analyze the security of a distributed trusted-setup protocol based on our ZK proof in the simplified universal composability framework. Lastly, we develop an optimized implementation of the ZK proof, and we propose a strategy to concretely deploy the trusted-setup protocol.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Isogenies Ramanajuan Graphs Zero-knowledge Proofs Trusted Setup
Contact author(s)
a basso @ cs bham ac uk
codogni @ mat uniroma2 it
durumcrustulum @ gmail com
secuer @ defeo lu
tako fouotsa @ epfl ch
guidomaria lido @ uniroma2 it
tmo @ vt edu
lorenz @ yx7 cc
sikhar patranabis @ ibm com
History
2022-10-27: approved
2022-10-26: received
See all versions
Short URL
https://ia.cr/2022/1469
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2022/1469,
      author = {Andrea Basso and Giulio Codogni and Deirdre Connolly and Luca De Feo and Tako Boris Fouotsa and Guido Maria Lido and Travis Morrison and Lorenz Panny and Sikhar Patranabis and Benjamin Wesolowski},
      title = {Supersingular Curves You Can Trust},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1469},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1469}},
      url = {https://eprint.iacr.org/2022/1469}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.