Sparse Ring-LPN ⇒ PCG

Standard model · BCG+20

Statement

Hardness of Sparse Ring-LPN over $R_p={\mathbb{Z}}_p[x]/(F(x))$ with $t$-sparse secret and noise yields a pseudorandom correlation generator for oblivious linear evaluation over $R_p$ (by the CRT, $\mathrm{deg}F$ OLEs over ${\mathbb{Z}}_p$ when $F$ splits into linear factors modulo $p$) and for authenticated multiplication triples: two seeds of size sublinear in the output length expand locally into the parties’ shares of the correlation. The construction also uses function secret sharing for sums of point functions, hence a PRG — BCG+20.

Sketch

Party $b$‘s seed holds $t$-sparse $e_b,f_b\in R_p$ and FSS keys for the four products $e_0{e}_1,e_0{f}_1,f_0{e}_1,f_0{f}_1$, each a $t^2$-sparse polynomial in ${\mathbb{Z}}_p[x]$ and hence shareable as a sum of $t^2$ point functions. Expanding the keys, reducing modulo $F$ and combining the shares with the public $1,a,a^2$ gives additive shares of $x_0{x}_1$ for $x_b=e_b+a{f}_b$; FSS security and Sparse Ring-LPN make $x_{1-b}$ pseudorandom given party $b$‘s seed.