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!


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

  • $\begingroup$ Very good - yes, I made an edit to require that $r\times p$ "pushes" the left hand side over the boundary of N. $\endgroup$
    – Russ
    Commented Jun 19, 2017 at 13:59
  • 1
    $\begingroup$ @Russ: having $r > q$ would do nothing to stop this attack. $\endgroup$
    – poncho
    Commented Jun 19, 2017 at 14:02
  • $\begingroup$ Yep, I see that now. Suppose that $N$ was replaced by $q$, and we assumed that $q>p$? $\endgroup$
    – Russ
    Commented Jun 19, 2017 at 14:07
  • $\begingroup$ I will skip this and try again ;-) Thanks for your comments. $\endgroup$
    – Russ
    Commented Jun 19, 2017 at 14:27
  • $\begingroup$ @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? $\endgroup$
    – poncho
    Commented Jun 19, 2017 at 14:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.