• home
• blog
• research
• bounties
• team
• events

Legendre PRF algorithmic Bounties

The Legendre PRF

The Legendre pseudo-random function is a one-bit PRF $\mathbb{F}_p \rightarrow \{0,1\}$ defined using the Legendre symbol:

$\displaystyle L\_{p, K}(x) = \left\lceil\frac{1}{2}\left( \left(\frac{K + x}{p}\right) + 1\right)\right\rceil$

Bounties

$20,000 For either • a sub-exponential, i.e. $2^{(\log p)^c}$ for some $0, classical key recovery algorithm that extracts the key $K$ using inputs chosen by the attacker1 • a security proof which reduces the Legendre pseudo-random function distinguishing problem to a well-known 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 polylog2 factor, using a sub-exponential, i.e. $M=2^{(\log p)^c}$ for $0 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 factor2, using a sub-exponential, 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 well-established 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
• Phi-hiding assumption
• Discrete logarithm, Diffie-Hellman and Decisional Diffie-Hellman 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 64--148 (security levels 24--1084), the following bounties are now available for recovering a Legendre key:

Prime sizeSecurityPrizeStatus
64 bits24 bits1 ETHCLAIMED
74 bits34 bits2 ETHCLAIMED
84 bits44 bits4 ETHCLAIMED
100 bits60 bits8 ETH
148 bits108 bits16 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.

Footnotes

1. In all cases, probabilistic algorithms are also considered if they improve on the probabilistic versions of the known algorithms. Only classical (non-quantum) algorithms are permitted for the algorithm bounties. 2

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

3. 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$

4. This was originally set as 44--128 bits of security, but has been reduced to 24--108 due to the Beullens algorithm.

cryptography@ethereum.org