CSIDH: An efficient post-quantum commutative group action

Wouter Castryck; Tanja Lange; Chloe Martindale; Lorenz Panny; Joost Renes

doi:10.1007/978-3-030-03332-3_15

CSIDH: An efficient post-quantum commutative group action

Wouter Castryck, Tanja Lange, Chloe Martindale, Lorenz Panny, Joost Renes

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

259 Citations (Scopus)

Abstract

We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field F_p, rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST’s post-quantum security category I.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
Editors	Thomas Peyrin, Steven Galbraith
Place of Publication	Berlin
Publisher	Springer
Pages	395-427
Number of pages	33
ISBN (Print)	9783030033316
DOIs	https://doi.org/10.1007/978-3-030-03332-3_15
Publication status	Published - 1 Jan 2018
Event	24th ternational Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2018 - Brisbane, Australia Duration: 2 Dec 2018 → 6 Dec 2018 Conference number: 24 https://asiacrypt.iacr.org/2018/

Publication series

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

Conference

Conference	24th ternational Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2018
Abbreviated title	ASIACRYPT 2018
Country/Territory	Australia
City	Brisbane
Period	2/12/18 → 6/12/18
Internet address	https://asiacrypt.iacr.org/2018/

Funding

Author list in alphabetical order; See https://www.ams.org/profession/leaders/ culture/CultureStatement04.pdf. This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 643161 (ECRYPT-NET), 645622 (PQCRYPTO), 645421 (ECRYPT-CSA), and CHIST-ERA USEIT (NWO project 651.002.004); the Technology Foundation STW (project 13499 – TYPHOON) from the Dutch government; and the Research Foundation - Flanders (FWO) through the WOG Coding Theory and Cryptography. The first listed author is affiliated on a free basis with the Department of Mathematics, Ghent University. Date of this document: 2018.09.07. Acknowledgements. This project started during a research retreat on post-quantum cryptography, organized by the European PQCRYPTO and ECRYPT-CSA projects in Tenerife from 29 January until 1 February 2018. We would like to thank Jeffrey Burdges, whose quest for a flexible post-quantum key exchange protocol made us look for speed-ups of the Couveignes–Rostovtsev–Stolbunov scheme. We are grateful to Luca De Feo, Jean Kieffer, and Ben Smith for sharing a draft of their paper in preparation, and to Daniel J. Bernstein, Luca De Feo, Jeroen Demeyer, Léo Ducas, Steven Galbraith, David Jao, and Fré Vercauteren for helpful feedback.

Keywords

Class-group action
Isogeny-based cryptography
Key confirmation
Non-interactive key exchange
Post-quantum cryptography

Access to Document

10.1007/978-3-030-03332-3_15

Cite this

Castryck, W., Lange, T., Martindale, C., Panny, L., & Renes, J. (2018). CSIDH: An efficient post-quantum commutative group action. In T. Peyrin, & S. Galbraith (Eds.), Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (pp. 395-427). (Lecture Notes in Computer Science; Vol. 11274). Springer. https://doi.org/10.1007/978-3-030-03332-3_15

Castryck, Wouter ; Lange, Tanja ; Martindale, Chloe et al. / CSIDH : An efficient post-quantum commutative group action. Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. editor / Thomas Peyrin ; Steven Galbraith. Berlin : Springer, 2018. pp. 395-427 (Lecture Notes in Computer Science).

@inproceedings{24dbb7c06ba14ecf815025cd803113ec,

title = "CSIDH: An efficient post-quantum commutative group action",

abstract = "We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field Fp, rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST{\textquoteright}s post-quantum security category I.",

keywords = "Class-group action, Isogeny-based cryptography, Key confirmation, Non-interactive key exchange, Post-quantum cryptography",

author = "Wouter Castryck and Tanja Lange and Chloe Martindale and Lorenz Panny and Joost Renes",

year = "2018",

month = jan,

day = "1",

doi = "10.1007/978-3-030-03332-3\_15",

language = "English",

isbn = "9783030033316",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "395--427",

editor = "Thomas Peyrin and Steven Galbraith",

booktitle = "Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings",

address = "Germany",

note = "24th ternational Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2018, ASIACRYPT 2018 ; Conference date: 02-12-2018 Through 06-12-2018",

url = "https://asiacrypt.iacr.org/2018/",

}

Castryck, W, Lange, T, Martindale, C, Panny, L & Renes, J 2018, CSIDH: An efficient post-quantum commutative group action. in T Peyrin & S Galbraith (eds), Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Lecture Notes in Computer Science, vol. 11274, Springer, Berlin, pp. 395-427, 24th ternational Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2018, Brisbane, Australia, 2/12/18. https://doi.org/10.1007/978-3-030-03332-3_15

CSIDH: An efficient post-quantum commutative group action. / Castryck, Wouter; Lange, Tanja; Martindale, Chloe et al.
Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. ed. / Thomas Peyrin; Steven Galbraith. Berlin: Springer, 2018. p. 395-427 (Lecture Notes in Computer Science; Vol. 11274).

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

TY - GEN

T1 - CSIDH

T2 - 24th ternational Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2018

AU - Castryck, Wouter

AU - Lange, Tanja

AU - Martindale, Chloe

AU - Panny, Lorenz

AU - Renes, Joost

N1 - Conference code: 24

PY - 2018/1/1

Y1 - 2018/1/1

N2 - We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field Fp, rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST’s post-quantum security category I.

AB - We propose an efficient commutative group action suitable for non-interactive key exchange in a post-quantum setting. Our construction follows the layout of the Couveignes–Rostovtsev–Stolbunov cryptosystem, but we apply it to supersingular elliptic curves defined over a large prime field Fp, rather than to ordinary elliptic curves. The Diffie–Hellman scheme resulting from the group action allows for public-key validation at very little cost, runs reasonably fast in practice, and has public keys of only 64 bytes at a conjectured AES-128 security level, matching NIST’s post-quantum security category I.

KW - Class-group action

KW - Isogeny-based cryptography

KW - Key confirmation

KW - Non-interactive key exchange

KW - Post-quantum cryptography

UR - http://www.scopus.com/inward/record.url?scp=85057601063&partnerID=8YFLogxK

U2 - 10.1007/978-3-030-03332-3_15

DO - 10.1007/978-3-030-03332-3_15

M3 - Conference contribution

AN - SCOPUS:85057601063

SN - 9783030033316

T3 - Lecture Notes in Computer Science

SP - 395

EP - 427

BT - Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings

A2 - Peyrin, Thomas

A2 - Galbraith, Steven

PB - Springer

CY - Berlin

Y2 - 2 December 2018 through 6 December 2018

ER -

Castryck W, Lange T, Martindale C, Panny L, Renes J. CSIDH: An efficient post-quantum commutative group action. In Peyrin T, Galbraith S, editors, Advances in Cryptology – ASIACRYPT 2018 - 24th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings. Berlin: Springer. 2018. p. 395-427. (Lecture Notes in Computer Science). doi: 10.1007/978-3-030-03332-3_15

CSIDH: An efficient post-quantum commutative group action

Abstract

Publication series

Conference

Funding

Keywords

Access to Document

Other files and links

Fingerprint

CSIDH: an efficient Post-Quantum Commutative Group Action

Cite this