The exponent of a number says how many times to multiply the number by it self. Ex:
\( 4^{3} = 4 \cdot 4 \cdot 4 = 64 \)
where 3 is the exponent (or power) and 4 is the base. In words we say 4 to the power 3.
Here are the laws of exponents:
| Law | Example |
|---|---|
| \( x^{1} = x \) | \( 3^{1} = 3 \) |
| \( x^{0} = 1 \) | \( 4^{0} = 1 \) |
| \( x^{-1} = \frac{1}{x} \) | \( 5^{-1} = \frac{1}{5} \) |
| \( x^{m} \cdot x^{n} = x^{m+n} \) | \( x^{2} \cdot x^{3} = (x \cdot x) \cdot (x \cdot x \cdot x) = x \cdot x \cdot x \cdot x \cdot x = x^{5} = x^{2+3} \) |
| \( \frac{x^{m}}{x^{n}} = x^{m-n} \) | \( \frac{x^{4}}{x^{2}} = \frac{x \cdot x \cdot x \cdot x}{x \cdot x} = x \cdot x \cdot \frac{x \cdot x}{x \cdot x} = x \cdot x \cdot 1 = x^{2} = x^{4-2} \) |
| \( (x^{m})^{n} = x^{m \cdot n} \) | \( (x^{2})^{3} = (x \cdot x) \cdot (x \cdot x) \cdot (x \cdot x) = x \cdot x \cdot x \cdot x \cdot x \cdot x = x^{6} = x^{2 \cdot 3} \) |
| \( (x \cdot y)^{n} = x^{n} \cdot y^{n} \) | \( (x \cdot y)^{2} = (x \cdot y) \cdot (x \cdot y) = x \cdot x \cdot y \cdot y = x^{2} \cdot y^{2} \) |
| \( (\frac{x}{y})^{n} = \frac{x^{n}}{y^{n}} \) | \( (\frac{x}{y})^{3} = (\frac{x}{y}) \cdot (\frac{x}{y}) \cdot (\frac{x}{y}) = \frac{x \cdot x \cdot x}{y \cdot y \cdot y} = \frac{x^{3}}{y^{3}} \) |
| \( x^{-n} = \frac{1}{x^{n}} \) | \( x^{-3} = (x^{-1})^{3} = (\frac{1}{x})^{3} = \frac{1}{x} \cdot \frac{1}{x} \cdot \frac{1}{x} = \frac{1 \cdot 1 \cdot 1}{x \cdot x \cdot x} = \frac{1}{x^{3}} \) |
You already use modulo computation when you look at the clock and e.g. needs to figure out what time it's 3 hours after 11 o'clock, which is 2 o'clock. In math we write that as:
\( (11 + 3) \: mod \: 12 = 2 \)
where 12 is the modulus because we want the time as an integer between 0 and 11 (12 o'clock is in this case denoted by 0). In words we say 11 plus 3 modulo 12 is equal 2. The result of a modulo computation is an integer between 0 and the modulus minus 1. E.g. with the modulus 3 we have that:
If we e.g. look at \( 27 \: mod \: 5 \) then modulo computes the number of times 5 divides 27 and then returns the remainder of the result which is 2 in this case, i.e. \( 27 \: mod \: 5 = 2 \). But how did we get this result?
First we compute the number of times it's possible to multiply 5 with the number \( x \) such that we get an integer as close as possible to 27 without exceeding it, i.e. we have to find the maximun value of \( x \) such that \( 5 \cdot x \leq 27 \). In this case we have that \( x = 5 \) because \( 5 \cdot 5 = 25 \leq 27 \). Then by subtracting 27 with 25 we get the answer \( 27 - 25 = 2\).
If the integer is negative e.g. \( -27 \: mod \: 5 \) we have to do it slightly different and the answer is \( -27 \: mod \: 5 = 3 \). In this case the integer \( x \) is negative and should be the closest integer that exceed -27, i.e. we have to find the minimum value of \( -x \) such that \( 5 \cdot -x \geq -27 \). Now we have that \( -x = -6 \) because \( 5 \cdot -6 = -30 \geq -27 \). Then by subtracting -27 with -30 we get the answer \( -27 - (-30) = -27 + 30 = 3\).
It's important that \( x \) or \( -x \) is an integer such as \( -14, 3, 17 \) etc. and NOT a fraction or float such as \( \frac{1}{4}, \frac{-3}{7}, 2.5, 5.1 \) etc.
If two integers \( a \) and \( b \) modulo the same modulus \( c \) returns the same remainder \( r \), then we say that \( a \) and \( b \) are congruent modulo \( c \). I.e. if \( a \: mod \: c = r \) and \( b \: mod \: c = r \) then \( a \equiv b \: (mod \: c) \). Also, notice that if the modulus \( c \) is greater than the integer \( a \), i.e. \( c > a \), the result will always be equal \( a \: mod \: c = a \).
A prime number is an integer greater than 1, which only can be divided evenly by 1 and itself. Divided evenly means that the result must not be a float. E.g. if you try to divide 13 with 3 it returns the float \( \frac{13}{3} = 4.333 \). We have that 13 is a prime number because it can only be divided evenly by 1 and itself, i.e. \( \frac{13}{1} = 13 \) and \( \frac{13}{13} = 1 \).
If an integer is not a prime number it's called a composite number. E.g. the integer 6 is a composite number because it can be divided evenly by 1, 2, 3 and 6:
\( \frac{6}{1} = 6 \), \( \frac{6}{2} = 3 \), \( \frac{6}{3} = 2 \) and \( \frac{6}{6} = 1 \)
The term composite means "something made by combining things". So, a composite number is an integer made by multiplying prime numbers:
Therefore, an integer is either a prime number or a product of prime numbers (a composite number).
The famous Greek mathematician Euclid proved that there are infinite many prime numbers.
Michael Rabin and Gary Miller have developed an algorithm that decides whether an integer is a prime or composite number by testing the integer with multiple bases denoted by \( a \). The algorithm is called the Rabin-Miller primality test.
Before we describe what the greatest common divisor of two integers are, we first define what we mean by a divisor. In this context is a divisor of an integer \( x \) some integer that divides \( x \) evenly, i.e. the result must not be a float. E.g. if you try to divide \( x=12 \) with 5 it returns the float \( \frac{12}{5} = 2.4 \) and 5 is therefore not a divisor of \( x=12 \). For \( x=12 \) we have the divisors 1, 2, 3, 4, 6 and 12 because \( \frac{12}{1} = 12 \), \( \frac{12}{2} = 6 \), \( \frac{12}{3} = 4 \), \( \frac{12}{4} = 3 \), \( \frac{12}{6} = 2 \) and \( \frac{12}{12} = 1 \).
Likewise the divisors of 16 is 1, 2, 4, 8 and 16 because \( \frac{16}{1} = 16 \), \( \frac{16}{2} = 8 \), \( \frac{16}{4} = 4 \), \( \frac{16}{8} = 2 \) and \( \frac{16}{16}=1 \).
The greatest common divisor of 12 and 16 is therefore 4, because it is the largest integer of the common divisors. In math we write that as \( \gcd(12, 16) = 4 \).
Two integers with greatest common divisor 1 are called relatively prime numbers or co-primes. E.g. 15 and 28 are relatively prime numbers because \( \gcd(15, 28) = 1 \) (notice that 28 is not a prime number).
If one of the two integers is a prime number the greatest common divisor will always be 1, i.e. \( \gcd(a, p) = 1 \) where \( a \) is an integer (either a prime number or a composite number) and \( p \) is a prime number.
One method to compute the greatest common divisor of two integers is by using the Euclidean algorithm developed by the famous Greek mathematician Euclid. See "The extended Euclidean algorithm" for more information about how to compute the greatest common divisor of two integer.
The extended Euclidean algorithm is an extended version of the Euclidean algorithm, which only returns the greatest common divisor of two integers. Given two integers \( a \) and \( b \) the extended Euclidean algorithm returns the integers \( a \), \( b \), \( \lambda \) and \( \mu \) such that:
\( a \cdot \lambda + b \cdot \mu = \gcd(a, b) \)
where \( \lambda \) and \( \mu \) are called the Bézout coefficients for \( a \) and \( b \). Only if \( a \) and \( b \) are relatively prime numbers, i.e. \( \gcd(a, b) = 1 \), then:
\( a \cdot \lambda + b \cdot \mu = 1 \)
and \( \lambda \; mod \; b \) is the inverse of \( a \), denoted \( a^{-1} = \lambda \; mod \; b \), and \( \mu \: mod \: a \) is the inverse of \( b \), denoted \( b^{-1} = \mu \: mod \: a \) (see "Modulo computation" for more information about the \( mod \) operator). One useful property of an integer and its inverse is that \( a \cdot a^{-1} \; mod \; b = 1 \) and \( b \cdot b^{-1} \; mod \; a = 1 \).
You can easily compute \( \gcd(a, b) \), \( \lambda \) and \( \mu \) for e.g. \( a=5 \) and \( b=39 \) with a simple table. So, let us first create a table with 3 columns (we do not yet know how many rows there will be in the table). Let us denote the entry in the first row and first column for [1,1], the entry in the first row and second column for [1,2], the entry in the second row and first column for [2,1] and so on.
Next we write \( b=39 \) in entry [1,1] and \( a=5 \) in entry [2,1]. Then we try to find the biggest integer \( q_{1} \), such that \( q_{1} \cdot a \leq b \). We have that \( q_{1}=7 \), which we write in entry [2,2], because \( 7 \cdot 5 = 35 \leq 39 \) and a remainder of \( r_{1}=4 \), which we write in entry [3,1].
Again we try to find the biggest integer \( q_{2} \), such that \( q_{2} \cdot r_{1} \leq a \). We have that \( q_{2}=1 \), which we write in entry [3,2], because \( 1 \cdot 4 = 4 \leq 5 \) and a remainder of \( r_{2}=1 \) that we write in entry [4,1]. Notice that we just computed the same as before, just with integers in a lower row.
The next computation returns a remainder of \( r_{3} = 0 \) because \( q_{3} \cdot r_{2} = 4 \cdot 1 = 4 \leq 4 = r_{1} \). We have now computed \( \gcd(5, 39)=r_{2}=1 \) since \( r_{3} = 0 \). And because 5 and 39 are relatively prime numbers, we know that \( \lambda \) and \( \mu \) exists and we can then start using the last column.
First we write \( x_{1}=0 \) in entry [4,3] and \( x_{2}=1 \) in entry [3,3]. Then we write \( x_{3}=q_{2} \cdot x_{2} + x_{1} = 1 \cdot 1 + 0 = 1 \) in entry [2,3]. For entry [1,3] we compute the same as before, just with integers from the row above, i.e. \( x_{4}=q_{1} \cdot x_{3} + x_{2} = 7 \cdot 1 + 1 = 8 \).
Finally we have that \( a \cdot x_{4} \pm b \cdot x_{3} = r_{2} \), where we need to decide whether it should be plus or minus between the two terms. Because \( a \cdot x_{4} = 5 \cdot 8 = 40 \), \( b \cdot x_{3} = 39 \cdot 1\) and \( 40 \geq 39 \) we have that \( 5 \cdot 8 - 39 \cdot 1 = 1 \) (which is the same as \( 5 \cdot 8 + 39 \cdot (-1) = 1 \)) and the Bézout coefficients are \( \lambda=8 \) and \( \mu=-1 \). Notice that \( a^{-1} = \lambda \; mod \; b = 8 \; mod \; 39 = 8\) and \( b^{-1} = \mu \; mod \; a = -1 \: mod \: 5 = 4\) where \( a \cdot a^{-1} \; mod \; b = 5 \cdot 8 \; mod \; 39 = 1 \) and \( b \cdot b^{-1} \; mod \; a = 39 \cdot 4 \; mod \; 5 = 1 \).
The table for computing \( 5 \cdot \lambda + 39 \cdot \mu = \gcd(5, 39) \) is:
| \( b=39 \) | \( x_{4}=8 \) | |
| \( a=5 \) | \( q_{1}=7 \) | \( x_{3}=1 \) |
| \( r_{1}=4 \) | \( q_{2}=1 \) | \( x_{2}=1 \) |
| \( r_{2}=1 \) | \( q_{3}=4 \) | \( x_{1}=0 \) |
| \( r_{3}=0 \) |
The set of integers \( \{ \dots, -2, -1, 0, 1, 2, \dots \} \) is denoted by the symbol \( \mathbb{Z} \), i.e. \( \mathbb{Z} = \{ \dots, -2, -1, 0, 1, 2, \dots \} \), and is called a ring of integers or a group. The group of integers modulo \( n \) is a subset of \( \mathbb{Z} \) and is denoted by the symbol \( \mathbb{Z}/n\mathbb{Z} \), but we use the shorthand version \( \mathbb{Z}_{n} \). This subset contains the following elements (because we compute modulo \( n \)):
\( \mathbb{Z}_{n} = \{ 0, 1, 2, \dots, n - 1 \}\)
Notice that whenever we make an addition or multiplication in \( \mathbb{Z}_{n} \), we always compute the addition or multiplication modulo \( n \) to obtain an integer in \( \mathbb{Z}_{n} \). To illustrate this we look at \( n = 5 \):
\( \mathbb{Z}_{5} = \{ 0, 1, 2, 3, 4 \}\)
When adding \( 3 \) with \( 4 \) in \( \mathbb{Z}_{5} \) we do the following: \( (3 + 4) \: mod \: 5 = 7 \: mod \: 5 = 2 \). Likewise, when multiplying \( 3 \) with \( 4 \) in \( \mathbb{Z}_{5} \) we do the following: \( (3 \cdot 4) \: mod \: 5 = 12 \: mod \: 5 = 2 \).
An integer \( a \) in \( \mathbb{Z}_{n} \) has an inverse if the greatest common divisor of \( a \) and \( n \) is 1, i.e. \( \gcd(a, n) = 1 \) (see "The extended Euclidean algorithm" for more information). The integer \( a \) is then called an unit. The set of units (all integers with an inverse in \( \mathbb{Z}_{n} \)) is denoted by the symbol \( (\mathbb{Z}/n\mathbb{Z})^{*} \). Again, we will use the shorthand version \( \mathbb{Z}_{n}^{*} \). If \( a_{1} \) and \( a_{2} \) are units then is the multiplication \( (a_{1} \cdot a_{2}) \: mod \: n \) also always an unit (i.e. \( a_{1} \cdot a_{2} \) is in the group \( \mathbb{Z}_{n}^{*} \)), but the addition \( (a_{1} + a_{2}) \: mod \: n \) may NOT be an unit (i.e. \( a_{1} + a_{2} \) is in the group \( \mathbb{Z}_{n} \) but may not be in the group \( \mathbb{Z}_{n}^{*} \)). We see the difference in the two sets \( \mathbb{Z}_{8} \) and \( \mathbb{Z}_{8}^{*} \):
If we chose \( n \) to be a prime number \( p \) then for all integers \( a \) excluding 0 in \( \mathbb{Z}_{p} \) we have that \( \gcd(a, p) = 1 \), which result in that \( \mathbb{Z}_{p}^{*} \) contains all integers from \( \mathbb{Z}_{p} \) excluding 0, i.e.:
\( \mathbb{Z}_{p}^{*} = \{ 1, 2, 3, \dots, p - 1 \}\)
E.g. for \( p=7 \) we see that the only difference in the two sets \( \mathbb{Z}_{7} \) and \( \mathbb{Z}_{7}^{*} \) is the integer 0:
The number of elements in \( \mathbb{Z}_{n}^{*} \) is denoted by the symbol \( \phi(n) \) after a famous Swiss mathematician called Euler and is called Euler's phi function. As we saw previously, then if \( n \) is a prime number \( p \) then \( \phi(p) = p-1 \). The number of elements in a group \( G \) is also called the order of \( G \) and is written as \( \left| G \right| \). The order of:
If we e.g. chose the elements \( x \), \( a \) and \( b \) from the group \( \mathbb{Z}_{p}^{*} \) and want to compute \( x^{a + b} \: mod \: p \), then in the exponent we actually compute \( a + b \) modulo the order of the group, i.e. \( a + b \: mod \: (p-1) \) because \( \left| \mathbb{Z}_{p}^{*} \right| = \phi(p) = p-1 \). So, what we actually compute is \( x^{a + b \: mod \: (p-1)} \: mod \: p \). The same is true if we had chosen one of the other groups; We always compute modulo the order of the group in the exponent. Therefore, next time you look at an equation from a cryptosystem and wonder why they suddenly compute e.g. modulo \( p-1 \) instead of modulo \( p \), then it's because the equation is used in the exponent of some integer.
In the following we use the group \( \mathbb{Z}_{p} \) as an example for simplicity, but we could have chosen any group.
There exist an element \( g \) in the group of integers \( \mathbb{Z}_{p} \) (see "The group of integers and units" for more information), where \( p \) is a prime number, whose powers gives every elements in the set of units \( \mathbb{Z}_{p}^{*} \), i.e. there exists an integer \( g \) in \( \mathbb{Z}_{p} \) such that:
\( \mathbb{Z}_{p}^{*} = \{ g^{1} \: mod \: p, g^{2} \: mod \: p, g^{3} \: mod \: p, \dots, g^{p-1} \: mod \: p \} \)
where \( g^{p-1} \: mod \: p = 1 \) because \( p-1 \: mod \: (p-1) = 0 \) (remember that the order of \( \mathbb{Z}_{p}^{*} \) is \( p-1 \) and we compute modulo the order of the group in the exponent of \( g \) because \( g \) belongs to the group \( \mathbb{Z}_{p}^{*} \)) and \( g^{0} = 1 \). Such a \( g \) is called a generator or a primitive root of the group and it's denoted as \( \left< g \right> = \mathbb{Z}_{p}^{*} \). We also say that the order of \( g \) is \( ord(g) = p-1 \) because \( g \) generates the group \( \mathbb{Z}_{p}^{*} \) with \( p-1 \) elements.
To make it clear we look at an example with the prime number 5. We remember that \( \mathbb{Z}_{5}^{*} = \{ 1, 2, 3, 4 \} \) (see "The group of integers and units" for the example). The group \( \mathbb{Z}_{5}^{*} \) has 2 as a generator because the powers of 2 generates every elements in the group, i.e. \( \left< 2 \right> = \mathbb{Z}_{5}^{*} \):
The last power is 4 because \( p - 1 = 5 - 1 = 4\). On the other hand, 4 is NOT a generator of \( \mathbb{Z}_{5}^{*} \) because the powers of 4 only generates the integers 1 and 4:
If you don't know the factorization of the integer \( p-1 \), then the only way to find a generator is to make the above computation, i.e. check that it generates every element in the group \( \mathbb{Z}_{p}^{*} \). Otherwise, if you know the factorization of the integer \( p-1 \), then for every prime number \( q \) that evenly divides the integer \( p-1 \) we check that \( g^{(p-1)/q} \: mod \: p \neq 1 \) for a random integer \( g \) in the group \( \mathbb{Z}_{p} \). If this is the case, then \( g \) is a generator of \( \mathbb{Z}_{p}^{*} \).
Because the prime factorication problem is hard (the problem of computing the factorization of the integer \( p-1 \)), we use a so called safe prime \( p \). A safe prime \( p \) is on the form \( p = 2 \cdot q + 1 \) where \( q \) is a prime number. Now the factorization of \( p-1 \) is always only \( 2 \) and \( q \). E.g. if we compute the safe prime \( p = 2 \cdot 5 + 1 = 11 \) with the prime number \( q = 5 \) we see that \( g = 7 \) is a generator of the group \( \mathbb{Z}_{11}^{*} \) because:
where 2 and \( q=5 \) are the only prime numbers that divides \( p-1=11-1=10 \) evenly. For the same reason is \( g = 5 \) not a generator of \( \mathbb{Z}_{11}^{*} \) because:
The group \( \mathbb{Z}_{n}^{*} \) where \( n \) is a composite number may not have a generator, but if \( n \) is a prime number \( p \) then the group \( \mathbb{Z}_{p}^{*} \) has minimum one generator.
Let \( g \) be a generator of the group \( G \). Given the values \( g \) and \( H \), the discrete logarithm (DL) problem is about computing the exponent \( a \) in the following equation, which is a hard problem:
\( g^{a} = H \)
The exponent \( a \) is also called the discrete logarithm of \( H \) to the base \( g \).
E.g. if we use the group \( \mathbb{Z}_{p}^{*} \) where \( p \) is a large prime number and \( g \) is a generator of the group, then if you are given \( g \), \( p \) and \( H \) it's a hard to compute \( a \), such that it satisfies the following equation:
\( g^{a} \: mod \: p = H \)
Besides the DL problem we have two similar problems; the Diffie-Hellman (DH) problem and the decisional Diffie-Hellman (DDH) problem. Given the values \( g \), \( g^{a} \) and \( g^{b} \) the DH problem is about computing the exponent \( a \cdot b \) in \( g^{a \cdot b} \).
Similar, given the values \( g \), \( g^{a} \), \( g^{b} \) and \( g^{c} \) the DDH problem is about deciding whether \( c = a \cdot b \) or \( c \) is a random integer.
You may have noticed that if we can solve the DL problem, i.e. computing \( a \) in \( g^{a} = H \), then we also can solve the DH problem: first we compute \( a \) in \( g^{a} \), then \( b \) in \( g^{b} \) and finally \( a \cdot b \). Now this also implies that we can solve the DDH problem: first we compute \( a \cdot b \) as described above, then \( c \) in \( g^{c} \) and finally we check whether \( c = a \cdot b \).
Let \( n \) be the product of two large prime numbers \( p \) and \( q \), i.e. \( n = p \cdot q \). Then, if you know the value of \( n \) it's hard to compute \( p \) and \( q \) from \( n \).
The problem of computing \( p \) and \( q \) is called the prime factorization problem.
The goal of an identification scheme is to allow someone's identity to be confirmed; in our case Peggy wants to prove to Victor that she is really Peggy. If Peggy and Victor meet face to face Peggy might use her driver's license to identify herself, but the problem becomes more difficult when Peggy and Victor are communication over an insecure channel eavesdropped by their adversary Eve. An identification scheme should prevent Eve from impersonating Peggy. Even Victor should not be able to impersonate Peggy after Peggy has identified herself to him.
A zero-knowledge proof such as the Fiat-Shamir zero-knowledge proof is one way of doing identification and typically performs multiple rounds of challenge and response messages, in that sense Victor sends Peggy a challenge and Peggy respond on the challenge by using knowledge she only possesses, which identify herself to Victor. You can think of it as Peggy using her secret key to create the response and Victor verifying the response with hers public key. The reason why it's called a zero-knowledge proof is because Victor learns nothing new (zero-knowledge) from the exchange of messages between him and Peggy (the challenge and response messages). I.e. Peggy convinces Victor that a certain claim is true without giving Victor any information he could use to convince other people about that the claim is true.
An identification scheme based on a zero-knowledge proof must satisfy the following three conditions:
So, why not just use a public key system such as RSA or ElGamal as an identification scheme with the zero-knowledge property where Peggy wants to convince Victor about that she is the owner of the secret key corresponding to the public key that Victor is in possession of? Now Victor could encrypt a message \( m \) with Peggy's public key and send the ciphertext to Peggy (the challenge). If Victor then receives the correct plaintext from Peggy (the response), he know that Peggy has the secret key (because it's only the corresponding secret key of the public key that can decrypt the ciphertext correct).
If Victor is honest and chooses the message \( m \) by himself he learns nothing new from the exchange of messages and the protocol would work as desired, but if Victor is malicious he could just choose a previous seen ciphertext from Peggy and send it to her as the challenge. Now, when Victor receives the plaintext from Peggy (the response), he has gained knowledge about the content of this plaintext, which he did not have before.
The above problem can be solved if Peggy and Victor also uses a commitment scheme such as the Pedersen commitment scheme where Peggy makes a commitment to a value that is hidden for Victor until Peggy chooses to reveal it by opening the commitment. Now, in the above example when Peggy receives the ciphertext from Victor (the challenge) she first decrypt the ciphertext, which result in a plaintext \( m' \), she then makes a commitment to \( m' \) and sends the commitment to Victor instead of \( m' \). Victor then sends the original plaintext \( m \) to Peggy who checks that \( m' = m \). Only if this is the case she know that Victor is honest and opens the commitment by sending \( m' \) (and the used randomness in the commitment) to Victor who checks that the commitment is correct. And if the commitment is correct Peggy has convinced Victor about that she is the owner of the secret key corresponding to the public key that Victor is in possession of. Otherwise if \( m' \neq m \) in Peggy's last check then Victor has tried to gain knowledge about the plaintext of the ciphertext.
Another classic example of a commitment scheme is the coin flipping by telephone problem: In this scenario Peggy and Victor each flip a coin and should agree on who the winner is where Peggy wins if both coins shows the same side and Victor wins if they are different. The obvious problem is that if Peggy tells the result of her coin first, then Victor can answer in such a way that he wins no matter what the actually result of his coin is. At the same time Peggy has no chance of verifying that Victor tells the truth because they are communication through a telephone.
One solution to this problem is that Peggy first flip her coin and then makes a commitment to the result that she sends to Victor. The commitment has two properties: first the result of Peggy's coin is hidden for Victor and second the commitment prevent Peggy from changing her answer later on. Victor then flip his coin and sends the result to Peggy. When Peggy receives Victor's result she opens the commitment, i.e. she reveals the result of her coin to Victor. Now Peggy and Victor can agree on the winner of the game in a honest way.
A commitment scheme comes with two different flavors; either it's unconditional binding and computational hiding or it's computational binding and unconditional hiding. The four properties are defined as follows:
If the commitment scheme is unconditional binding and computational hiding Peggy then generates the secret and public keys and sends the public key to Victor who verifies that it's generated correctly. Otherwise, if the commitment scheme is computational binding and unconditional hiding Victor then generates the keys and sends the public key to Peggy who verifies that it's generated correctly.
So, it seems that an unconditional binding and unconditional hiding commitment scheme would be preferable, why do we not create such a scheme? The answer is because it's impossible: Assume that we have a commitment scheme with the desired properties. Because it's unconditional hiding there exists two different values \( m \) and \( m' \) that generates the same commitment. If this was not the case, an adversary (or Peggy and Victor) could try to compute the commitment of every value (remember that unconditional implies that the adversary has infinity computing power/time) and compare them to the commitment and hereby find the committed value. But the unconditional hiding property contradicts the unconditional binding property because we now have two different values \( m \) and \( m' \) that generates the same commitment.
As described previously performs an identification scheme based on a zero-knowledge proof multiple rounds of challenge and response messages, which is not preferable. Therefore, we can use sigma protocols such as Schnorr's sigma protocol that only performs one round of challenge and response messages.
In a sigma protocol Peggy knows a witness \( w \) of a problem \( x \) in some relation \( R \). You may think of \( w \) as the solution to the problem \( x \) where the relation \( R \) is the set of all problems and solutions. E.g. \( R \) could be the relation of all discrete logarithm problems where \( w \) is the discrete logarithm of \( x \), i.e. \( x = g^{w} \) for some \( g \). This is also denoted as \( (x,w) \in R \). A sigma protocol must satisfy the following four conditions:
Some sigma protocols have one of the following two properties (or both in some cases):
The Fiat-Shamir zero-knowledge proof is a zero-knowledge proof proposed by Amos Fiat and Adi Shamir in 1986.
Peggy first chooses two large prime numbers \( p \) and \( q \) and computes \( n = p \cdot q \). She then chooses a secret value \( x \) and computes the public value \( y = x^{2} \: mod \: n \). Now Peggy claims that \( y \) is a square modulo \( n \). And hence, this is what she wants to convince Victor about without revealing any information (the value of \( x \)) such that Victor can convince other people about that \( y \) is a square modulo \( n \). You may think of it as \( x \) being Peggy's secret key and \( y \) being her public key. Peggy then wants to convince Victor about that she is the owner of the secret key \( x \) corresponding to the public key \( y \) that Victor is in possession of.
In this protocol one round of challenge and response messages are not enough to convince Victor, therefore the following steps are performed \( k \) times where \( k \) is chosen such that if Peggy don't know the secret value \( x \) and just guesses, the probability that she guess correctly every time is very small.
In the protocol Peggy first chooses a random value \( r \) between \( 1 \) and \( n - 1 \) and then computes \( a = r^{2} \: mod \: n \), which she sends to Victor. Notice that \( a \) is a square modulo \( n \). Victor then chooses the random challenge \( b \) where either \( b=0 \) or \( b=1 \) and sends it to Peggy. Peggy respond by computing \( z = x^{b} \cdot r \: mod \: n \) where she only use the secret value \( x \) when \( b = 1 \). Finally Victor verifies the respond by checking that \( p = z^{2} \: mod \: n \) is equal to \( p' = y^{b} \cdot s \: mod \: n \). Only if \( p=p' \) a new round starts where Victor sends a new challenge \( b' \) to Peggy, otherwise the protocol stops.
We now have to check that the protocol satisfies the three conditions: completeness, soundness and zero-knowledge. For completeness the last check is always true when \( y \) is a square modulo \( n \) because:
\( \eqalign{ p &= z^{2} \: mod \: n &&(z = x^{b} \cdot r) \\ &= (x^{b} \cdot r)^{2} \: mod \: n &&(\mbox{exponent rule}) \\ &= x^{b \cdot 2} \cdot r^{2} \: mod \: n &&(\mbox{exponent rule}) \\ &= (x^{2})^{b} \cdot r^{2} \: mod \: n &&(y = x^{2} \: \mbox{and} \: a = r^{2}) \\ &= y^{b} \cdot a \: mod \: n = p' } \)
For soundness we assume for contradiction that \( y \) is not a square modulo \( n \) and Peggy in one round still can give a valid response for both \( b = 0 \) and \( b = 1 \), i.e. the last check Victor makes is always true even when \( y \) is not a square modulo \( n \). For \( b = 0 \) we denote Peggy's response as \( z_{0} \), i.e. we have that \( z_{0}^{2} \: mod \: n = a \: mod \: n \), and for \( b = 1 \) we denote Peggy's response as \( z_{1} \), i.e. we have that \( z_{1}^{2} \: mod \: n = y \cdot a \: mod \: n \). From the following equation we see that \( y \) must be a square modulo \( n \), which contradict our assumption:
\( \eqalign{ z_{1}^{2} \: mod \: n &= y \cdot a \: mod \: n &&(a = z_{0}^{2}) \\ z_{1}^{2} \: mod \: n &= y \cdot z_{0}^{2} \: mod \: n \\ z_{1}^{2} \cdot (z_{0}^{2})^{-1} \: mod \: n &= y \cdot z_{0}^{2} \cdot (z_{0}^{2})^{-1} \: mod \: n &&(z_{0}^{2} \cdot (z_{0}^{2})^{-1} = 1) \\ z_{1}^{2} \cdot (z_{0}^{2})^{-1} \: mod \: n &= y \: mod \: n &&(\mbox{exponent rule}) \\ z_{1}^{2} \cdot (z_{0}^{-1})^{2} \: mod \: n &= y \: mod \: n &&(\mbox{exponent rule}) \\ (z_{1} \cdot z_{0}^{-1})^{2} \: mod \: n &= y \: mod \: n } \)
I.e. if Peggy can produce a valid response for both \( b = 0 \) and \( b = 1 \) then \( y \) must be a square modulo \( n \) because \( y = (z_{1} \cdot z_{0}^{-1})^{2} \: mod \: n \). Therefore, when \( y \) is not a square modulo \( n \) Peggy can only produce a valid response for the challenge \( b = 0 \), which implies that in one round Victor has \( \frac{1}{2} \) probability for accepting Peggy's response when \( y \) is not a square modulo \( n \). Therefore, when repeating the protocol \( k \) times the probability is \( (\frac{1}{2})^{k} \) and with e.g. \( k = 80 \) the probability is acceptable small.
To prove that the protocol is zero-knowledge we have to build a simulator \( M \) that can convince Victor about that \( y \) is a square modulo \( n \) (notice that \( M \) doesn't know the value of \( x \)). The simulator \( M \) is constructed as follows:
Step (3) where \( M \) rewind Victor may seem a bit odd, but it's essential the same as restarting a computer (in our case Victor) when it freeze (in our case when \( M \) receives a challenge from Victor it can't answer). We see that \( M \) still satisfies completeness because when \( c=b \) then:
\( \eqalign{ a_{M} \cdot y^{c} \: mod \: n &= (r^{2} \cdot (y^{-1})^{c}) \cdot y^{c} \: mod \: n &&(\mbox{exponent rule})\\ &= r^{2} \cdot (y^{c})^{-1} \cdot y^{c} \: mod \: n &&((y^{c})^{-1} \cdot y^{c} \: mod \: n = 1)\\ &= r^{2} \: mod \: n } \)
Remember that \( (a_{M},c,z_{M}) \) (the output of \( M \)) must have the same distribution as \( (a,b,z) \) (the output of the real protocol between Peggy and Victor):
| Initialization | |
| Peggy: Chooses the secret prime numbers \( p \) and \( q \) and computes \( n = p \cdot q \). Chooses the secret value \( x \) which Peggy wants to convince Victor about that she know. Computes the public value \( y = x^{2} \: mod \: n \). Chooses the random integer \( 1 \leq r \leq n-1 \) and computes \( a = r^{2} \: mod \: n \). | |
| Peggy sends the public values \( (n, y, a) \) to Victor. | |
| The following is performed \( k \) times | |
| Challenge | |
| Victor: Chooses randomly a challenge \( b \) where \( b=0 \) or \( b=1 \). | |
| Victor sends the challenge \( b \) to Peggy. | |
| Response | |
| Peggy: Computes the response \( z = x^{b} \cdot r \: mod \: n \). | |
| Peggy sends the response \( z \) to Victor. | |
| Verification | |
| Victor: Verifies that \( y \) is a square modulo \( n \) by checking that \( z^{2} \: mod \: n = y^{b} \cdot a \: mod \: n \). | |
Try a demo of the zero-knowledge protocol here.
Peggy first chooses the two prime numbers \( p = 197 \) and \( q = 281 \) and computes \( n = p \cdot q = 197 \cdot 281 = 55357 \). She then chooses the secret value \( x = 57 \) and computes the public value \( y = x^{2} \: mod \: n = 57^{2} \: mod \: 55357 = 3249 \) which she wants to convince Victor about is a square modulo \( n = 55357 \). Next Peggy chooses the random integer \( r = 60 \) and computes \( a = r^{2} \: mod \: n = 60^{2} \: mod \: 55357 = 3600 \) which she sends to Victor.
In the first round Victor chooses the challenge \( b = 0 \) which he sends to Peggy. Peggy respond on the challenge by computing \( z = x^{b} \cdot r \: mod \: n = 57^{0} \cdot 60 \: mod \: 55357 = 60 \) which she sends to Victor. Victor then verifies the response by checking that \( p = z^{2} \: mod \: n = 60^{2} \: mod \: 55357 = 3600 \) is equal to \( p' = y^{b} \cdot a \: mod \: n = 3249^{0} \cdot 3600 \: mod \: 55357 = 3600 \).
Because \( p = p' \) Victor accept the response as valid and start a new round by sending a new challenge \( b' \) to Peggy. If Peggy's response is valid in all \( k \) rounds then Victor is convinced that \( y = 3249 \) is a square modulo \( n = 55357 \).
The Pedersen commitment scheme, proposed in 1991 by Torben P. Pedersen, is an unconditional hiding and computational binding commitment scheme based on the discrete logarithm problem. The setup of the scheme is the same as in the Schnorr signature and the Digital Signature Algorithm (DSA). Notice that Victor generates the keys because the commitment scheme is unconditional hiding and computational binding.
First Victor (or a trusted third party) chooses two prime numbers \( p \) and \( q \) such that \( p \: mod \: q = 1 \) (by first choosing \( q \) and then computing \( p = i \cdot q + 1 \) for \( i \geq 2 \) until \( p \) is a prime number) and a generator \( g \) of order \( q \) from the group \( \mathbb{Z}_{p}^{*} \). If a generator \( g \) has order \( q \), it means that \( g \) generates a subgroup \( G \) of \( \mathbb{Z}_{p}^{*} \) with \( q \) elements. Victor can easily find \( g \) by computing \( g = g_{1}^{(p-1)/q} \: mod \: p \) where \( g_{1} \) is a generator of the group \( \mathbb{Z}_{p} \).
Victor then chooses a secret key \( a \) between \( 1 \) and \( q-1 \) and computes the public key \( pk = h \) where \( h = g^{a} \: mod \: p \) which he sends to Peggy. Before Peggy makes a commitment to the value \( x \) she verifies the received public key and only if it's correct generated she continues. Peggy first chooses a random integer \( r \) between \( 1 \) and \( q-1 \) and then she uses the received public key \( pk \) to compute the commitment \( c = commit_{pk}(x, r) = g^{x} \cdot h^{r} \: mod \: p \) which she sends to Victor.
At some later point Peggy opens the commitment by sending the values \( x \) and \( r \) to Victor who first computes the commitment by \( c' = commit_{pk}(x, r) = g^{x} \cdot h^{r} \: mod \: p \) and then verifies that \( c = c' \). Only if this is true he know that the received \( x \) is the same value that Peggy made a commitment to earlier on.
In the following we will argue about why the scheme is unconditional hiding and computational binding (actually is Pedersen's commitment scheme perfectly hiding). Perfect hiding means that the commitment \( c = commit_{pk}(x, r) = g^{x} \cdot h^{r} \: mod \: p \) reveals no information whatsoever about the value \( x \). Rewriting the commitment we have that:
\(\eqalign{ c &= g^{x} \cdot h^{r} \: mod \: p &&(h = g^{a}) \\ &= g^{x} \cdot (g^{a})^{r} \: mod \: p &&(\mbox{exponent rule}) \\ &= g^{x} \cdot g^{a \cdot r} \: mod \: p &&(\mbox{exponent rule}) \\ &= g^{x + a \cdot r} \: mod \: p }\)
I.e. the commitment \( c \) is a random element in the group \( G \): \( g \) is an element in \( G \) (remember that \( g \) generates \( G \) and therefore it also belongs to the group) and the group \( G \) is closed under multiplication, so \( g^{x + a \cdot r} \) is an element in \( G \) (think of \( g^{x + a \cdot r} \) as \( g \) multiplied with itself \( x + a \cdot r \) times). Because we multiply with the random integer \( r \) in the exponent we have that the commitment \( c \) is a totally random element in \( G \) and therefore is the scheme perfectly hiding.
The computational binding property means that only if Peggy has infinity computing power/time she is able of changing the committed value \( x \), i.e. she can compute a valid commitment \( c \) for two values \( x \) and \( x' \) where \( x \neq x' \). We can prove the computational binding property by showing that if Peggy can compute this commitment \( c \), then she can solve the discrete logarithm problem: Assume that Peggy has computed a valid commitment \( c \) for both \( x \) and \( x' \) where \( x \neq x' \), i.e. \( commit_{pk}(x, r) = c = commit_{pk}(x', r') \). We then have that:
\(\eqalign{ g^{x} \cdot h^{r} \: mod \: p &= g^{x'} \cdot h^{r'} \: mod \: p \\ g^{x} \cdot h^{r} \cdot (h^{r'})^{-1} \: mod \: p &= g^{x'} \cdot h^{r'} \cdot (h^{r'})^{-1} \: mod \: p &&(h^{r'} \cdot (h^{r'})^{-1} = 1) \\ g^{x} \cdot (g^{x})^{-1} \cdot h^{r} \cdot (h^{r'})^{-1} \: mod \: p &= g^{x'} \cdot (g^{x})^{-1} \: mod \: p &&(g^{x} \cdot (g^{x})^{-1} = 1) \\ h^{r} \cdot (h^{r'})^{-1} \: mod \: p &= g^{x'} \cdot (g^{x})^{-1} \: mod \: p &&(\mbox{exponent rule}) \\ h^{r} \cdot h^{-r'} \: mod \: p &= g^{x'} \cdot g^{-x} \: mod \: p &&(\mbox{exponent rule}) \\ h^{r - r'} \: mod \: p &= g^{x' - x} \: mod \: p \\ }\)
which implies that \( r-r' \: mod \: q = x'-x \: mod \: q \) (remember that we compute modulo \( q \) in the exponent of \( g \) because the order of \( g \) is \( q \)). Because \( r \neq r' \) we have that \( r-r' \neq 0 \) and hence \( \gcd(r-r', q)=1 \) (remember that \( \gcd(a,q)=1 \) for every integer \( a \geq 1 \) when \( q \) is a prime number) which implies that we can compute the inverse \( (r-r')^{-1} \) of \( r-r' \) with the extended Euclidean algorithm. Now by multiplying both sides of the equation \( r-r' \: mod \: q = x'-x \: mod \: q \) with \( (r-r')^{-1} \) we have that the discrete logarithm of \( h \) is \( a = (x'-x) \cdot (r-r')^{-1} \: mod \: q \) (remember that \( h = g^{a} \: mod \: p \), i.e. we have solved the discrete logarithm problem).
So why does this prove that the scheme is computational binding? We know that the discrete logarithm problem is computationally hard in the used group \( G \) (because \( G \) is a subgroup of \( \mathbb{Z}_{p}^{*} \) of order \( q \)). Therefore, because Peggy only can change her commitment by solving the discrete logarithm problem, which is computationally hard, it's also computationally hard for Peggy to change the committed value.
| Public parameters | |
| A trusted third party publish two large prime numbers \( p \) and \( q \) satisfying that \( p \: mod \: q = 1 \) and a generator \( g = g_{1}^{(p-1)/q} \: mod \: p \) of order \( q \) from the group \( \mathbb{Z}_{p}^{*} \) (where \( g_{1} \) is a generator of the group \( \mathbb{Z}_{p} \)). | |
| Initialization | |
| Victor: Chooses the secret key \( 1 \le a \le q-1 \). Computes the public key \( h = g^{a} \: mod \: p \). | |
| Victor sends the public key \( pk = h \) to Peggy. | |
| Commitment | |
| Peggy: Chooses the random integer \( 1 \le r \le q-1 \). Computes the commitment \( c = commit_{pk}(x, r) = g^{x} \cdot h^{r} \: mod \: p \) to the value \( x \) by using the public key. | |
| Peggy sends the commitment \( c \) to Victor. | |
| Opening | |
| Peggy opens the commitment by sending the values \( x \) and \( r \) to Victor. | |
| Victor: Computes the commitment \( c' = commit_{pk}(x, r) = g^{x} \cdot h^{r} \: mod \: p \). Verifies that \( c = c' \). | |
Try a demo of the commitment scheme here.
Victor chooses the two prime numbers \( p = 1447 \) and \( q = 241 \) and the generator \( g_{1} = 1252 \) of the group \( \mathbb{Z}_{1447} \). He then computes the generator \( g = g_{1}^{(p-1)/q} \: mod \: p = 1252^{(1447-1)/241} \: mod \: 1447 = 123 \) of order \( q = 241 \). Next he chooses the secret key \( a = 161 \) and computes the public key \( h = g^{a} \: mod \: p = 123^{161} \: mod \: 1447 = 944 \) which he sends to Peggy.
Peggy then chooses the random value \( r = 5 \) and makes a commitment to \( x = 52 \) by computing \( c = g^{x} \cdot h^{r} \: mod \: p = 123^{52} \cdot 944^{5} \: mod \: 1447 = 325 \) which she sends to Victor. When she wants to open the commitment again, she sends \( x = 52 \) and \( r = 5 \) to Victor. Victor then computes the commitment \( c' = g^{x} \cdot h^{r} \: mod \: p = 123^{52} \cdot 944^{5} \: mod \: 1447 = 325 \) and checks that \( c' = 325 \) is equal to \( c = 325 \).
Schnorr's sigma protocol developed by Claus P. Schnorr in 1989 is based on the discrete logarithm problem like ElGamal. The setup of the prtocol is the same as in the Schnorr signature and the Digital Signature Algorithm (DSA).
First Peggy (or a trusted third party) chooses a prime number \( q \) and computes another prime number \( p \) by \( p = 2 \cdot q + 1 \) (now \( p \: mod \: q = 1 \)) and a generator \( g \) of order \( q \) from the group \( \mathbb{Z}_{p}^{*} \). If a generator \( g \) has order \( q \), it means that \( g \) generates a subgroup \( G \) of \( \mathbb{Z}_{p}^{*} \) with \( q \) elements. Peggy can easily find \( g \) by computing \( g = g_{1}^{(p-1)/q} \: mod \: p \) where \( g_{1} \) is a generator of the group \( \mathbb{Z}_{p} \). Peggy then chooses a secret key \( w \) between \( 1 \) and \( q-1 \) and computes the public key \( h = g^{w} \: mod \: p \) which she publish. The goal of the protocol is for Peggy to convince Victor about that she is really Peggy, i.e. she is the owner of the secret key \( w \) corresponding to the public key \( h \).
Remember that the messages sent in a sigma protocol must be on the special form \( (a,e,z) \), which is called a conversation, where Peggy sends the first message \( a \), Victor sends the challenge \( e \) and Peggy response with \( z \): Peggy first chooses a random number \( r \) between \( 1 \) and \( q-1 \) and computes \( a = g^{r} \: mod \: p \) which she sends to Victor. Victor then chooses the random challenge \( e \) between \( 1 \) and \( q-1 \) and sends it to Peggy who respond with \( z = r + e \cdot w \: mod \: q \) where she uses the secret key \( w \). Finally Victor verifies Peggy's identity by checking that \( s = g^{z} \: mod \: p \) is equal to \( s' = a \cdot h^{e} \: mod \: p \).
We now need to check that Schnorr's sigma protocol satisfies completeness, special soundness and special HVZK. If Peggy know the value of \( w \) it's easy to check completeness:
\(\eqalign{ s &= g^{z} \: mod \: p &&(z = r + e \cdot w) \\ &= g^{r + e \cdot w} \: mod \: p &&(\mbox{exponent rule}) \\ &= g^{r} \cdot g^{e \cdot w} \: mod \: p &&(\mbox{exponent rule}) \\ &= g^{r} \cdot (g^{w})^{e} \: mod \: p &&(a = g^{r}, h=g^{w}) \\ &= a \cdot h^{e} \: mod \: p =s' }\)
For special soundness we have to prove that if Peggy can produce two accepting conversations \( (a,e,z) \) and \( (a,e',z') \) where \( e \neq e' \) then she can efficiently compute the secret key \( w \). Because the conversations are accepting the last check is true for both conversations, i.e. \( g^{z} \: mod \: p = a \cdot h^{e} \: mod \: p \) and \( g^{z'} \: mod \: p = a \cdot h^{e'} \: mod \: p \). Now if we divide one with the other we have that:
\(\eqalign{ \frac{g^{z}}{g^{z'}} \: mod \: p &= \frac{a \cdot h^{e}}{a \cdot h^{e'}} \: mod \: p \\ \frac{g^{z}}{g^{z'}} \: mod \: p &= \frac{h^{e}}{h^{e'}} \: mod \: p &&(\mbox{exponent rule}) \\ g^{z-z'} \: mod \: p &= h^{e-e'} \: mod \: p }\)
If we look at the exponent we have that \( z-z' \: mod \: q = e-e' \: mod \: q\) because \( g \) is an element in the group \( G \) of order \( q \). We also know that \( e \neq e' \) which implies that \( e - e' \neq 0 \) and therefore \( \gcd(e-e', q) = 1 \) (remember that \( \gcd(x,q)=1 \) for every integer \( x \geq 1 \) when \( q \) is a prime number). Because \( \gcd(e-e', q) = 1 \) we can find the inverse \( (e-e')^{-1} \) of \( e-e' \) with the extended Euclidean algorithm. When multiplying both sides of the exponent with \( (e-e')^{-1} \) we have that:
\(\eqalign{ g^{(z-z') \cdot (e-e')^{-1}} \: mod \: p &= h^{(e-e') \cdot (e-e')^{-1}} \: mod \: p &&((e-e') \cdot (e-e')^{-1} = 1) \\ g^{(z-z') \cdot (e-e')^{-1}} \: mod \: p &= h^{1} \: mod \: p }\)
Remember that \( h = g^{w} \: mod \: p \), i.e. we have efficiently computed \( w = (z-z') \cdot (e-e')^{-1} \: mod \: q \). This proves that Schnorr's sigma protocol satisfies special soundness, and hence, if Peggy doesn't know the secret key \( w \) she can maximum produce one accepting conversation, which only happens with very small probability when the prime numbers are large.
Now for special HVZK we have to build a simulator \( M \) which given \( h \) and \( e \) can produce an accepting conversation \( (a_{M},e_{M},z_{M}) \) with the same distribution as a real conversation \( (a,e,z) \) between Peggy and Victor. \( M \) is constructed as follows:
We see that \( M \) still satisfies completeness because:
\( \eqalign{ a_{M} \cdot h^{e_{M}} \: mod \: p &= (g^{z_{M}} \cdot h^{-e_{M}}) \cdot h^{e_{M}} \: mod \: p &&(h^{-e_{M}} \cdot h^{e_{M}} \: mod \: p = 1)\\ &= g^{z_{M}} \: mod \: p } \)
\( (a_{M},e_{M},z_{M}) \) also have the same distribution as \( (a,e,z) \) because:
| Public parameters | |
| A trusted third party publish two large prime numbers \( p \) and \( q \) satisfying that \( p \: mod \: q = 1 \) and a generator \( g = g_{1}^{(p-1)/q} \: mod \: p \) of order \( q \) from the group \( \mathbb{Z}_{p}^{*} \) (where \( g_{1} \) is a generator of the group \( \mathbb{Z}_{p} \)). | |
| Initialization | |
| Peggy: Chooses the secret key \( 1 \le w \le q-1 \). Computes the public key \( h = g^{w} \: mod \: p \). | |
| Peggy sends the public key \( h \) to Victor. | |
| The first message \( a \) | |
| Peggy: Chooses the random value \( 1 \le r \le q-1 \) and computes \( a = g^{r} \: mod \: p \). | |
| Peggy sends \( a \) to Victor. | |
| The challenge \( e \) | |
| Victor: Chooses randomly a challenge \( 1 \le e \le q-1 \). | |
| Victor sends the challenge \( e \) to Peggy. | |
| The response \( z \) | |
| Peggy: Computes the response \( z = r + e \cdot w \: mod \: q \). | |
| Peggy sends the response \( z \) to Victor. | |
| Verification | |
| Victor: Verifies Peggy's identity by checking that \( g^{z} \: mod \: p = a \cdot h^{e} \: mod \: p \). | |
Try a demo of the sigma protocol here.
Peggy chooses the two prime numbers \( p = 467 \) and \( q = 233 \) and the generator \( g_{1} = 439 \) of the group \( \mathbb{Z}_{467} \). She then computes the generator \( g = g_{1}^{(p-1)/q} \: mod \: p = 439^{(467-1)/233} \: mod \: 467 = 317 \) of order \( q = 233 \). Next she chooses the secret key \( w = 20 \) and computes the public key \( h = g^{w} \: mod \: p = 317^{20} \: mod \: 467 = 47 \) which she publish.
In the protocol Peggy first chooses the random value \( r = 12 \) and computes \( a = g^{r} \: mod \: p = 317^{12} \: mod \: 467 = 23 \) which she sends to Victor. Victor then chooses randomly a challenge \( e = 117 \) which he sends to Peggy who respond by computing \( z = r + e \cdot w \: mod \: q = 12 + 117 \cdot 20 \: mod \: 233 = 22 \). Finally Victor verifies Peggy's identity by checking that \( s = g^{z} \: mod \: p = 317^{22} \: mod \: 467 = 212 \) is equal to \( s' = a \cdot h^{e} \: mod \: p = 23 \cdot 159^{117} \: mod \: 467 = 212\).