0
$\begingroup$

I am trying to understand IND-CPA security in (Partially) Homomorphic Encryption schemes. However, the result of the proofs is usually something stating that a ciphertext does not expose anything about the plaintext.

How about the case where homomorphic operations are applied?

I wonder if there is some game similar to that used in IND-CPA that allows to prove that a ciphertext $C_1$ where a homomorphic operation has been applied is indistinguishable from another $C_2$ encrypting a random value. Something like:

  1. Adversary -> Challenger: $Enc(x)$, $Enc(y)$
  2. Challenger: samples random $r$, compute $c_0 = Enc(x) + Enc(y)$, $c_1 = Enc(r)$
  3. Challenger -> Adversary: $c_b$
  4. Adversary: makes it guess $b'$

It can be a different game, but something that captures that notion of not being able to know if a ciphertext is the result of a homomorphic operation.

$\endgroup$
4
  • $\begingroup$ I do not really get the relationship between IND-CPA security and the game you are proposing, that is based on chosen ciphertext? For an attacker disposing of $Enc(x)$ and $Enc(y)$ it is trivial to distinguish between $c_0$ and $c_1$, because the attacker can also compute $Enc(x) + Enc(y)$. The security of FHE relies on the fact that an encryption looks random, not that operations necessarily "re-randomize" the output ciphertext. Or maybe I missed something in your question? $\endgroup$ Commented Apr 30 at 14:04
  • $\begingroup$ @ProfCornDog: the statement «­ For an attacker disposing of $Enc(x)$ and $Enc(y)$ it is trivial to distinguish between $c_0$ and $c_1$, because the attacker can also compute $Enc(x)+Enc(y)$ » is valid or not depending on how that $+$ operation is defined. In Paillier encryption, it's possible to define $\operatorname{Enc}(x)+\operatorname{Enc}(y)=(r^n\,\operatorname{Enc}(x)\,\operatorname{Enc}(y)\bmod n^2)$ for random secret $r$ coprime with $n$, and then it's believed impossible to make the distinction that you state. $\endgroup$
    – fgrieu
    Commented Apr 30 at 15:51
  • $\begingroup$ "something that captures that notion of not being able to know if a ciphertext is the result of a homomorphic operation" reminds me of the notion of "function privacy" for (fully) homomorphic encryption: intuitively, function privacy guarantees that, even given the secret key, one should not be able to know which function was homomorphically evaluated. $\endgroup$
    – integrator
    Commented May 1 at 9:06
  • $\begingroup$ (cont) This property is actually fairly widely used, even for homomorphic encryption which is only linearly homomorphic (for instance, this is a key property to build two-round semi-honest oblivious transfer from (function-hiding) LHE). However, since this property follows from re-randomisability, few works formalise it $\endgroup$
    – integrator
    Commented May 1 at 9:07

2 Answers 2

0
$\begingroup$

First, it should be mentioned that

a ciphertext does not expose anything about the plaintext

is not the common definition of IND-CPA security for homomorphic encryption. Roughly speaking, in (fully) homomorphic encryption schemes it may be straightforward to extract particularities about which particular computation is being homomorphically computed. If one wants to hide this, one requires a (stronger) notion of security known as circuit private FHE.

So, what is IND-CPA for HE? Recall that HE augments an encryption scheme $\Pi = (\mathsf{KeyGen}, \mathsf{Enc}, \mathsf{Dec})$ with a publicly-computable evaluation function $\mathsf{Eval}$. This evaluation function may take in

  1. some collection of ciphertexts, and
  2. a description of the computation to homomorphically perform (say as a circuit), and
  3. some public key-material (generally called an evaluation key in the FHE literature).

We then say that $\Pi' := (\Pi, \mathsf{Eval})$ is IND-CPA if $\Pi$ satisfies the standard notion of IND-CPA, where an adversary gets as input not only the public key $pk$, but additionally the evaluation key $ek$, e.g. both of the public keys.

