Noisy k-LIN + PC ⇒ PKE

Standard model · GHJS25

Statement

If the planted clique conjecture holds against non-uniform circuits of size $n^{{\log }^{\alpha }n}$ for some $\alpha \in (0,1)$, and noisy $k$-LIN holds over $(\gamma ,\Omega (\log n),2^{(\log n{)}^{\alpha }})$-expanding matrices over ${\mathbb{F}}_p$, then there is a PKE scheme semantically secure against non-uniform polynomial-size circuits — GHJS25, Theorem 5.12.

Notes

• Planted clique together with the search variant of noisy $k$-LIN also gives PKE — GHJS25, Theorem 8.8 (PC + Search noisy k-LIN ⇒ PKE).