Sub-exponential SXDH + LWE + LPN + NC0-PRG ⇒ iO

Free reduction · standard model · JLS21 · security loss: requires sub-exponential hardness of all four hypotheses

Statement

Let $\tau >0$ and $\delta ,\epsilon \in (0,1)$ be constants, and let $k,\ell ,n$ be large enough polynomials in $\lambda$. Assume sub-exponential hardness of the following: SXDH on asymmetric bilinear groups of prime order $p=O(2^{\lambda })$; LWE over ${\mathbb{Z}}_p$ with secret dimension $k$ and modulus-to-noise ratio $2^{k^{\epsilon }}$; LPN over ${\mathbb{Z}}_p$ (the field generalization, not binary LPN) with secret dimension $\ell$, polynomially many samples and error rate ${\ell }^{-\delta }$; and a Boolean PRG in ${\mathrm{NC}}^0$ with stretch $n^{1+\tau }$ on $n$-bit seeds. Then iO for all polynomial-size circuits exists — JLS21.

Notes

• A Boolean polynomial-stretch PRG in ${\mathrm{NC}}^0$ is a stronger hypothesis than a pseudorandom generator in ${\mathrm{NC}}^1$, since it is in particular one — folklore.