International Association
for Cryptologic Research

We make progress on the foundational problem of determining the strongest security notion achievable by homomorphic encryption. Our results are negative. We prove that a wide class of semi-homomorphic public key encryption schemes (SHPKE) cannot be proven IND-PCA secure (indistinguishability against plaintext checkability attacks), a relaxation of IND-CCA security. This class includes widely used and versatile schemes like ElGamal PKE, Paillier PKE, and the linear encryption system by Boneh, Boyen, and Shacham (Crypto'04). In contrast to CCA security, where the adversary is given access to a decryption oracle, in a PCA attack the adversary solely has access to an oracle that decides for a given ciphertext/plaintext pair (c,m) if c indeed encrypts m. Since the notion of IND-PCA security is weaker than IND-CCA security, it is not only easier to achieve, leading to potentially more efficient schemes in practice, but it also side-steps existing impossibility results that rule out the IND-CCA security. To rule out IND-PCA security we thus have to rely on novel techniques. We provide two results, depending on whether the attacker is allowed to query the PCA oracle after it has received the challenge (IND-PCA2 security) or not (IND-PCA1 security -- the more challenging scenario). First, we show that IND-PCA2 security can be ruled out unconditionally if the number of challenges is smaller than the number of queries made after the challenge. Next, we prove that no Turing reduction can reduce the IND-PCA1 security of SHPKE schemes with O(\kappa^3) PCA queries overall to interactive complexity assumptions that support t-time access to their challenger with t=O(\kappa). To obtain our second impossibility results, we develop a new meta-reduction-based methodology that can be used to tackle security notions where the attacker is granted access to a decision oracle. Previous works on meta-reduction-based impossibility results focused on definitions that allow the attacker to access an inversion oracle (e.g. long-term key corruptions or a signature oracle) making the corresponding techniques generally not applicable in our scenario. To obtain our result, we have to overcome several technical challenges that are entirely novel to the setting of public key encryption.