The SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponents

Jorge Chávez-Saab; Jesús Javier Chi-Domínguez; Samuel Jaques; Francisco Rodríguez-Henríquez

doi:10.1007/s13389-021-00271-w

The SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponents

Jorge Chávez-Saab, Jesús Javier Chi-Domínguez, Samuel Jaques, Francisco Rodríguez-Henríquez

Computing Sciences

Research output: Contribution to journal › Article › Scientific › peer-review

19 Citations (Scopus)

14 Downloads (Pure)

Abstract

Recent independent analyses by Bonnetain–Schrottenloher and Peikert in Eurocrypt 2020 significantly reduced the estimated quantum security of the isogeny-based commutative group action key-exchange protocol CSIDH. This paper refines the estimates of a resource-constrained quantum collimation sieve attack to give a precise quantum security to CSIDH. Furthermore, we optimize large CSIDH parameters for performance while still achieving the NIST security levels 1, 2, and 3. Finally, we provide a C-code constant-time implementation of those CSIDH large instantiations using the square-root-complexity Vélu’s formulas recently proposed by Bernstein, De Feo, Leroux and Smith.

Original language	English
Journal	JOURNAL OF CRYPTOGRAPHIC ENGINEERING
Volume	12
Issue number	3
Early online date	31 Aug 2021
DOIs	https://doi.org/10.1007/s13389-021-00271-w
Publication status	Published - 2022
Publication type	A1 Journal article-refereed

Keywords

Isogeny-based cryptography
Post-quantum cryptography
Quantum cryptanalysis
[Constant time implementations]
[Finite field arithmetic]

Publication forum classification

Publication forum level 1

ASJC Scopus subject areas

Software
Computer Networks and Communications

Access to Document

10.1007/s13389-021-00271-wLicence: CC BY

The SQALE of CSIDH sublinear Vélu quantum-resistant isogeny action with low exponentsFinal published version, 747 KBLicence: CC BY

http://urn.fi/URN:NBN:fi:tuni-202109247267Licence: CC BY

Cite this

@article{0028ff5b194c4e4dbda94b3bb57c7d47,

title = "The SQALE of CSIDH: sublinear V{\'e}lu quantum-resistant isogeny action with low exponents",

abstract = "Recent independent analyses by Bonnetain–Schrottenloher and Peikert in Eurocrypt 2020 significantly reduced the estimated quantum security of the isogeny-based commutative group action key-exchange protocol CSIDH. This paper refines the estimates of a resource-constrained quantum collimation sieve attack to give a precise quantum security to CSIDH. Furthermore, we optimize large CSIDH parameters for performance while still achieving the NIST security levels 1, 2, and 3. Finally, we provide a C-code constant-time implementation of those CSIDH large instantiations using the square-root-complexity V{\'e}lu{\textquoteright}s formulas recently proposed by Bernstein, De Feo, Leroux and Smith.",

keywords = "Isogeny-based cryptography, Post-quantum cryptography, Quantum cryptanalysis, [Constant time implementations], [Finite field arithmetic]",

author = "Jorge Ch{\'a}vez-Saab and Chi-Dom{\'i}nguez, {Jes{\'u}s Javier} and Samuel Jaques and Francisco Rodr{\'i}guez-Henr{\'i}quez",

note = "Funding Information: This project has received funding from the European Research Council (ERC) under the European Union{\textquoteright}s Horizon 2020 research and innovation programme (grant agreement No 804476). S. Jaques was supported by the University of Oxford Clarendon fund. Publisher Copyright: {\textcopyright} 2021, The Author(s).",

year = "2022",

doi = "10.1007/s13389-021-00271-w",

language = "English",

volume = "12",

journal = "JOURNAL OF CRYPTOGRAPHIC ENGINEERING",

issn = "2190-8508",

publisher = "Springer Verlag",

number = "3",

}

TY - JOUR

T1 - The SQALE of CSIDH

T2 - sublinear Vélu quantum-resistant isogeny action with low exponents

AU - Chávez-Saab, Jorge

AU - Chi-Domínguez, Jesús Javier

AU - Jaques, Samuel

AU - Rodríguez-Henríquez, Francisco

N1 - Funding Information: This project has received funding from the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (grant agreement No 804476). S. Jaques was supported by the University of Oxford Clarendon fund. Publisher Copyright: © 2021, The Author(s).

PY - 2022

Y1 - 2022

N2 - Recent independent analyses by Bonnetain–Schrottenloher and Peikert in Eurocrypt 2020 significantly reduced the estimated quantum security of the isogeny-based commutative group action key-exchange protocol CSIDH. This paper refines the estimates of a resource-constrained quantum collimation sieve attack to give a precise quantum security to CSIDH. Furthermore, we optimize large CSIDH parameters for performance while still achieving the NIST security levels 1, 2, and 3. Finally, we provide a C-code constant-time implementation of those CSIDH large instantiations using the square-root-complexity Vélu’s formulas recently proposed by Bernstein, De Feo, Leroux and Smith.

AB - Recent independent analyses by Bonnetain–Schrottenloher and Peikert in Eurocrypt 2020 significantly reduced the estimated quantum security of the isogeny-based commutative group action key-exchange protocol CSIDH. This paper refines the estimates of a resource-constrained quantum collimation sieve attack to give a precise quantum security to CSIDH. Furthermore, we optimize large CSIDH parameters for performance while still achieving the NIST security levels 1, 2, and 3. Finally, we provide a C-code constant-time implementation of those CSIDH large instantiations using the square-root-complexity Vélu’s formulas recently proposed by Bernstein, De Feo, Leroux and Smith.

KW - Isogeny-based cryptography

KW - Post-quantum cryptography

KW - Quantum cryptanalysis

KW - [Constant time implementations]

KW - [Finite field arithmetic]

U2 - 10.1007/s13389-021-00271-w

DO - 10.1007/s13389-021-00271-w

M3 - Article

AN - SCOPUS:85113965282

SN - 2190-8508

VL - 12

JO - JOURNAL OF CRYPTOGRAPHIC ENGINEERING

JF - JOURNAL OF CRYPTOGRAPHIC ENGINEERING

IS - 3

ER -

The SQALE of CSIDH: sublinear Vélu quantum-resistant isogeny action with low exponents

Abstract

Keywords

Publication forum classification

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this