Cryptanalysis of an oblivious PRF from supersingular isogenies

Andrea Basso; Péter Kutas; Simon Philipp Merz; Christophe Petit; Antonio Sanso

doi:10.1007/978-3-030-92062-3_6

Cryptanalysis of an oblivious PRF from supersingular isogenies

Andrea Basso^*, Péter Kutas, Simon Philipp Merz, Christophe Petit, Antonio Sanso

^*Corresponding author for this work

Computer Science

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

30 Downloads (Pure)

Abstract

We cryptanalyse the SIDH-based oblivious pseudorandom function from supersingular isogenies proposed at Asiacrypt’20 by Boneh, Kogan and Woo. To this end, we give an attack on an assumption, the auxiliary one-more assumption, that was introduced by Boneh et al. and we show that this leads to an attack on the oblivious PRF itself. The attack breaks the pseudorandomness as it allows adversaries to evaluate the OPRF without further interactions with the server after some initial OPRF evaluations and some offline computations. More specifically, we first propose a polynomial-time attack. Then, we argue it is easy to change the OPRF protocol to include some countermeasures, and present a second subexponential attack that succeeds in the presence of said countermeasures. Both attacks break the security parameters suggested by Boneh et al. Furthermore, we provide a proof of concept implementation as well as some timings of our attack. Finally, we examine the generation of one of the OPRF parameters and argue that a trusted third party is needed to guarantee provable security.

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, Proceedings, Part 1
Editors	Mehdi Tibouchi, Huaxiong Wang
Publisher	Springer
Pages	160-184
Number of pages	25
Edition	1
ISBN (Electronic)	9783030920623
ISBN (Print)	9783030920616
DOIs	https://doi.org/10.1007/978-3-030-92062-3_6
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	13090 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 Dan Boneh, Jesús Javier Chi Domínguez, Luca De Feo, Enric Florit, Dmitry Kogan and Simon Masson for fruitful discussions. Péter Kutas, Simon-Philipp Merz and Christophe Petit were supported by EPSRC and the UK government as part of the grant EP/S01361X/1 for Péter Kutas and Christophe Petit and the grant EP/P009301/1 for Simon-Philipp Merz. Further, Péter Kutas was supported by the Ministry of Innovation and Technology and the National Research, Development and Innovation Office within the Quantum Information National Laboratory of Hungary.

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

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Access to Document

10.1007/978-3-030-92062-3_6

BassoA2021Cryptanalysis
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-92062-3_6. 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, 480 KBLicence: Other (please specify with Rights Statement)

Cite this

Basso, A., Kutas, P., Merz, S. P., Petit, C., & Sanso, A. (2021). Cryptanalysis of an oblivious PRF from supersingular isogenies. In M. Tibouchi, & H. Wang (Eds.), Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 1 (1 ed., pp. 160-184). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13090 LNCS). Springer. https://doi.org/10.1007/978-3-030-92062-3_6

Basso, Andrea ; Kutas, Péter ; Merz, Simon Philipp et al. / Cryptanalysis of an oblivious PRF from supersingular isogenies. Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 1. editor / Mehdi Tibouchi ; Huaxiong Wang. 1. ed. Springer, 2021. pp. 160-184 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{736b4791709d4839a03b700bc64e96f8,

title = "Cryptanalysis of an oblivious PRF from supersingular isogenies",

abstract = "We cryptanalyse the SIDH-based oblivious pseudorandom function from supersingular isogenies proposed at Asiacrypt{\textquoteright}20 by Boneh, Kogan and Woo. To this end, we give an attack on an assumption, the auxiliary one-more assumption, that was introduced by Boneh et al. and we show that this leads to an attack on the oblivious PRF itself. The attack breaks the pseudorandomness as it allows adversaries to evaluate the OPRF without further interactions with the server after some initial OPRF evaluations and some offline computations. More specifically, we first propose a polynomial-time attack. Then, we argue it is easy to change the OPRF protocol to include some countermeasures, and present a second subexponential attack that succeeds in the presence of said countermeasures. Both attacks break the security parameters suggested by Boneh et al. Furthermore, we provide a proof of concept implementation as well as some timings of our attack. Finally, we examine the generation of one of the OPRF parameters and argue that a trusted third party is needed to guarantee provable security.",

author = "Andrea Basso and P{\'e}ter Kutas and Merz, {Simon Philipp} and Christophe Petit and Antonio Sanso",

note = "Funding Information: Acknowledgments. We would like to thank Dan Boneh, Jes{\'u}s Javier Chi Dom{\'i}nguez, Luca De Feo, Enric Florit, Dmitry Kogan and Simon Masson for fruitful discussions. P{\'e}ter Kutas, Simon-Philipp Merz and Christophe Petit were supported by EPSRC and the UK government as part of the grant EP/S01361X/1 for P{\'e}ter Kutas and Christophe Petit and the grant EP/P009301/1 for Simon-Philipp Merz. Further, P{\'e}ter Kutas was supported by the Ministry of Innovation and Technology and the National Research, Development and Innovation Office within the Quantum Information National Laboratory of Hungary. 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-92062-3_6",

language = "English",

isbn = "9783030920616",

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

publisher = "Springer",

pages = "160--184",

editor = "Mehdi Tibouchi and Huaxiong Wang",

booktitle = "Advances in Cryptology – ASIACRYPT 2021",

edition = "1",

}

