• 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