I am studying an encryption scheme which is Elgamal-like where I think CRT can help optimise the encryption and decryption but I am not sure if I am applying CRT the correct way.

I have a cyclic group $G$ of order $n=p_1p_2q$, generator $g$ of $G$, an element $h=g^x$ of $G$ where $x$ is a random integer and the secret key, and a message $m\in\mathbb{Z}_{p_1p_2}^*$. This group $G$ has a cyclic subgroup $F$ of order $p_1p_2$ generated by $f$. Computing discrete logs in $F$ is easy which we use to recover our message $m$ as follows:

Encryption -- Compute ciphertext $(c_1,c_2) = (g^r,\ f^mh^r)$ where $r$ is a random integer

Decryption -- Compute $c_2/c_1^x = f^m = l$. Recover $m$ by computing $$m = l^{-1}\pmod{p_1p_2}$$.

I am applying CRT in the final step by computing $$l^{-1}\pmod{p_1}$$ and $$l^{-1}\pmod{p_2}$$ and then combining them both using CRT to recover $m$. I have a feeling this is stupid because I am not really optimising anything, infact making it more computation heavy as single inversion modulo is faster than two inversions modulo + CRT. This is also visible when I time these two methods -- single inversion modulo $p_1p_2$ is faster.

So how should I properly apply CRT in these type of schemes?

  • $\begingroup$ Decryption -- Compute $c_2/c_1^x = f^m = l$. Recover $m$ by computing $$m = l^{-1}\pmod{p_1p_2}$$ Is it correct? $l^{-1} = f^{-m}$ and I don't see how $l^{-1}\pmod{p_1p_2}$ gives you $m$. $\endgroup$ Commented Oct 6, 2018 at 9:33
  • $\begingroup$ Oh, I see it is an abuse of notation on my part. $f$ and $f^m$ are not integers, they are ideals and $l$ is an ideal which has $m^{-1}$ which can be easily read off. Proposition 1 from eprint.iacr.org/2015/047.pdf $\endgroup$
    – Papa Delta
    Commented Oct 6, 2018 at 19:34
  • $\begingroup$ That's too much an abuse, better to use more conventional notations in the question. $\endgroup$ Commented Oct 6, 2018 at 20:02


Your Answer

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