No reduction from NP to compact FHE

Unconditional · BL13

Statement

Let $\mathsf{PKE}$ be a public-key bit-encryption scheme with compact homomorphic evaluation of a sensitive collection of functions, e.g. parities, majorities, or all ANDs and ORs. Every black-box reduction of constant query complexity that bases the message indistinguishability of $\mathsf{PKE}$ on a problem $\Pi$ places $\Pi$ in SZK, and every general adaptive one places $\Pi$ in $\mathbf{AM}\cap \mathbf{coAM}$ — BL13. A compact FHE scheme, restricted to bit messages, evaluates parities compactly, so the bounds apply to it. Hence, for an NP-complete $\Pi$, no constant-query black-box reduction exists unless some $\mathbf{NP}$-complete problem lies in $\mathbf{SZK}$, and no general adaptive one exists unless $\mathbf{NP}\subseteq \mathbf{coAM}$, equivalently $\mathbf{coNP}\subseteq \mathbf{AM}$.