1
$\begingroup$

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!

Improve this question
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$
  • $\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 Jun 19 '17 at 13:59
  • 1
    $\begingroup$ @Russ: having $r > q$ would do nothing to stop this attack. $\endgroup$ – poncho Jun 19 '17 at 14:02
  • $\begingroup$ Yep, I see that now. Suppose that $N$ was replaced by $q$, and we assumed that $q>p$? $\endgroup$ – Russ Jun 19 '17 at 14:07
  • $\begingroup$ I will skip this and try again ;-) Thanks for your comments. $\endgroup$ – Russ Jun 19 '17 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 Jun 19 '17 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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