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:

## 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 )$

## 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.