2
$\begingroup$

To construct a secure multiparty computation function, we need to use the cyclic group G = Z*p^2 with p is a large prime. However, we are uncertain that DDH holds over this group.

Can you show that DDH holds/doesn't hold over the cyclic group Z*p^2?

Note that: the order of G is q = p(p-1) and q is multiple of the large prime p.

Thank you very much!

$\endgroup$
  • $\begingroup$ Am I correct in assuming that this is a homework assignment or something similar? If so, please provide an indication of what you are not understanding / need clarification on and your attempts at solving it, so we have a clear indication of where you are stuck. Questions just asking for a solution to a homework exercise are considered off-topic here. Thanks. $\endgroup$ – Ilmari Karonen Jun 2 '18 at 21:28
  • $\begingroup$ This is not my homework assignment. It is an important problem in my research in Secure multiparty computation area. So please do not close this topic. I need to be supported by the experts! $\endgroup$ – HienVD Jun 3 '18 at 3:19
  • $\begingroup$ That's very interesting. Could you describe your research in more detail? $\endgroup$ – Ilmari Karonen Jun 3 '18 at 12:03
  • $\begingroup$ I'm trying to construct a SMC protocol to efficiently compute the secure sum of n-parties. If this protocol is successfully built, then numerous of application problems are solved (e.g. privacy-preserving linear and logistic regression). $\endgroup$ – HienVD Jun 3 '18 at 14:32
4
$\begingroup$

I would say that DDH does not hold in $Z^*_{p^2}$.

Let's first consider DDH in $Z^*_{p}$. We know DDH is not hard because given a DDH tuple $(g^a,g^b,g^c)$, one can compute the Legendre symbols $(L(g^a),L(g^b),L(g^c))$, and know whether they are quadratic residues or not. If any of $(g^a,g^b)$ is a residue but $g^c$ is not, then we know $c\ne ab$.

It has also shown by Gauss that a number co-prime to an odd prime $p$ is a residue modulo any power of $p$ if and only if it is a residue modulo $p$. Thus the above can be extended to $Z^*_{p^2}$.

|improve this answer|||||
$\endgroup$

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.