4
$\begingroup$

According to wikipedia(markdown is striped below) for Decisional Diffie–Hellman assumption:

the DDH assumption does not hold in the multiplicative group $Z(p)$, where $p$ is prime. This is because if $g$ is a generator of $Z(p)$, then the Legendre symbol of $g^a$ reveals if a is even or odd.

For example I have $p=23$, $g=2$ and $a=13$ than how do Legendre symbol reveal that $2^{13}$ is even or odd?

$\endgroup$
1

1 Answer 1

4
$\begingroup$

Since $g$ is generator then it is not square, otherwise cannot generate the group (See the bottom theorem). Therefore, as being a $\text{QNR}$, it's Legendre symbol is $−1$; $$\left(\frac{g}{p}\right) = -1 \tag{1}\label{r1}$$

Now, consider $g^a \bmod p$ and the Legendre calculation

$$\left(\frac{g^a}{p}\right) \equiv (g^a)^{\frac{p-1}{2}} \pmod p \quad \text{ and } \quad\left(\frac{g^a}{p}\right) \in \{-1,0,1\} \tag{2}\label{r2}$$

So, it can be $1$ or $-1$. Let's find out how to determine.

Now, Legendre is Multiplicative on it's top argument. I.e.

$$\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)\tag{3}\label{r3}$$

$g^a$ means multiply $g$ by $a$-times; combine (\ref{r1}) and (\ref{r2})

$$\left(\frac{g^a}{p}\right) = \underbrace{ \left(\frac{g}{p}\right)\cdots \left(\frac{g}{p}\right)}_{a-times} = \underbrace{ (-1)\cdots (-1)}_{a-times} = (-1)^a \tag{4}\label{r4}$$

  • If parity of $a$ is even, then the Legendre is $1$

  • If parity of $a$ is odd, then the Legendre is $-1$

Keep in mind that we don't need to determine $a$ here ( that is dLog and hard), we just use the result of the Legendre ( Eqn. \ref{r2}) to determine the parity with the fact that $(-1)^x= 1$ if $x$ is even, and $(-1)^x= -1$ if $x$ is odd.

Similarly, we can find the parity of $g^b$.

Now, we know the parity of $a$ and $b$ then we can find the parity of $ab$, thus this will leak the Legendre of $g^{ab}$ without knowing $g^{ab}$ by using Eqn. \ref{r4}.


Theorem: for an odd prime $p$, a generator $g$ cannot be Quadratic Residue. i.e. $\left(\frac{a}{p}\right) \neq 1$

Proof 1: For prime $p$ we have $\varphi(p)=p-1$ is even and we know that the multiplicative group $\pmod{p}$ has order $\varphi(p)$.

Let assume that $g$ is a square, i.e. $g=x^2$, then $x^{p-1}= g^{(p-1)/2} =1 \pmod{p}$.

On the other hand, if $g$ is a generator of the multiplicative group then it cannot have smaller power than $\varphi(p)$ equal to 1. i.e have $g^k\not=1\pmod{p}$ for $0<k<p-1$.

This is contradiction, so a generator $g$ cannot be a square.

Proof 2: If we assume that half of the elements are $\text{QR}$ and half are $\text{QNR}$, then using the fact that if we multiply a $\text{QR}$ with $\text{QR}$ then the result is $\text{QR}$, and this implies, a $\text{QR}$ cannot generate all the elements of the multiplicative group.


Note on the reverse of the theorem : The theorem states that being $\text{QNR}$ is a necessary condition, however, it is not sufficient. The number of generators of $\mathbb{Z}_{n}$ is studied and turns out to be $\varphi(\varphi(n))$. If we consider the $\mathbb{Z}_{571}$, then there are $\varphi(\varphi(571))= 144 < 285 = 570/2$ generators, so not every $\text{QNR}$ is a generator.


Example: Consider the $\mathbb{Z}_{571}^*$, where 571 is a prime number and $*$ indicates we consider the multiplicative group with the invertible elements.

Now, use the below SageMath code (try online)

rn = 571
R = Integers(rn)

g = R(2)

print(g.order())

print("kronecker(g, rn)", kronecker(g,rn))

assert kronecker(g,rn) == -1

a = 23
kga = kronecker(g^a,rn)
print("kronecker(g^a, rn)", kga)

ap = 0
if kga == -1:
    ap =  1 
else :
    ap = 0
    
print("parity of a = ", ap)

b = 33
kgb = kronecker(g^b,rn)
print("kronecker(g^b, rn)", kgb )

bp = 0

if kgb == -1:
    bp =  1 
else :
    bp = 0

print("parity of = ", bp)

print("parity a*b =", ap*bp)


print("kronecker(g^ab, rn)", kronecker(g^(a*b),rn))

assert ((-1)^(ap*bp) ) == kronecker(g^(a*b),rn)

to test the claims ( remove the prints and make a loop to test more with from random import randrange, a = randrange(rn), and b = randrange(rn)).

Note that SageMath uses Kronecker Symbol which is a generalization of the Legendre Symbol that allows non-primes.

$\endgroup$
2
  • $\begingroup$ how does using of subgroup of prime order prevent this leak? $\endgroup$
    – pacman
    Oct 13, 2023 at 13:19
  • 1
    $\begingroup$ That easy if you can restrict the group into only QR or k-th residues. That's the point of achieving DDH. $\endgroup$
    – kelalaka
    Oct 13, 2023 at 13:51

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.