Following @poncho's nice clarification of the RSA speedup here, let's see if I'm able to do the same in the case of the DGK cryptosystem:

  • We have pk = (n, g, h, u), sk = (p, q, $v_p$, $v_q$) which are generated as following:
    • we have 3 numbers, $k > t > l$
    • we pick u as the next prime greater than $2^{l+2}$ (having more than $l + 2$ bits)
    • we pick 2 random t bit primes, $v_p$, $v_q$
    • we generate p and q primes of length $k/2$ bits such that u and $v_p$ divide $p-1$ and u and $v_q$ divide $q-1$
    • we generate h of order $v_p*v_q$ modulo p and q
    • we generate g of order $u*v_p*v_q$ modulo p and q
  • Encryption: $E(m,r) = g^mh^r\pmod n$
  • Decryption: $E(m,r)^{v_p} = (g^{v_p})^m\pmod p$, which determines m uniquely, so we precompute all possible values of the right side (since the message space, u, is really small) and during decryption we just search for $c^{v_p}$ among the precomputed values. Later edit: The correction to the original paper states that $c^{v_p}$ uniquely determines m, so it's not necessary to use $c^{v_pv_q}$. I am not able to figure out how they came to this conclusion, but it does seem to work.

I know that there are a lot of details missing, but for those that are curious, I suggest reading the entire paper and the subsequent security correction (which replaces v with $v_p$ and $v_q$).

Now, we want to speed up the encryption process, since those exponentiations modulo n are rather slow, so we express $E(m,r)$ in $\mathbb{Z}_n^*$ as $E_p(m,r)$ and $E_q(m,r)$ in $\mathbb{Z}_p^* \times \mathbb{Z}_q^*$:

  • $E_p(m,r) = g^mh^r \pmod p$
  • $E_q(m,r) = g^mh^r \pmod q$

Now we apply the Chinese Remainder Theorem in order to obtain $E(m,r) \pmod n$. The formula used to achieve this is: $$\sum_{i} a_i \frac{N}{n_i} \left[\left(\frac{N}{n_i}\right)^{-1}\right]_{n_i}$$

So we have: $$E(m,r) = E_p(m,r)*q*(q^{-1}\bmod p) + E_q(m,r)*p*(p^{-1}\bmod q) \pmod n \Rightarrow$$

$$E(m,r) = (g^mh^r \bmod p)*q*(q^{-1}\bmod p) + (g^mh^r \bmod q)*p*(p^{-1}\bmod q) \pmod n$$

The above formula seems to make sense, right? Right?

Because further optimization is required, I need to somehow compute the above formula in two steps. More precisely, the random numbers can sometimes be generated in a different process, so I need the ability to split $E(m,r) = g^mh^r\pmod n$ in half:

  • first compute $E_{nonrand}(m,r) = g^m \pmod n$
  • then randomize: $E(m,r) = E_{nonrand}(m,r) * h^r\pmod n$

My intuition tells me that in this case I can still perform the encryption speedup and the formula should look something like this:

$$E_{nonrand}(m,r) = (g^m \bmod p)*q*(q^{-1}\bmod p) + (g^m \bmod q)*p*(p^{-1}\bmod q) \pmod n$$

$$E(m,r) = E_{nonrand}(m,r) * [(h^r \bmod p)*q*(q^{-1}\bmod p) + (h^r \bmod q)*p*(p^{-1}\bmod q)] \pmod n$$

I tested this formula and it seems to work, but I am unsure that I'm doing it right... Also, is it OK to skip the $\pmod n$ operation when computing $E_{nonrand}(m,r)$? It seems to me that it is redundant.

  • $\begingroup$ Well, the first obvious comment (without going into the math) is that CRT cannot be used to speed-up encryption, because CRT assumes that you know the factorization of the modulus, and the public key doesn't tell you that; that's a part of the private key. $\endgroup$
    – poncho
    May 14, 2012 at 13:47
  • $\begingroup$ That is a very good remark, @poncho. Let me try to explain the motivation: This is supposed to be a building block used for comparing private inputs. Alice will generate the keys, encrypt data with the public key and send ciphertexts to Bob, who performs homomorphic operations on them and then sends the results back to Alice. I'm working in the semi-honest model, so it is assumed that both parties are honest but curious and they follow the protocol no matter what. Now, this allows Alice to use parts of the private key for speeding up the encryption process, since Bob will not encrypt anything. $\endgroup$ May 14, 2012 at 17:01

1 Answer 1


As it turns out, this is just a beginner question and I think I managed to figure it out. Since $E(m,r) = g^mh^r \pmod n$, I can just split it in two: $E(m,r) = (g^m \pmod n) (h^r\pmod n)$ and then apply the CRT trick on both sides, after which I can multiply the results together to get back the original:

$E_{nonrand}(m,r) = (g^m \bmod p)*q*(q^{-1}\bmod p) + (g^m \bmod q)*p*(p^{-1}\bmod q) \pmod n$

$R_{h}(r) = (h^r \bmod p)*q*(q^{-1}\bmod p) + (h^r \bmod q)*p*(p^{-1}\bmod q) \pmod n$

$E(m,r) = E_{nonrand}(m,r)R_{h}(r) \pmod n$

Can anyone think of any reasons why I should not skip the (mod n) reductions for $E_{nonrand}(m,r)$ and $R_{h}(r)$? It looks to me like they are redundant...

LE: In practice, the (mod n) reductions are useful at each step to avoid numbers increasing in size, which can hurt performance.


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.