Legendre PRF algorithmic Bounties
The Legendre PRF
The Legendre pseudorandom function is a onebit PRF $\mathbb{F}_p \rightarrow \{0,1\}$ defined using the Legendre symbol:
Bounties
$ 20,000
For either
 a subexponential, i.e. $2^{(\log p)^c}$ for some $0<c<1$, classical key recovery algorithm that extracts the key $K$ using inputs chosen by the attacker^{.css1piu1ot{transitionproperty:var(chakratransitionpropertycommon);transitionduration:var(chakratransitiondurationfast);transitiontimingfunction:var(chakratransitioneasingeaseout);cursor:pointer;webkittextdecoration:none;textdecoration:none;outline:2px solid transparent;outlineoffset:2px;color:var(chakracolorsbrandlightblue);}.css1piu1ot:hover,.css1piu1ot[datahover]{color:var(chakracolorsbrandorange);webkittextdecoration:underline;textdecoration:underline;}.css1piu1ot:focus,.css1piu1ot[datafocus]{boxshadow:var(chakrashadowsoutline);}1}
 a security proof which reduces the Legendre pseudorandom function distinguishing problem to a wellknown computational hardness assumption (see below)
$ 6,000
For a classical key recovery algorithm improving on the algorithm by Kaluđerović, Kleinjung and Kostić ($O (p \log(p) \log(\log(p))/M^2)$ Legendre evaluations where $M$ is the number of PRF queries needed) algorithm by more than a polylog^{2} factor, using a subexponential, i.e. $M=2^{(\log p)^c}$ for $0<c<1$ number of queries.^{1} ^{3}
$ 3,000
For a classical PRF distinguishing algorithm against the Legendre PRF that has an error probability bounded away from $1/3$ and is faster than direct use of the Kaluđerović, Kleinjung, and Kostić key recovery attacks, by more than a polylog factor^{2}, using a subexponential, i.e. $M = 2^{(\log p )^c}$ for 0 < c < 1 number of queries.
The first two 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 $\mathbb{F}_p^{\times}$
 Lattice problems: Shortest vector and learning with errors
Concrete instances
At Devcon5, further bounties for concrete instances of the Legendre PRF were announced. For primes of size 64148 (security levels 24108^{4}), the following bounties are now available for recovering a Legendre key:
Prime size  Security  Prize  Status 

64 bits  24 bits  1 ETH  CLAIMED 
74 bits  34 bits  2 ETH  CLAIMED 
84 bits  44 bits  4 ETH  CLAIMED 
100 bits  60 bits  8 ETH  
148 bits  108 bits  16 ETH 
For each of the challenges, $2^{20}$ bits of output from the Legendre PRF are available here. To claim one of these bounties, you must find the correct key that generates the outputs.
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 (2019)
 Ward Beullens, Tim Beyne, Aleksei Udovenko, Giuseppe Vitto: Cryptanalysis of the Legendre PRF and generalizations (2019)
 Novak Kaluđerović, Thorsten Kleinjung and Dušan Kostić: Cryptanalysis of the generalised Legendre pseudorandom function (2020)
Footnotes

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}

An improvement $g(n)$ on a function $f(n)$ is by more than a polylog factor if $f(n)/g(n)=\Omega(\log^m(n))$ for all $m\in\mathbf{N}$. ↩ ↩^{2}

For this bounty, we also consider any algorithm that can distinguish a $2^{(\log p)^c}$ bit length output of the Legendre PRF from a random bit string with advantage $>0.1$ ↩

This was originally set as 44128 bits of security, but has been reduced to 24108 due to the Beullens algorithm. ↩