Paper 2019/1357
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
Note: Add DOI of the published version, minor fixes in complexity estimations.
Metadata
- Available format(s)
-
PDF
- 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
- 2019-11-27: received
- See all versions
- Short URL
- https://ia.cr/2019/1357
- License
-
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}, url = {https://eprint.iacr.org/2019/1357} }