Reference : Cryptanalysis of the Legendre PRF and generalizations
Scientific journals : Article
Engineering, computing & technology : Computer science
Security, Reliability and Trust
Cryptanalysis of the Legendre PRF and generalizations
Beullens, Ward [> >]
Beyne, Tim [> >]
Udovenko, Aleksei mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) >]
Vitto, Giuseppe mailto [University of Luxembourg > Interdisciplinary Centre for Security, Reliability and Trust (SNT) >]
IACR Transactions on Symmetric Cryptology
[en] Cryptanalysis ; Legendre PRF ; MPC-friendly ; primitives ; Collision attack
[en] 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(plogp/M) to O(plog^2p/M2) Legendre symbol evaluations when M≤p√4 queries are available. The practical relevance of our improved attack is demonstrated by breaking two 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.
University of Luxembourg: High Performance Computing - ULHPC
Fonds National de la Recherche - FnR
Researchers ; Professionals ; Students
FnR ; FNR11684537 > Alex Biryukov > FinCrypt > Security, Scalability, and Privacy in Blockchain Applications and Smart Contracts > 01/08/2018 > 31/07/2021 > 2017

File(s) associated to this reference

Fulltext file(s):

Open access
legendrePRF.pdfPublisher postprint505.25 kBView/Open

Bookmark and Share SFX Query

All documents in ORBilu are protected by a user license.