# What is the hard problem for this algebraic encryption construct?

I would like to know what cryptographic hard problem this reduces to.

Select two large prime numbers $p$ and $q$, and let $N=pq$. Select a random positive integer $r$. Compute the encryption of plaintext $M$, ($M<p$) as $$E_I(M)\ =\ (M\ +\ r\times p)\mod N$$

This is the inner encryption of the Algebra Homomorphic Encryption Scheme: Xiang, Guangli, Benzhi Yu, and Ping Zhu. "A algorithm of fully homomorphic encryption." Fuzzy Systems and Knowledge Discovery (FSKD), 2012 9th International Conference on. IEEE, 2012.

Update: @poncho points out an easy GCD recovery attack against the inner encryption as stated. In fairness, the inner encryption was never to stand alone in Xiang's paper. I believe we can fix this by two changes:

1. Replace $N$ with $q$, and assume $q>p$ and $q$ is large enough to contain the message and factors of $p$, and
2. Require $r$ such that $r\times p>q$

Giving: $$E_I(M)\ =\ (M\ +\ r\times p)\mod q$$

Regardless, I'm interested in what the hard problem might be on such a thing.

I am relatively new to this. I looked at a few hard problems; none of the residuosity or discrete logarithmic problems seem to apply, but I'm hesitant to say that it's integer factorization or RSA in case there is some problem with a stronger assumption that fits. I want to get a good characterization of the construct so that I may describe it accurately.

Xiang et al. claims that the overall method is derived from ElGamal, and so I believe they feel the reduction is that of ElGamal (Discrete Logarithms), despite having introduced the inner encryption construct.

I want to get a good characterization of the construct so that I may describe it accurately.

I would characterize it as "insecure".

If someone has a ciphertext, and manages to guess the plaintext it corresponds to, then they can compute:

$$\text{gcd}(E_I(M) - M, N)$$

and they'll give then the factor $p$.

• Very good - yes, I made an edit to require that $r\times p$ "pushes" the left hand side over the boundary of N.
– Russ
Commented Jun 19, 2017 at 13:59
• @Russ: having $r > q$ would do nothing to stop this attack. Commented Jun 19, 2017 at 14:02
• Yep, I see that now. Suppose that $N$ was replaced by $q$, and we assumed that $q>p$?
– Russ
Commented Jun 19, 2017 at 14:07
• I will skip this and try again ;-) Thanks for your comments.
– Russ
Commented Jun 19, 2017 at 14:27
• @Russ: with the updated $E_I$ definition, how is the legitimate user supposed to decrypt. Assuming that he doesn't know $r$, then we can show that, for any $E_I(M)$ value, then for any $M'$, there exists an $r'$ with $E_I(M) = (M' + r'p) \bmod q$; that is, all plaintexts are possible. How is the decryptor supposed to know which is the right one? Commented Jun 19, 2017 at 14:46