No fixed-construction reduction from HE to IND-CCA2 Security

Conditional · against fixed-construction reductions · assuming Homomorphic encryption · folklore

Statement

If an HE scheme with two distinct messages of equal length exists, the identity map does not turn HE into IND-CCA2-secure PKE: appending the constant bit $0$ to every ciphertext that its $\mathsf{Enc}$ outputs, a bit that $\mathsf{Dec}$ ignores and that $\mathsf{Eval}$ strips from its inputs and sets to $0$ on its output, keeps it HE for the same class, with the same correctness and CPA advantage, while flipping that bit of the challenge ciphertext gives an admissible decryption query that returns the challenge plaintext — standard. Without any modification, an HE scheme is not IND-CCA2-secure when a binary $f\in \mathcal{F}$ and inputs $x,w,z,m_0$ with $f(x,w)\ne x$, $f(m_0,z)\ne f(x,z)$, $|m_0|=|x|$ and $|z|=|w|$ can be computed from $\mathsf{pk}$ in polynomial time and the scheme decrypts correctly, except with negligible probability, on fresh and evaluated encryptions of inputs so computed (as under perfect correctness, or when $f$ and the inputs depend on $1^{\lambda }$ only), as for sums of messages, since $\mathsf{Eval}$ for $f$ applied to the challenge ciphertext and a fresh encryption gives, unless it returns the challenge ciphertext, an admissible decryption query that reveals the challenge bit — folklore.

Sketch

The length conditions make both challenges below admissible, and such inputs exist, though they need not be computable from $\mathsf{pk}$, when $f$ depends on both arguments and all messages have one length; for the sum in ${\mathbb{Z}}_M$ one may take $x=z=0$ and $w=m_0=1$. With $m_1:=x$ and challenge $c^{\ast }$, $\mathcal{A}$ computes $c^{\prime }\leftarrow \mathsf{Eval}(\mathsf{pk},f,c^{\ast },\mathsf{Enc}(\mathsf{pk},z))$ and outputs $0$ if $c^{\prime }=c^{\ast }$; otherwise the Phase-2 query $\mathsf{Dec}(\mathsf{sk},c^{\prime })$ returns $f(m_b,z)$, which determines $b$. When $b=1$, $c^{\prime }=c^{\ast }$ has negligible probability: with $w$ in place of $z$ it would contradict correctness, as $f(m_1,w)\ne m_1$, and a CPA adversary that computes the same inputs, encrypts $m_1$ itself and tests $\mathsf{Eval}(\mathsf{pk},f,c^{\ast },c)=c^{\ast }$ on its challenge $c$, an encryption of $z$ or of $w$, bounds the difference.

Notes

• The impossibility is stated as well known by LMSV11, for any scheme supporting any form of homomorphic operation.
• IND-CCA1-secure fully homomorphic encryption follows generically from multi-key identity-based FHE, instantiated as a leveled scheme from sub-exponential LWE in the random oracle model, and from sub-exponentially secure iO with sub-exponentially secure lossy encryption — CRRV17.
• Targeted malleability confines a scheme’s malleability to a declared set of allowable functions, giving a non-malleability guarantee alongside homomorphic evaluation — BSW12.