The Legendre PRF

The Legendre pseudo-random function is a one-bit PRF defined using the Legendre symbol:

There are also variants of Legendre PRF with a higher degree, which replaces above with a univariate polynomial of degree two or more, where 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 for an input (square brackets indicate a shared value):

  1. Choose a quadratic non-residue

  2. Pre-compute a random square and a random bit

  3. Open the value

  4. Compute on the open value

  5. The result of the computation is

Suitability for ZKP

Similarly, the evaluation of this PRF can be proved efficiently in ZKP over . Let be any quadratic nonresidue in . To validate for :

  1. Prove in ZKP that

  2. For , compute ; for , compute

  3. Allocate as a witness to the ZKP protocol

  4. Prove in ZKP that


The Legendre bounties are now closed.

Further reading

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

Research papers