Séta: supersingular encryption from torsion attacks

Luca De Feo; Cyprien Delpech de Saint Guilhem; Tako Boris Fouotsa; Péter Kutas; Antonin Leroux; Christophe Petit; Javier Silva; Benjamin Wesolowski

doi:10.1007/978-3-030-92068-5_9

Séta: supersingular encryption from torsion attacks

Luca De Feo^*, Cyprien Delpech de Saint Guilhem, Tako Boris Fouotsa, Péter Kutas, Antonin Leroux, Christophe Petit, Javier Silva, Benjamin Wesolowski

^*Corresponding author for this work

Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

58 Downloads (Pure)

Abstract

We present Séta (To be pronounced [ʃe:tɒ] meaning “walk” in Hungarian.), a new family of public-key encryption schemes with post-quantum security based on isogenies of supersingular elliptic curves. It is constructed from a new family of trapdoor one-way functions, where the inversion algorithm uses Petit’s so called torsion attacks on SIDH to compute an isogeny between supersingular elliptic curves given an endomorphism of the starting curve and images of torsion points. We prove the OW-CPA security of Séta and present an IND-CCA variant using the post-quantum OAEP transformation. Several variants for key generation are explored together with their impact on the selection of parameters, such as the base prime of the scheme. We furthermore formalise an “uber” isogeny assumption framework which aims to generalize computational isogeny problems encountered in schemes including SIDH, CSDIH, OSIDH and ours. Finally, we carefully select parameters to achieve a balance between security and run-times and present experimental results from our implementation.

Original language	English
Title of host publication	Advances in Cryptology – ASIACRYPT 2021
Subtitle of host publication	27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4
Editors	Mehdi Tibouchi, Huaxiong Wang
Publisher	Springer
Pages	249-278
Number of pages	30
Edition	1
ISBN (Electronic)	9783030920685
ISBN (Print)	9783030920678
DOIs	https://doi.org/10.1007/978-3-030-92068-5_9
Publication status	Published - 1 Dec 2021
Event	27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021 - Virtual, Online Duration: 6 Dec 2021 → 10 Dec 2021

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	13093 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
City	Virtual, Online
Period	6/12/21 → 10/12/21

Bibliographical note

Funding Information:
Acknowledgments. We would like to thank the anonymous reviewers for their remarks and suggestions. Péter Kutas and Christophe Petit’s work was supported by EPSRC grant EP/S01361X/1. Péter Kutas was also supported by the Ministry of Innovation and Technology and the National Research, Development and Innovation Office within the Quantum Information National Laboratory of Hungary. Cyprien Delpech de Saint Guilhem’s work was supported by ERC Advanced Grant ERC-2015-AdG-IMPaCT, by DARPA under contract No. HR001120C0085, and by CyberSecurity Research Flanders with reference number VR20192203.

Publisher Copyright:
© 2021, International Association for Cryptologic Research.

Keywords

public-key cryptography
elliptic curves
isogenies
Encryption

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-92068-5_9

DeL2021Séta
This version of the contribution has been accepted for publication, after peer review (when applicable) but is not the Version of Record and does not reflect post-acceptance improvements, or any corrections. The Version of Record is available online at: http://dx.doi.org/10.1007/978-3-030-92068-5_9. Use of this Accepted Version is subject to the publisher’s Accepted Manuscript terms of use https://www.springernature.com/gp/open-research/policies/accepted-manuscript-terms
Accepted author manuscript, 453 KBLicence: Other (please specify with Rights Statement)

https://eprint.iacr.org/2019/1291.pdf

Cite this

De Feo, L., Delpech de Saint Guilhem, C., Fouotsa, T. B., Kutas, P., Leroux, A., Petit, C., Silva, J., & Wesolowski, B. (2021). Séta: supersingular encryption from torsion attacks. In M. Tibouchi, & H. Wang (Eds.), Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4 (1 ed., pp. 249-278). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13093 LNCS). Springer. https://doi.org/10.1007/978-3-030-92068-5_9

De Feo, Luca ; Delpech de Saint Guilhem, Cyprien ; Fouotsa, Tako Boris et al. / Séta : supersingular encryption from torsion attacks. Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4. editor / Mehdi Tibouchi ; Huaxiong Wang. 1. ed. Springer, 2021. pp. 249-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{a841ed2323a143b387dd249ae9e77e7b,

title = "S{\'e}ta: supersingular encryption from torsion attacks",

abstract = "We present S{\'e}ta (To be pronounced [ʃe:tɒ] meaning “walk” in Hungarian.), a new family of public-key encryption schemes with post-quantum security based on isogenies of supersingular elliptic curves. It is constructed from a new family of trapdoor one-way functions, where the inversion algorithm uses Petit{\textquoteright}s so called torsion attacks on SIDH to compute an isogeny between supersingular elliptic curves given an endomorphism of the starting curve and images of torsion points. We prove the OW-CPA security of S{\'e}ta and present an IND-CCA variant using the post-quantum OAEP transformation. Several variants for key generation are explored together with their impact on the selection of parameters, such as the base prime of the scheme. We furthermore formalise an “uber” isogeny assumption framework which aims to generalize computational isogeny problems encountered in schemes including SIDH, CSDIH, OSIDH and ours. Finally, we carefully select parameters to achieve a balance between security and run-times and present experimental results from our implementation.",

keywords = "public-key cryptography, elliptic curves, isogenies, Encryption",

author = "{De Feo}, Luca and {Delpech de Saint Guilhem}, Cyprien and Fouotsa, {Tako Boris} and P{\'e}ter Kutas and Antonin Leroux and Christophe Petit and Javier Silva and Benjamin Wesolowski",

note = "Funding Information: Acknowledgments. We would like to thank the anonymous reviewers for their remarks and suggestions. P{\'e}ter Kutas and Christophe Petit{\textquoteright}s work was supported by EPSRC grant EP/S01361X/1. P{\'e}ter Kutas was also supported by the Ministry of Innovation and Technology and the National Research, Development and Innovation Office within the Quantum Information National Laboratory of Hungary. Cyprien Delpech de Saint Guilhem{\textquoteright}s work was supported by ERC Advanced Grant ERC-2015-AdG-IMPaCT, by DARPA under contract No. HR001120C0085, and by CyberSecurity Research Flanders with reference number VR20192203. Publisher Copyright: {\textcopyright} 2021, International Association for Cryptologic Research.; 27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021 ; Conference date: 06-12-2021 Through 10-12-2021",

year = "2021",

month = dec,

day = "1",

doi = "10.1007/978-3-030-92068-5_9",

language = "English",

isbn = "9783030920678",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "249--278",

editor = "Mehdi Tibouchi and Huaxiong Wang",

booktitle = "Advances in Cryptology – ASIACRYPT 2021",

edition = "1",

}

