Supersingular Curves You Can Trust

Andrea Basso; Giulio Codogni; Deirdre Connolly; Luca De Feo; Tako Boris Fouotsa; Guido Maria Lido; Travis Morrison; Lorenz Panny; Sikhar Patranabis; Benjamin Wesolowski

doi:10.1007/978-3-031-30617-4_14

Supersingular Curves You Can Trust

Andrea Basso^*
, Giulio Codogni
, Deirdre Connolly
, Luca De Feo
, Tako Boris Fouotsa
, Guido Maria Lido
, Travis Morrison
, Lorenz Panny
, Sikhar Patranabis
, Benjamin Wesolowski

^*Corresponding author for this work

Systems and Software Security

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

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.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2023
Subtitle of host publication	42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II
Editors	Carmit Hazay, Martijn Stam
Place of Publication	Cham
Publisher	Springer Cham
Pages	405-437
Number of pages	33
ISBN (Electronic)	9783031306174
ISBN (Print)	9783031306167
DOIs	https://doi.org/10.1007/978-3-031-30617-4_14
Publication status	Published - 15 Apr 2023
Event	42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques - Lyon, France Duration: 23 Apr 2023 → 27 Apr 2023

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	14005
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques
Abbreviated title	EUROCRYPT 2023
Country/Territory	France
City	Lyon
Period	23/04/23 → 27/04/23

Keywords

isogenies
Ramanujan graphs
zero-knowledge proofs
trusted setup

Access to Document

10.1007/978-3-031-30617-4_14

Cite this

Basso, A., Codogni, G., Connolly, D., De Feo, L., Fouotsa, T. B., Lido, G. M., Morrison, T., Panny, L., Patranabis, S., & Wesolowski, B. (2023). Supersingular Curves You Can Trust. In C. Hazay, & M. Stam (Eds.), Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II (pp. 405-437). (Lecture Notes in Computer Science; Vol. 14005). Springer Cham. https://doi.org/10.1007/978-3-031-30617-4_14

Basso, Andrea ; Codogni, Giulio ; Connolly, Deirdre et al. / Supersingular Curves You Can Trust. Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II. editor / Carmit Hazay ; Martijn Stam. Cham : Springer Cham, 2023. pp. 405-437 (Lecture Notes in Computer Science).

@inproceedings{9be3384849474222a9f8d97e5971e57a,

title = "Supersingular Curves You Can Trust",

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.",

keywords = "isogenies, Ramanujan graphs, zero-knowledge proofs, trusted setup",

author = "Andrea Basso and Giulio Codogni and Deirdre Connolly and \{De Feo\}, Luca and Fouotsa, \{Tako Boris\} and Lido, \{Guido Maria\} and Travis Morrison and Lorenz Panny and Sikhar Patranabis and Benjamin Wesolowski",

year = "2023",

month = apr,

day = "15",

doi = "10.1007/978-3-031-30617-4\_14",

language = "English",

isbn = "9783031306167",

series = "Lecture Notes in Computer Science",

publisher = "Springer Cham",

pages = "405--437",

editor = "Carmit Hazay and Martijn Stam",

booktitle = "Advances in Cryptology {\textendash} EUROCRYPT 2023",

address = "Switzerland",

note = "42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2023 ; Conference date: 23-04-2023 Through 27-04-2023",

}

Basso, A, Codogni, G, Connolly, D, De Feo, L, Fouotsa, TB, Lido, GM, Morrison, T, Panny, L, Patranabis, S & Wesolowski, B 2023, Supersingular Curves You Can Trust. in C Hazay & M Stam (eds), Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II. Lecture Notes in Computer Science, vol. 14005, Springer Cham, Cham, pp. 405-437, 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, 23/04/23. https://doi.org/10.1007/978-3-031-30617-4_14

Supersingular Curves You Can Trust. / Basso, Andrea; Codogni, Giulio; Connolly, Deirdre et al.
Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II. ed. / Carmit Hazay; Martijn Stam. Cham: Springer Cham, 2023. p. 405-437 (Lecture Notes in Computer Science; Vol. 14005).

Research output: Chapter in Book/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Supersingular Curves You Can Trust

AU - Basso, Andrea

AU - Codogni, Giulio

AU - Connolly, Deirdre

AU - De Feo, Luca

AU - Fouotsa, Tako Boris

AU - Lido, Guido Maria

AU - Morrison, Travis

AU - Panny, Lorenz

AU - Patranabis, Sikhar

AU - Wesolowski, Benjamin

PY - 2023/4/15

Y1 - 2023/4/15

N2 - 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.

AB - 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.

KW - isogenies

KW - Ramanujan graphs

KW - zero-knowledge proofs

KW - trusted setup

U2 - 10.1007/978-3-031-30617-4_14

DO - 10.1007/978-3-031-30617-4_14

M3 - Conference contribution

SN - 9783031306167

T3 - Lecture Notes in Computer Science

SP - 405

EP - 437

BT - Advances in Cryptology – EUROCRYPT 2023

A2 - Hazay, Carmit

A2 - Stam, Martijn

PB - Springer Cham

CY - Cham

T2 - 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques

Y2 - 23 April 2023 through 27 April 2023

ER -

Basso A, Codogni G, Connolly D, De Feo L, Fouotsa TB, Lido GM et al. Supersingular Curves You Can Trust. In Hazay C, Stam M, editors, Advances in Cryptology – EUROCRYPT 2023: 42nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Lyon, France, April 23–27, 2023, Proceedings, Part II. Cham: Springer Cham. 2023. p. 405-437. (Lecture Notes in Computer Science). doi: 10.1007/978-3-031-30617-4_14

Supersingular Curves You Can Trust

Abstract

Publication series

Conference

Keywords

Access to Document

Fingerprint

Cite this