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

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

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

• 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 (2019)
• Ward Beullens, Tim Beyne, Aleksei Udovenko, Giuseppe Vitto: Cryptanalysis of the Legendre PRF and generalizations (2019)
• Novak Kaluđerović, Thorsten Kleinjung and Dušan Kostić: Cryptanalysis of the generalised Legendre pseudorandom function (2020)