PC + Search noisy $k$-LIN ⇒ PKE

Standard model · GHJS25

Statement

If the planted clique conjecture holds and the search variant of noisy $k$-LIN over expanders, recovering $\mathbf{s}$ from $(\mathbf{M},\mathbf{Ms}+\mathbf{e})$ for an expanding sparse $\mathbf{M}$, is hard, then semantically secure PKE exists — GHJS25, Theorem 8.8.

Notes

• The decisional variant gives the paper’s main construction — GHJS25, Theorem 5.12 (Noisy k-LIN + PC ⇒ PKE). The LPN search-to-decision reduction is not known to transfer to expanding matrices, so Theorem 8.8 is not known to follow from Theorem 5.12 — folklore.