### Cryptanalysis of the Legendre PRF and generalizations

Ward Beullens, Tim Beyne, Aleksei Udovenko, and Giuseppe Vitto

##### Abstract

The Legendre PRF relies on the conjectured pseudorandomness properties of the Legendre symbol with a hidden shift. Originally proposed as a PRG by Damgård at CRYPTO 1988, it was recently suggested as an efficient PRF for multiparty computation purposes by Grassi et al. at CCS 2016. Moreover, the Legendre PRF is being considered for usage in the Ethereum 2.0 blockchain. This paper improves previous attacks on the Legendre PRF and its higher-degree variant due to Khovratovich by reducing the time complexity from $O(p\log{p}/M)$ to $O(p\log^2{p}/M^2)$ Legendre symbol evaluations when $M \le \sqrt[4]{p \log^2 p}$ queries are available. The practical relevance of our improved attack is demonstrated by breaking three concrete instances of the PRF proposed by the Ethereum foundation. Furthermore, we generalize our attack in a nontrivial way to the higher-degree variant of the Legendre PRF and we point out a large class of weak keys for this construction. Lastly, we provide the first security analysis of two additional generalizations of the Legendre PRF originally proposed by Damgård in the PRG setting, namely the Jacobi PRF and the power residue PRF.

Note: Add DOI of the published version, minor fixes in complexity estimations.

Available format(s)
Category
Secret-key cryptography
Publication info
A minor revision of an IACR publication in FSE 2020
DOI
10.13154/tosc.v2020.i1.313-330
Keywords
CryptanalysisLegendre PRFMPC-friendly primitivesCollision attack
Contact author(s)
ward beullens @ esat kuleuven be
tim beyne @ esat kuleuven be
giuseppe vitto @ uni lu
aleksei @ affine group
History
2020-10-30: last of 3 revisions
See all versions
Short URL
https://ia.cr/2019/1357

CC BY

BibTeX

@misc{cryptoeprint:2019/1357,
author = {Ward Beullens and Tim Beyne and Aleksei Udovenko and Giuseppe Vitto},
title = {Cryptanalysis of the Legendre PRF and generalizations},
howpublished = {Cryptology ePrint Archive, Paper 2019/1357},
year = {2019},
doi = {10.13154/tosc.v2020.i1.313-330},
note = {\url{https://eprint.iacr.org/2019/1357}},
url = {https://eprint.iacr.org/2019/1357}
}

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