Legendre PRF 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

$ 10,000

  For either

• a sub-exponential, 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¹
• a security proof which reduces the Lgendre pseudo-random function distinguishing problem to a well-known computational hardness assumption (see below)

$ 3,000

  For a classical key recovery algorithm improving on the Beullens ($O (p \log^2(p) / M^2)$ Legendre evaluations where $M$ is the number of PRF queries needed) algorithm by more than a polylog² factor, using a sub-exponential, i.e. $M=2^{(\log p)^c}$ for $0<c<1$ number of queries.^{1 3}

$ 1,000

  For the most interesting paper on the Legendre PRF in the next year (ends 31 August 2020)⁴

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–108²), the following bounties are now available for recovering a Legendre key:

Prime size	Security	Prize
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: MPC-Friendly 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
• Ward Beullens, Tim Beyne, Aleksei Udovenko, Giuseppe Vitto: Cryptanalysis of the Legendre PRF and generalizations