This article is part five of a series of increasingly advanced math prerequisite concepts required to understand how zero-knowledge proofs actually work. It explains what cyclic groups are and why, due to the hardness of the discrete logarithm problem, they are commonly used in cryptography.
Before reading this one, you should have already read the previous four and therefore have a working knowledge of:
A cyclic group is a group with an element, known as the generator point $g$, such that every element in the group can be “generated” by repeatedly applying the group operation to $g$.
To recap, a group is a set $G$ with a single binary operator (referred to as the group operation and denoted $*$) that has the following properties:
A group $G$ is called cyclic if there exists an element $g∈G$ such that, for some integer $n$, every element in $G$ can be written as:
$$\underbrace{g \times g \times ... \times g}_{\text{n times}}= g^n$$
for multiplicative groups (repeated scalar multiplication is scalar exponentiation).
And:
$$\underbrace{g + g + ... + g}_{\text{n times}}= g \times n$$
for additive groups (repeated addition is scalar multiplication).
Note that **all cyclic groups are Abelian groups (commutative groups),** but not all Abelian groups are cyclic.
Not every element in a cyclic group is a generator, and not every group with a prime modulus has a generator point that is simple to find.
In the multiplicative group $\mathbb{Z}_p^*$, an element $g$ is a generator if and only if:
$$g^k \not\equiv 1 \pmod{p} \quad \text{for all} \; k \; \text{where} \; 1 \leq k < p-1$$
This means that to verify if an element $g$ is a generator point, we need to check that that element $g$ raised to any power less than $p−1$, and more than or equal to $1$, will not equal $1$. Only when raised to the power of $p−1$ will it equal $1$.
Checking this for every possible $g$ would be inefficient, so, in practice, we can use a more efficient method based on the factorization of $p-1$: If $p-1 = q_1^{e_1} \times q_2^{e_2} \times ... \times q_t^{e_t}$ where $q_i$ are distinct prime factors of $p-1$, then $g$ is a generator if and only if:
$$g^{(p-1)/q_i} \not\equiv 1 \pmod{p}$$
For all prime factor indices $i$ from $1$ to $t$ where $t$ is the number of prime factors.
For example: in $\mathbb{Z}_{11}^*$, since $11-1 = 10 = 2 \times 5$ (it has two prime factors so $t=2$), we only need to check that:
to determine if $g$ is a generator. This significantly reduces the number of checks needed to verify if an element is a generator.
The full multiplicative group $\mathbb{Z}_p^*$ has order (number of elements) $p-1$, which is rarely prime. However, cryptographic applications often use subgroups of prime order for enhanced security and efficiency.
If $p-1 = qr$, where $q$ is a large prime factor of $p-1$ and $r$ is the cofactor, then we can find a subgroup of order $q$ within $\mathbb{Z}_p^$.*
For example, for the following $p$, $q$, and $r$ values:
An element $h \in \mathbb{Z}_p^*$ is the generator for this subgroup if:
$h = g^r \mod p$, where $g$ is a generator of the full group $\mathbb{Z^*_p}$.
Working in these prime-order subgroups offers several advantages:
This concept of prime-order subgroups extends to other cyclic groups used in cryptography, including elliptic curve groups (the subject of the next article).
A group being cyclic means that calculations can be simplified.
The multiplicative group of any finite field $\mathbb{F}_p$ is a cyclic group of order $p−1$. Meaning there is a generator $g$ in $\mathbb{F}_p$ such that every non-zero element in $\mathbb{F}_p$ can be expressed as $g^k$ for some integer $k$.
This allows multiplication and exponentiation to be reduced to operations on exponents. For instance, instead of multiplying two elements $a$ and $b$ directly, if it is known that $a = g^k$ and $b = g^m$, then their product is
$$a \times b = g^k \times g^m = g^{k+m}$$
Cyclic groups are fundamental in cryptography and zero-knowledge proofs because certain problems that are easy in infinite fields become computationally difficult when restricted to finite fields. A key example is the discrete logarithm problem (DLP).
The discrete logarithm problem asks:
Given a generator $g$ and an element $h$, find an integer $x$ such that applying the group operation $x$ times to $g$ results in $h$.
In a finite multiplicative cyclic group $\mathbb{Z^*_p}$, this means finding $x$ such that:
$$g^x\equiv h\mod(p)$$
Here, $g$ is the generator of the cyclic group, and $h$ is the result of raising $g$ to the power of $x$, followed by taking the modulus $p$. The task is to determine $x$ given $g$ and $h$, which is computationally difficult when $p$ is large.
Unlike standard logarithms, where we can take the natural log of both sides, the modular nature of cyclic groups breaks the properties that make logarithms easy to compute in regular arithmetic.
There's no direct "inverse function" we can apply because the modular nature creates a discrete, seemingly random relationship between inputs and outputs that doesn't preserve the mathematical properties we exploit when computing standard logarithms.
This is why we resort to algorithms like baby-step giant-step or Pollard's rho, which essentially search for the correct $x$ rather than calculating it directly.
As $p$ grows larger, the search space expands exponentially and quickly becomes computationally infeasible, even for powerful computers.
In additive cyclic groups (such as elliptic curve groups which is the subject of a future article), the problem is instead to find $x$ such that:
$$x \cdot g = h$$
Where $g$ is again a generator point, $x$ is the scalar we are attempting to find, and $h$ is a set element, e.g., an elliptic curve point.
Since elliptic curve groups require a different mathematical framework, we will focus on the multiplicative case here and return to the additive version in our discussion on elliptic curve cryptography.
Example: In the finite field $\mathbb{F}_p^*$, given $g$ and $h$, the problem is to find $x$ such that: $2^x\equiv 23 \mod(p)$
While computing the power is an efficient calculation, the reverse operation of finding the logarithm, finding $x$ given $g$ (2) and $h$ (23) , is considered hard, especially as $p$ becomes large.
The DLP's computational difficulty ensures that an attacker cannot easily derive the private key from the public key in protocols like Diffie-Hellman, providing security in digital communications.
DLP also allows us to hide secret information!
We can “hide” our secret $x$ in a cyclic group element $h = g^x \pmod p$! And prove properties about our secret $x$ by performing computations on $h$, without ever revealing $x$ itself. This is possible due to the homomorphic properties of cyclic groups and the subject of the next article.
Let's work through a small example to illustrate how the generator point generates all the points in a cyclic group.
Consider the multiplicative group $\mathbb{Z}_{11}^*$ (integers from 1 to 10 under multiplication modulo 11). Let's verify that $g = 2$ is a generator of this group by computing all powers:
$2^1 \pmod{11} = 2$
$2^2 \pmod {11} = 4$
$2^3 \pmod {11} = 8$
$2^4 \pmod {11} = 5 (since 16 \pmod {11} = 5)$
$2^5 \pmod {11} = 10 (since 32 \pmod {11} = 10)$
$2^6 \pmod {11} = 9 (since 64 \pmod {11} = 9)$
$2^7 \pmod {11} = 7 (since 128 \pmod {11} = 7)$
$2^8 \pmod {11} = 3 (since 256 \pmod {11} = 3)$
$2^9 \pmod {11} = 6 (since 512 \pmod {11} = 6)$
$2^{10} \pmod {11} = 1 (since 1024 \pmod {11} = 1)$
We've generated all non-zero elements in $\mathbb{Z}_{11}$, confirming that $2$ is indeed a generator.
Now, back to the discrete logarithm problem: if we're given $g = 2$ and $h = 9$, we need to find $x$ such that $2^x \equiv 9 \pmod{11}$. From our calculations above, we can see that $x = 6$. With small moduli like $11$, we can find the answer by exhaustive search, but with cryptographically-sized moduli (e.g., 2048 bits, which creates a search space of 2^2048 possibilities), this approach becomes computationally infeasible. It would be impossible to calculate every single point to find the $x$ corresponding to a given $h$ value.
Cyclic groups and the discrete logarithm problem form the backbone of many cryptography and zero-knowledge proof systems: complex statements can be reduced to proving knowledge of values that satisfy specific relations in cyclic groups, where the DLP ensures that these values remain hidden.
This allows provers to demonstrate they know a secret (like a discrete logarithm) without revealing any information about the secret itself.
The mathematical properties of cyclic groups make them ideal for constructing these proofs.
