Homomorphic decryption circuit in integer-based scheme 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?
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)$.