DGK Cryptosystem Encryption Speedup

Question

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.

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.