### Cryptanalysis of an oblivious PRF from supersingular isogenies

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

##### 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.

Note: Add results of our proof-of-concept implementation of the attack for the 67 bits instance

Available format(s)
Category
Cryptographic protocols
Publication info
Keywords
isogenyisogeniessidhoprfcryptanalysis
Contact author(s)
a basso @ cs bham ac uk
kutasp @ gmail com
simon-philipp merz 2018 @ live rhul ac uk
christophe f petit @ gmail com
antonio sanso @ gmail com
History
2021-12-11: last of 3 revisions
See all versions
Short URL
https://ia.cr/2021/706

CC BY

BibTeX

@misc{cryptoeprint:2021/706,
author = {Andrea Basso and Péter Kutas and Simon-Philipp Merz and Christophe Petit and Antonio Sanso},
title = {Cryptanalysis of an oblivious PRF from supersingular isogenies},
howpublished = {Cryptology ePrint Archive, Paper 2021/706},
year = {2021},
note = {\url{https://eprint.iacr.org/2021/706}},
url = {https://eprint.iacr.org/2021/706}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.