What is the hard problem for this algebraic encryption construct?

Question

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.

Thanks for your help!

Answer 1

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$.