Cryptanalysis of an oblivious PRF from supersingular isogenies

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 languageEnglish
Title of host publicationAdvances in Cryptology – ASIACRYPT 2021
Subtitle of host publication27th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings, Part 1
EditorsMehdi Tibouchi, Huaxiong Wang
PublisherSpringer
Pages160-184
Number of pages25
Edition1
ISBN (Electronic)9783030920623
ISBN (Print)9783030920616
DOIs
Publication statusPublished - 1 Dec 2021
Event27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021 - Virtual, Online
Duration: 6 Dec 202110 Dec 2021

Publication series

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

Conference

Conference27th International Conference on Theory and Application of Cryptology and Information Security, ASIACRYPT 2021
CityVirtual, Online
Period6/12/2110/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
  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Cryptanalysis of an oblivious PRF from supersingular isogenies'. Together they form a unique fingerprint.

Cite this