As for why this is a sensible definition, it's because after an adversary is given $ek$, they can now compute $\mathsf{Eval}_{ek}$ however they want. So, given a ciphertext $C := \mathsf{Enc}_{pk}(m_b)$ that they want to determine if $m_b$ is $m_0$ or $m_1$ (like in the standard IND-CPA game), they can leverage $\mathsf{Eval}_{ek}$ to homomorphically post-process this (and other ciphertexts $C^{(i)} := \mathsf{Enc}_{pk}(m^{(i)})$ that they know the underlying messages of) to $C_b := \mathsf{Enc}_{pk}(f(m_b, m^{(0)},\dots,m^{(k)}))$ If this homomorphic post-processing yields ciphertexts $C_0, C_1$ that are distinguishable, the HE scheme is not IND-CPA secure. But if $C_b$ are distinguishable from $C := \mathsf{Enc}_{pk}(m_b)$, it is not seen as a security concern.

Why should this not be seen as a security concern? Well the main idea behind HE is that we can export computation to some honest-but-curious server. This server has a description of the computation to perform (except for in the circuit private setting). So an adversary could instead corrupt this server to recover the description of the computation, e.g. the ciphertexts leaking the computation isn't the only potential leak one would need to handle, so if we can get more efficient schemes by allowing the ciphertexts to leak its seen as fine.

Note that assuming that $\Pi$ is secure when adversaries get $(pk, ek)$ is often a strictly stronger assumption than assuming $\Pi$ is (non-HE) IND-CPA secure. Micciancio and Vaikuntanathan just wrote a nice SoK on this, but I don't think there is a preprint publicly available. Roughly speaking, $ek$ is often of the form $ek = \mathsf{Enc}_{pk}(f(sk))$ for some publicly-known (scheme-dependent) function $f$, e.g. one requires a form of key-dependent message security (typically called circular security) that is not known to be reducible to the IND-CPA security of the underlying scheme, at least for lattice-based FHE schemes.

Note that this all gets significantly more complicated when the underlying HE is only approximately correct. See for example the paper of Li and Micciancio on this topic, though this is mostly relevant to a very specific lattice-based FHE scheme (CKKS), or other lattice-based FHE schemes where one improperly chooses parameters.

$\endgroup$
1
  • $\begingroup$ FYI, the as of part is not clearly written $\endgroup$
    – kelalaka
    Commented May 2 at 8:05
0
$\begingroup$

I don't know a standard game for what the question wants to achieve.

If I understand the requirement to be tested, it's met by a simple variant of Paillier encryption: define $\operatorname{Enc}(x)+\operatorname{Enc}(y)=(r^n\,\operatorname{Enc}(x)\,\operatorname{Enc}(y)\bmod n^2)$ for random secret $r$ coprime with $n$. The random $r$ makes the ciphertext for the sum essentially indistinguishable from random even with knowledge of $x$, $y$, and the $\operatorname{Enc}(x)$ and $\operatorname{Enc}(y)$ inputs, while keeping the homomorphic property.

The question's game seems to be on the right track. I assume it's added the obvious:

  • Key generation by Challenger
  • Sending the public key to Adversary
  • Uniformly random choice of $b\in\{0,1\}$ by Challenger
  • Test of $b=b'$ by Challenger to determine the outcome

There are a few ways Adversary could try to cheat:

  • As is, Challenger gets no insurance that Adversary's alleged $\operatorname{Enc}(x)$ and $\operatorname{Enc}(y)$ are valid ciphertext for some $x$ and $y$. For many but not all homomorphic encryption schemes, Challenger can verify this using the public and/or private key. If not, it still seems possible that Adversary sends $x$, $y$, and whatever random tapes it used to build $\operatorname{Enc}(x)$ and $\operatorname{Enc}(y)$ in the cardinal way, allowing Challenger to verity the alleged ciphertext (or alternatively, Challenger can be tasked to compute $\operatorname{Enc}(x)$ and $\operatorname{Enc}(y)$ from the material supplied by Adversary).
  • As is, Challenger gets no insurance that Adversary's alleged $x$ and $y$ are such that $x+y$ is in the set allowing encryption (e.g. in some definitions of Paillier encryption, $x+y$ must be in the range $[0,n)$ or $[(1-n)/2,(n-1)/2]$ ). This is easy to fix, since Challenger knows the private key, thus can compute $x$ and $y$ from $\operatorname{Enc}(x)$ and $\operatorname{Enc}(y)$, then $x+y$, then check that it's valid.
$\endgroup$
1
  • $\begingroup$ One still needs to rerandomize the $c_1$, too. $\endgroup$
    – kelalaka
    Commented Apr 30 at 19:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.