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:
- Replace $N$ with $q$, and assume $q>p$ and $q$ is large enough to contain the message and factors of $p$, and
- 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!