De Feo, L, Delpech de Saint Guilhem, C, Fouotsa, TB, Kutas, P, Leroux, A, Petit, C, Silva, J & Wesolowski, B 2021, Séta: supersingular encryption from torsion attacks. in M Tibouchi & H Wang (eds), Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4. 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13093 LNCS, Springer, pp. 249-278, 27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021, Virtual, Online, 6/12/21. https://doi.org/10.1007/978-3-030-92068-5_9

Séta: supersingular encryption from torsion attacks. / De Feo, Luca; Delpech de Saint Guilhem, Cyprien; Fouotsa, Tako Boris et al.
Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4. ed. / Mehdi Tibouchi; Huaxiong Wang. 1. ed. Springer, 2021. p. 249-278 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13093 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Séta

T2 - 27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021

AU - De Feo, Luca

AU - Delpech de Saint Guilhem, Cyprien

AU - Fouotsa, Tako Boris

AU - Kutas, Péter

AU - Leroux, Antonin

AU - Petit, Christophe

AU - Silva, Javier

AU - Wesolowski, Benjamin

N1 - Funding Information: Acknowledgments. We would like to thank the anonymous reviewers for their remarks and suggestions. Péter Kutas and Christophe Petit’s work was supported by EPSRC grant EP/S01361X/1. Péter Kutas was also supported by the Ministry of Innovation and Technology and the National Research, Development and Innovation Office within the Quantum Information National Laboratory of Hungary. Cyprien Delpech de Saint Guilhem’s work was supported by ERC Advanced Grant ERC-2015-AdG-IMPaCT, by DARPA under contract No. HR001120C0085, and by CyberSecurity Research Flanders with reference number VR20192203. Publisher Copyright: © 2021, International Association for Cryptologic Research.

PY - 2021/12/1

Y1 - 2021/12/1

N2 - We present Séta (To be pronounced [ʃe:tɒ] meaning “walk” in Hungarian.), a new family of public-key encryption schemes with post-quantum security based on isogenies of supersingular elliptic curves. It is constructed from a new family of trapdoor one-way functions, where the inversion algorithm uses Petit’s so called torsion attacks on SIDH to compute an isogeny between supersingular elliptic curves given an endomorphism of the starting curve and images of torsion points. We prove the OW-CPA security of Séta and present an IND-CCA variant using the post-quantum OAEP transformation. Several variants for key generation are explored together with their impact on the selection of parameters, such as the base prime of the scheme. We furthermore formalise an “uber” isogeny assumption framework which aims to generalize computational isogeny problems encountered in schemes including SIDH, CSDIH, OSIDH and ours. Finally, we carefully select parameters to achieve a balance between security and run-times and present experimental results from our implementation.

AB - We present Séta (To be pronounced [ʃe:tɒ] meaning “walk” in Hungarian.), a new family of public-key encryption schemes with post-quantum security based on isogenies of supersingular elliptic curves. It is constructed from a new family of trapdoor one-way functions, where the inversion algorithm uses Petit’s so called torsion attacks on SIDH to compute an isogeny between supersingular elliptic curves given an endomorphism of the starting curve and images of torsion points. We prove the OW-CPA security of Séta and present an IND-CCA variant using the post-quantum OAEP transformation. Several variants for key generation are explored together with their impact on the selection of parameters, such as the base prime of the scheme. We furthermore formalise an “uber” isogeny assumption framework which aims to generalize computational isogeny problems encountered in schemes including SIDH, CSDIH, OSIDH and ours. Finally, we carefully select parameters to achieve a balance between security and run-times and present experimental results from our implementation.

KW - public-key cryptography

KW - elliptic curves

KW - isogenies

KW - Encryption

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

U2 - 10.1007/978-3-030-92068-5_9

DO - 10.1007/978-3-030-92068-5_9

M3 - Conference contribution

AN - SCOPUS:85121911129

SN - 9783030920678

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 249

EP - 278

BT - Advances in Cryptology – ASIACRYPT 2021

A2 - Tibouchi, Mehdi

A2 - Wang, Huaxiong

PB - Springer

Y2 - 6 December 2021 through 10 December 2021

ER -

De Feo L, Delpech de Saint Guilhem C, Fouotsa TB, Kutas P, Leroux A, Petit C et al. Séta: supersingular encryption from torsion attacks. In Tibouchi M, Wang H, editors, Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, 2021, Proceedings, Part 4. 1 ed. Springer. 2021. p. 249-278. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-92068-5_9