A Note on Isogeny Group Action-Based Pseudorandom Functions

Yi-Fu Lai

Paper 2024/2042

A Note on Isogeny Group Action-Based Pseudorandom Functions

Yi-Fu Lai

, Ruhr University Bochum

Abstract

In PKC'24, de Saint Guilhem and Pedersen give a pseudorandom function basing on a relaxed group action assumption in the semi-honest setting. Basing on the assumption, they build an oblivious pseudorandom function (OPRF). Later, a recent paper by Levin and Pedersen uses the same function to build a verifiable random function (VRF), using the same assumption. We give a structural attack on this problem by reducing it to a few group action inverse problems (GAIP/DLog) over small subgroups. This reduction allows us to apply a CRT-based attack to recover the secret key, ultimately lowering the problem’s effective security strength to under 70 classical bits when using CSIDH-512. Hence the strength of their pseudorandom functions is bounded above by the GAIP over the largest prime order subgroup. Clearly, Kuperberg’s subexponential attack can be used to further reduce its quantum security.

Metadata

Available format(s): PDF
Category: Attacks and cryptanalysis
Publication info: Preprint.
Keywords: Group action isogeny cryptography VRF post-quantum cryptography
Contact author(s): Yi-Fu Lai @ rub de
History: 2024-12-18: approved; 2024-12-18: received; See all versions
Short URL: https://ia.cr/2024/2042
License: CC BY

BibTeX

@misc{cryptoeprint:2024/2042,
      author = {Yi-Fu Lai},
      title = {A Note on Isogeny Group Action-Based Pseudorandom Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/2042},
      year = {2024},
      url = {https://eprint.iacr.org/2024/2042}
}