4
$\begingroup$

I'm junior software developer and I need to implement a very simple authentication system based on Chaum-Pedersen ZKP Protocol. I know nothing about cryptography and I ask you to help me understand one thing in algorithm. An algorithm looks as follows: enter image description here

I just can't get what $q$ is. I've read about protocol in Cryptography: An Introduction by Nigel Smart. There's a phrase: 'We assume that $g$ and $h$ generate groups of prime order $q'$ but it says nothing to me. I've tried to google 'group of prime order' but it always linked to proving it's cycled and other stuff. I'm sorry if this question is stupid but I have no one else who could help me. It would be great to have an example with numbers as well.

$\endgroup$

1 Answer 1

9
$\begingroup$

I don't feel that this is the place to give a tutorial on elementary number theory, and so I'll just hit the aspects that immediately relate to your question.

When we take a prime $p$ and a value $g$ (which is not a multiple of $p$), then if we consider the sequence of values $g^0 \bmod p, g^1 \bmod p, g^2 \bmod p, ...$, then we find that at some point, the sequence will return to 1, and after that, start over. We call the order of $g$ the number of values we go through before we hit 1, that is, $g^q \bmod p = 1$, and that is the smallest value of $q > 0$ that satisfies this.

So, when Smart says that $g$ and $h$ have the same prime order, he is saying that $g^q \bmod p = 1$, $h^q \bmod p = 1$ and $q$ is prime (and in both cases, there is no smaller value of $q$).

How do you find such a $g, h, q$? Actually, it turns out to be not that difficult; $q$ will always divide $p-1$ evenly; we can pick a prime $p$ to make finding such a prime value $q$ easy. In addition, if $q$ is such a prime, then for any value $u$ without $p$ as a factor, the value $j = u^{(p-1)/q} \bmod p$ will be either 1 or have order $q$; so finding values $g, h$ is easy.

You asked for an example, I'll give you a toy one - we'll pick $p=23$ and $q=11$ (note that $11$ divides $23-1$ evenly), and $g=4$ and $h=9$ (it's easy to verify that these both have order 11). We also picks a secret value $x$ (we'll pick 6), and publishes $y_1 = g^x \bmod p = 4^6 \bmod 23 = 2$ and $y_2 = h^x \bmod p = 9^6 \bmod 23 = 3$

Then, the prover picks a random $k$, we'll arbitrarily select $k=7$

The prover then computes $r_1 = g^k \bmod p = 4^7 \bmod 23 = 8$ and $r_2 = h^k \bmod p = 9^7 \bmod 23 = 4$, and transmits those. Note that we did these computations modulo $p$ - that was implicit in the protocol (such modulus operations are commonly understood).

Now, the challenger picks a value $c$; we'll pick $4$; and sends that.

The prover then computes $s = (k - c \cdot x) \bmod q = (7 - 4 * 6) \bmod 11 = 5$ (note: in math, the $x \bmod q$ operation always returns the value between $0$ and $q-1$ so that $x - (x \bmod q)$ is a multiple of $q$ - many computer languages don't follow that - those languages are wrong), and sends that.

The verifier then checks that $r_1 = 8$ is the same as $g^s \cdot y_1^c \bmod p = 4^5 \cdot 2^4 \bmod 23 = 8$ and $r_2 = 4$ is the same as $h^s \cdot y_2^c \bmod p = 9^5 \cdot 3^4 \bmod 23 = 4$; both check out, and so this passes.

You do the same, only with values that are hundreds of digits in length, not the toy example I gave.

$\endgroup$
3
  • $\begingroup$ jesus, you've saved my life. thank you so much! $\endgroup$
    – jeldzinski
    Commented Mar 25, 2022 at 6:21
  • $\begingroup$ poncho and @jeldzinski, can you please help me understand why two generators g and h are, needed here? If we just use g and only generate y1, r1 and verifier only verify that, will there be any issue? $\endgroup$
    – tarun14110
    Commented Mar 20, 2023 at 0:16
  • 1
    $\begingroup$ @tarun14110 The point of Chaum-Pedersen is to prove knowledge of a single $r$ such that $y_1 = g_1^r$ and $y_2 = g_2^r$, so you need to have two generators. That's like, the point of the protocol $\endgroup$
    – Gareth Ma
    Commented Sep 10, 2023 at 8:31

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.