Ethereum Foundation logo
  • home
  • blog
  • research
  • bounties
  • team
  • events

The Legendre PRF

The Legendre pseudo-random function is a PRF that is extremely well suited for secure multi-party computation (MPC) and zero-knowledge proofs (ZKP) over arithmetic circuits.

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

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

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

There are also variants of Legendre PRF with a higher degree, which replaces K+xK+x above with a univariate polynomial fK(x)f_K(x) of degree two or more, where KK 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 [(xp)]\left[\left(\frac{x}{p}\right)\right] for an input [x][x] (square brackets indicate a shared value):

  1. Choose a quadratic non-residue α\alpha

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

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

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

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

Suitability for ZKP

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

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

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

  3. Allocate aa as a witness to the ZKP protocol

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


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.

Further reading

  • On using the Legendre PRF as a proof of custody: Ethresearch post
  • Concrete proof of custody construction (TBA)

Research papers


dankrad .at. ethereum .dot. org

© 2022 Ethereum Foundation. All rights reserved.