Legendre PRF bounties
The Legendre PRF
The Legendre pseudorandom function is a onebit PRF defined using the Legendre symbol:
Bounties
$ 10,000
For either
 a subexponential, i.e. , classical key recovery algorithm that extracts the key using inputs chosen by the attacker^{1}
 a security proof showing the nonexistence of such an algorithm by reducing it to a wellestablished computational hardness assumption (see below)
$ 3,000
For a classical key recovery algorithm improving on the Khovratovich ( where is the number of PRF queries needed) algorithm, using a subexponential, i.e. number of queries.^{1} ^{2}
$ 1,000
For the most interesting paper on the Legendre PRF in the next year (ends 31 August 2020)^{3}
Fhe first bounties are for the first entry that beats the given bounds. Please send submissions to Dankrad Feist dankrad .at. ethereum .dot. org.
Computational hardness assumptions
For the reduction to a wellestablished computational hardness assumption, we consider the assumptions below which are taken from the Wikipedia page
 Integer factorization problem
 RSA problem
 Quadratic residuosity, higher residuosity and decisional composite residuosity problem
 Phihiding assumption
 Discrete logarithm, DiffieHellman and Decisional DiffieHellman in
 Lattice problems: Shortest vector and learning with errors
Concrete instances
TBA: Some bounties for key recovery in concrete instances will be announced soon, stay tuned.
Research papers
 Damgård, Ivan Bjerre: On The Randomness of Legendre and Jacobi Sequences (1988)
 Lorenzo Grassi, Christian Rechberger, Dragos Rotaru, Peter Scholl, Nigel P. Smart: MPCFriendly Symmetric Key Primitives (2016)
 Alexander Russell, Igor Shparlinski: Classical and Quantum Polynomial Reconstruction via Legendre Symbol Evaluation (2002)
 Dmitry Khovratovich: Key recovery attacks on the Legendre PRFs within the birthday bound

In all cases, probabilistic algorithms are also considered if they improve on the probabilistic versions of the known algorithms. Only classical (nonquantum) algorithms are permitted for the algorithm bounties. ↩ ↩^{2}

For this bounty, we also consider any algorithm that can distinguish a bit length output of the Legendre PRF from a random bit string with advantage ↩

A cryptographer will be appointed by the Ethereum Foundation to judge this (TBD) ↩