8
$\begingroup$

I'm reading this excellent paper by Gentry as a smooth introduction to Fully Homomorphic Encryption. Most things are clear to me except from the way the homomorphic evaluation of the decryption circuit is described (which is after all the whole point).

If I understand correctly, we assume (for simplicity) 1 message $m$ encrypted as a ciphertext $c_1$ under the first public key $pk_1$ via $c_1=ENC(pk_1,m)$. Let's say this is a big $Q$-bit number.

Then Gentry suggests, that we double-encrypt this ciphertext, by encrypting each one of the $Q$-bits with a new public key $pk_2$, to obtain obviously a vector of $Q$ new ciphertexts, each one being $Q$-bits. Let's call this new ciphertext $\bar{c}$.

We also need an encryption of the $P$-bit secret key $sk_1$ in a similar fashion (i.e. encrypting each bit of it with $pk_2$ to generate $P$ vectors of $Q$-bit ciphertexts. Let's call this encrypted secret key $\bar{sk_1}$).

He now suggests, that we use the values $\bar{c},\bar{sk_1}$ (remember vectors of ciphertexts) as inputs to an evaluation circuit for the homomorphic evaluation of the decryption (this cleverly removes the inner encryption with $pk_1$ but still keeps the message wrapped under encryption with $pk_2$).

The scheme originally performs encryption of the form $c=pq+m$, where $m$ encodes 1-bit of the initial message as its least significant bit, so decryption is $(c \bmod p) \bmod 2$ ($\bmod 2$ obviously to retrieve the last bit). As such, the "default decryption" circuit accepts a $Q$-bit ciphertext and a $P$-bit secret key $p$ and outputs just one bit as the $\bmod 2$ operation dictates.

However, in the homomorphic case, the inputs are actually vectors and the output should be a fresh $Q$-bit ciphertext, that will be doubly-encrypted with a new key and so on. How then does this circuit look like? If it handles the vectors $\bar{c},\bar{sk}$ as huge integers it would still output 1 bit via the final $\bmod 2$ operation but this is not consistent with the concept of double encryptions.

Any idea?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ I do not see the problem. You have an encryption of a ciphertext $C$ (so a double encryption), and an encryption of the secret key. Using the homomorphic properties, you evaluate the decryption of $C$ with the secret key, in the encrypted domain. You therefore end up with an encryption of the output of the decryption circuit on $C$, that is, an encryption of a single bit. You do not want the decryption circuit to output a ciphertext, you want it to output a bit, but this output will stay "inside the encrypted domain" as everything is evaluated homomorphically. $\endgroup$
    – Geoffroy Couteau
    Commented Mar 2, 2017 at 20:58
  • $\begingroup$ I'm not sure I get the point. If you output 1 bit this is not compatible with the next steps of evaluation. The output of this homomorphic decryption should be a $Q$-bit number that needs to be double-encrypted in the next step under a new key and so forth. I can't see how a single output bit can carry encrypted information. How are the vectors of ciphertexts and vectors of secret keys going to be combined? $\endgroup$
    – Jimakos
    Commented Mar 3, 2017 at 0:36
  • $\begingroup$ The output of the decryption operation is a single bit, but this decryption is performed on a ciphertext inside another ciphertext, so the output you get is indeed a $Q$-bit ciphertext, as required. You seem to be confusing "the output of the decryption operation" with "the output of the homomorphic evaluation of the decryption operation on the encryption of a ciphertext $C$". The output of the homomorphic decryption should be a $Q$-bit number, hence the output of the decryption procedure should be a single bit, to lead to a $Q$-bit number when performed inside a ciphertext. $\endgroup$
    – Geoffroy Couteau
    Commented Mar 3, 2017 at 10:58
  • $\begingroup$ I just can't visualize how this evaluation will look like. The inputs should be $PQ$-bit vectors of the encrypted key $\bar{sk_1}$ and the $Q^2$-bit vector $\bar{c}$ of the double-encrypted ciphertext. How are these combined -circuit-wise- to evaluate a decryption under the public key? I just can see an evaluation of the form $(\bar{c} \bmod \bar{sk_1}) \bmod 2$ which is one bit. $\endgroup$
    – Jimakos
    Commented Mar 3, 2017 at 11:20
  • $\begingroup$ You might see it easier by abstracting out the details of how this particular scheme work. The only thing that matters here is that you are homomorphically evaluating a decryption circuit on a ciphertext $C$ that is itself encrypted, so that you end up with a ciphertext that contains the result of the decryption of $C$, id est, a ciphertext that contains a single bit. You do not end up with a bit, you evaluate something that does a mod 2 inside a ciphertext, so you end up with an encryption of a bit. $\endgroup$
    – Geoffroy Couteau
    Commented Mar 3, 2017 at 11:36

1 Answer 1

Reset to default
1
$\begingroup$

The circuit looks like any homomorphic version of a usual circuit: you replace the inputs by the corresponding ciphertexts and the operations by the corresponding homomorphic operations.

That means that,

  • The decryption circuit has as input a ciphertext $c$, which is a vector of $Q$ bits, and the secret key $sk$, a vector of $P$ bits; and it performs a $\mod 2$ operation at the end.
  • But the homomorphic decryption circuit, let's call $HDec$, has as input a vector of $Q$ ciphertexts ($\bar{c}$) representing the encryption of each bit of $c$ and a vector of $P$ ciphertexts ($\bar{sk}$) (representing the encryption of each bit of $sk$. And $HDec$ does not perform the $\mod 2$ operation, but a homomorphic operation equivalent to the $\mod 2$. Since it is a homomorphic operation, it returns a ciphertext (so, a $Q$-bit value, as expected).

Thus, $Dec$ takes vectors $(c_1, c_1, ..., c_Q)$ and $(sk_1, sk_2, ..., sk_P)$ and returns one bit $b$, while $HDec$ takes vectors $(Enc(c_1),..., Enc(c_Q))$ and $(Enc(sk_1), ..., Enc(sk_P))$ and returns a $Q$-bit value $Enc(b)$.

Improve this answer
$\endgroup$
6
  • $\begingroup$ @Geoffroy Couteau Thank you both for your replies. I can see maybe how a homomorphic evaluation of the first part of decryption $\bar{c} \bmod $\bar{sk_1}$ works because the values are huge integers but I fail to see how the homomorphic evaluation of $\bmod 2$ would look like. It's just that I'm trying to visualize it in terms of a circuit and I fail on that. $\endgroup$
    – Jimakos
    Commented Mar 3, 2017 at 11:50
  • $\begingroup$ Just look to my last paragraph and imagine the circuits... The circuit for $Dec$ works over bits while the circuit for $HDec$ works over ciphertexts... If $\mod 2$ is expressed as a sequence of fundamental operations $op_1, op_2, ..., op_\ell$ (additions and multiplications over bits) in the circuit $Dec$, then, (roughly speaking), the homomorphic $\mod 2$ is expressed as a sequence of $\ell$ homomorphic additions and multiplications over ciphertexts. $\endgroup$
    – Hilder Vitor Lima Pereira
    Commented Mar 3, 2017 at 11:57
  • $\begingroup$ As Gentry "greases" the decryption circuit, decryption amounts to $LSB(c) \oplus LSB(\lceil \sum_{i \in S} s_iz_i \rfloor)$. I'll omit for simplicity the second term for now. How would you homomorphically evaluate $LSB(\cdot)$ but with arguments $LSB(\bar{c})$? $\endgroup$
    – Jimakos
    Commented Mar 3, 2017 at 12:17
  • $\begingroup$ @Jimakos : ​ ​ ​ I would just output the zeroth entry of ​ $\overline{c}$ . ​ ​ ​ ​ ​ ​ ​ ​ $\endgroup$
    – user991
    Commented Mar 3, 2017 at 13:32
  • $\begingroup$ Let's examine the second term $\sum c \cdot s_i \cdot y_i$. Each of the $s_i$ is 1-bit and belong to a set $S$. $y_i$ are such that $\sum_{i \in S} y_i = 1/p \bmod 2$. So, our sum $\sum c \cdot s_i \cdot y_i = c/p \bmod 2$ is the decryption. So, how would these computations be calculated homomorphically? For example I should now choose $\bar{y_i}$ such that $\sum s_i \cdot \bar{y_i} = 1/\bar{p} \bmod 2$ ($\bmod 2$ homomorphically by keeping the least significant vector of the result)? And then perform $\sum \bar{c} \cdot s_i \cdot \bar{y_i}$? $\endgroup$
    – Jimakos
    Commented Mar 3, 2017 at 14:46

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.