2
$\begingroup$

I know that DDH does not hold in $Z_p^*$ because given $g, g^a, g^b, x$, we can compute legendre symbols of $g^a, g^b$ and compare it with legendre symbol of $x$. The same attack doesn't work when we consider the group $Z_N^*$ where N is product of 2 large primes. This is because computing jacobi symbol without knowing factors of N is hard by Quadratic Residuocity assumption. So, does DDH assumption hold in $Z_N^*$?

$\endgroup$
3
$\begingroup$

The same attack doesn't work when we consider the group $Z_N^*$ where N is product of 2 large primes. This is because computing jacobi symbol without knowing factors of N is hard by Quadratic Residuocity assumption.

This is incorrect: computing the Jacobi symbol can always be done in polynomial time, and does not require knowing the factorization. You're confusing it with the hardness of computing residuosity (i.e., checking whether an element of $Z_N^*$ is a square). DDH does not hold over $Z_N^*$. It is however conjectured to hold over $J_N$, the subgroup of elements with Jacobi symbol 1, see pages 23-24 of my paper.

EDIT: a screenshot of some old slides of mine: each element of $Z_N^*$ can have Jacobi symbol 1 or -1, and if it has Jacobi symbol 1, be square or non-square.

enter image description here

$\endgroup$
  • $\begingroup$ en.wikipedia.org/wiki/Jacobi_symbol This article describes how to compute Jacobi symbol of a given factors of n. May I know how to compute Jacobi symbol without the factors? $\endgroup$ – satya Dec 12 '18 at 13:40
  • $\begingroup$ Legendre symbol in $Z_p$ denotes whether an element is a square mod p. Doesn't Jacobi symbol in $Z_N$ denote whether an element is a square mod N? Why is comptuing jacobi symbol different from computing residuocity? $\endgroup$ – satya Dec 12 '18 at 13:41
  • 2
    $\begingroup$ @satya: to compute the Jacobi symbol, you can use the exact same algorithm used to compute the Legendre symbol. And, no, a Jacobi symbol doesn't indicate whether an element is a quadratic residue; a QR will necessarily have a QR of 1 (or 0); however, there are nonQR elements with Jacobi symbol 1 $\endgroup$ – poncho Dec 12 '18 at 13:45
  • 2
    $\begingroup$ @satya: an element $x \in \mathbb{Z}_n^*$ (where $n=pq$) will be a QR if $x$ is a QR mod $p$ AND $x$ is a QR mod $q$. $x$ will have Jacobi symbol 1 if $x$ is a QR mod $p$ XOR $x$ is a QR mod $q$ $\endgroup$ – poncho Dec 12 '18 at 13:49
  • 1
    $\begingroup$ @satya, the Wikipedia page which you link to does contain the answer to your question - see section "Computing the Jacobi Symbol" of the page. It contains an explicit method that does not involve knowing the factorization. $\endgroup$ – Geoffroy Couteau Dec 12 '18 at 13:59

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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