Basso, A, Kutas, P, Merz, SP, Petit, C & Sanso, A 2021, Cryptanalysis of an oblivious PRF from supersingular isogenies. in M Tibouchi & H Wang (eds), Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 1. 1 edn, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 13090 LNCS, Springer, pp. 160-184, 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-92062-3_6

Cryptanalysis of an oblivious PRF from supersingular isogenies. / Basso, Andrea; Kutas, Péter; Merz, Simon Philipp et al.
Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 1. ed. / Mehdi Tibouchi; Huaxiong Wang. 1. ed. Springer, 2021. p. 160-184 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 13090 LNCS).

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

TY - GEN

T1 - Cryptanalysis of an oblivious PRF from supersingular isogenies

AU - Basso, Andrea

AU - Kutas, Péter

AU - Merz, Simon Philipp

AU - Petit, Christophe

AU - Sanso, Antonio

N1 - Funding Information: Acknowledgments. We would like to thank Dan Boneh, Jesús Javier Chi Domínguez, Luca De Feo, Enric Florit, Dmitry Kogan and Simon Masson for fruitful discussions. Péter Kutas, Simon-Philipp Merz and Christophe Petit were supported by EPSRC and the UK government as part of the grant EP/S01361X/1 for Péter Kutas and Christophe Petit and the grant EP/P009301/1 for Simon-Philipp Merz. Further, Péter Kutas was supported by the Ministry of Innovation and Technology and the National Research, Development and Innovation Office within the Quantum Information National Laboratory of Hungary. Publisher Copyright: © 2021, International Association for Cryptologic Research.

PY - 2021/12/1

Y1 - 2021/12/1

N2 - We cryptanalyse the SIDH-based oblivious pseudorandom function from supersingular isogenies proposed at Asiacrypt’20 by Boneh, Kogan and Woo. To this end, we give an attack on an assumption, the auxiliary one-more assumption, that was introduced by Boneh et al. and we show that this leads to an attack on the oblivious PRF itself. The attack breaks the pseudorandomness as it allows adversaries to evaluate the OPRF without further interactions with the server after some initial OPRF evaluations and some offline computations. More specifically, we first propose a polynomial-time attack. Then, we argue it is easy to change the OPRF protocol to include some countermeasures, and present a second subexponential attack that succeeds in the presence of said countermeasures. Both attacks break the security parameters suggested by Boneh et al. Furthermore, we provide a proof of concept implementation as well as some timings of our attack. Finally, we examine the generation of one of the OPRF parameters and argue that a trusted third party is needed to guarantee provable security.

AB - We cryptanalyse the SIDH-based oblivious pseudorandom function from supersingular isogenies proposed at Asiacrypt’20 by Boneh, Kogan and Woo. To this end, we give an attack on an assumption, the auxiliary one-more assumption, that was introduced by Boneh et al. and we show that this leads to an attack on the oblivious PRF itself. The attack breaks the pseudorandomness as it allows adversaries to evaluate the OPRF without further interactions with the server after some initial OPRF evaluations and some offline computations. More specifically, we first propose a polynomial-time attack. Then, we argue it is easy to change the OPRF protocol to include some countermeasures, and present a second subexponential attack that succeeds in the presence of said countermeasures. Both attacks break the security parameters suggested by Boneh et al. Furthermore, we provide a proof of concept implementation as well as some timings of our attack. Finally, we examine the generation of one of the OPRF parameters and argue that a trusted third party is needed to guarantee provable security.

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

U2 - 10.1007/978-3-030-92062-3_6

DO - 10.1007/978-3-030-92062-3_6

M3 - Conference contribution

AN - SCOPUS:85121916353

SN - 9783030920616

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

SP - 160

EP - 184

BT - Advances in Cryptology – ASIACRYPT 2021

A2 - Tibouchi, Mehdi

A2 - Wang, Huaxiong

PB - Springer

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

Y2 - 6 December 2021 through 10 December 2021

ER -

Basso A, Kutas P, Merz SP, Petit C, Sanso A. Cryptanalysis of an oblivious PRF from supersingular isogenies. In Tibouchi M, Wang H, editors, Advances in Cryptology – ASIACRYPT 2021: 27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 1. 1 ed. Springer. 2021. p. 160-184. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-92062-3_6

Cryptanalysis of an oblivious PRF from supersingular isogenies

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this