For bounties on breaking the Legendre PRF, please see bounties for algorithmic bounties and here for concrete key recovery puzzles.

# The Legendre PRF

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

There are also variants of Legendre PRF with a higher degree, which replaces $K+x$ above with a univariate polynomial $f_K(x)$ of degree two or more, where $K$ represents its coefficients.

## Suitability for MPC

Thanks to a result by Grassi et al. (2016), we know that this PRF can be evaluated very efficiently in arithmetic circuit multi-party computations (MPCs). Due to the multiplicative property of the Legendre symbol, a multiplication by a random square does not change the result of an evaluation. By additionally blinding with a random bit, the Legendre symbol can be evaluated using only three multiplications, two of which can be done offline (before the input is known).

To compute the Legendre symbol $\left[\left(\frac{x}{p}\right)\right]$ for an input $[x]$ (square brackets indicate a shared value):

1. Choose a quadratic non-residue $\alpha$

2. Pre-compute a random square $[s^2]$ and a random bit $[b]$

3. Open the value $t \leftarrow \mathrm{Open}([x] [s^2]([b] + (1- [b]) \alpha) )$

4. Compute $u = \left(\frac{t}{p}\right)$ on the open value $t$

5. The result of the computation is $y = u (2 [b] -1 )$

## Suitability for ZKP

Similarly, the evaluation of this PRF can be proved efficiently in ZKP over $\mathbb{F}_{p}$. Let $n$ be any quadratic nonresidue in $\mathbb{F}_{p}$. To validate $L_{p, K}(x) = b$ for $x, b \in \mathbb{F}_p$:

1. Prove in ZKP that $b\cdot (1 - b) = 0$

2. For $b = 0$, compute $a = \sqrt{n(K + x)}$; for $b = 1$, compute $a = \sqrt{K + x}$

3. Allocate $a$ as a witness to the ZKP protocol

4. Prove in ZKP that $a^2 = ((1 - b)n + b)\cdot (K+x)$

## Bounties

Because of its suitability for MPCs, the Legendre PRF is used in a construction for the Ethereum 2.0 protocol. In order to encourage research in this PRF, we announced some bounties at Crypto’19. See bounties.