# How does the Legendre symbol reveal if $g^a$ is odd or even for Finite Field Diffie-Hellman

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?

• Comments have been moved to chat. Oct 14, 2023 at 16:48

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.

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

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.

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