Groups

Introduction
Groups And Abelian Groups
- Basic Definitions
- Example of Groups
Cyclic groups

Introduction

This document provides a simple introduction to group theory and its key role in cryptography. Group theory is essential for building many cryptographic systems, including encryption, digital signatures, and zero-knowledge proofs (ZKPs). These mathematical structures ensure that operations like encryption and authentication are secure and reliable.

We’ll start by defining groups, abelian groups, and cyclic groups, which are the backbone of many cryptographic algorithms. For example, the security of RSA encryption relies on group properties, and protocols like ECDSA use elliptic curves, which are based on group theory. Cyclic groups are crucial for creating secure ZKP systems like the Schnorr protocol, which is widely used for authentication.

Throughout the article, we’ll highlight how these abstract mathematical concepts directly contribute to secure communication in cryptography.

Groups And Abelian Groups

In cryptography, group theory plays a fundamental role, especially in modern public-key cryptography and protocol design. A group is an algebraic structure consisting of a set of elements and a binary operation that satisfies closure, associativity, identity element, and invertibility. Below are some key applications of group theory in cryptography:

Underpins many widely used signature schemes, such as RSA and ECDSA.
Many ZKP protocols use group operations, particularly cyclic groups, to construct secure proof systems. For instance, the Schnorr protocol is a zero-knowledge proof system based on cyclic groups and the discrete logarithm problem, widely used for authentication and privacy-preserving systems.

Let's begin with a definition and then some examples.

Basic Definitions

Binary operation: Let $G$ be a set. A binary operation is a map of sets: $\circ : G \times G \to G .$ For ease of notation we write $\circ (a, b) = a \circ b$ , for all $a, b$ in $G$ . Any binary operation on $G$ gives a way of combining elements. If $G = Z$ (the set of integers $Z$ , so denoted because the German word for numbers is Zahlen) then $+$ and $\times$ are natural examples of binary operations.

Group: A group is a set $G$ , together with a binary operation $\circ$ , such that the following hold:

(Associativity):The operation is associative;that is, $(a \circ b) \circ c = a \circ (b \circ c)$ for all $a, b, c$ in $G$ .
(Existence of identity): There is an element $e$ (called the identity) in $G$ such that $a \circ e = e \circ a = a$ for all $a$ in $G$ .
(Existence of inverses): For each element $a$ in $G$ , there is an element $b$ in $G$ (called an inverse of $a$ and denoted by $a^{- 1}$ ) such that $a \circ b = b \circ a = e$ .

Note

If $a$ is the $in v erse$ of $b$ , then $b$ is the $in v erse$ of $a$ .
The group we have just defined may be represented by the symbol $(G, \circ)$ . This notation makes it explicit that the group consists of the $se t$ $G$ and the $bina ry o p er a t i o n \circ$ .(Remember that, in general, there are other possible operations on $G$ , so it may not always be clear which is the group's operation unless we indicate it.) If there is no danger of confusion, we shall denote the group simple with the letter $G$ .

Abelian group: If the operation is $co mm u t a t i v e$ , that is the $g ro u p$ has the property that $a \circ b = b \circ a$ for every pair of elements a and b, we say the group is $A b e l ian$ .

Note

When cryptographers refer to " $g ro u p s$ ", they typically mean " $A b e l ian g ro u p s$ (a.k.a $C o mm u t a t i v e g ro u p s$ )". From now on, when we mention $g ro u p s$ , we will assume they are $A b e l ian g ro u p s$ by default.

Example of Groups

The integers $Z = {..., - 1, 0, 1, 2, ...}$ form a group under the operation of addition. The binary operation on two integers $m, n$ in $Z$ is just their sum. Since the integers under addition already have a well-established notation, we will use the operator $+$ instead of $\circ$ ; that is, we shallwrite $m + n$ instead of $m \circ n$ .The identity is 0, and the inverse of $n$ in $Z$ is written as $- n$ instead of $n^{- 1}$ .
The integers mod $n$ form a group under additon modulo $n$ .Consider $Z_{5}$ , consisting of the equivalence classes of the integers 0, 1, 2, 3, and 4. We define the group operation on $Z_{5}$ by modular addition. We write the binary operation on the group additively; that is, we write $m + n$ . The element 0 is the identity of the group and each element in $Z_{5}$ has an inverse. For instance, $3 + 2 = 2 + 3 = 0$ .
Not every set with a binary operation is a group. For example, if we let modular multiplication be the binary operation on $Z_{n}$ , then $Z_{n}$ fails to be a group. The element 1 acts as a group identity since $1 \cdot k = k \cdot 1 = k$ for all $k$ in $Z_{n}$ .Even if we consider the set $Z_{n} \ {0} = {1, 2, 3, ..., n - 1}$ , we still may not have a group. For instance, let 2 in $Z_{6}$ .Than 2 has no multiplicative inverse since $0 \cdot 2 = 0 1 \cdot 2 = 2 2 \cdot 2 = 4 3 \cdot 2 = 6 4 \cdot 2 = 8 5 \cdot 2 = 10$

Note

We can use exponential notation for groups just as we do in ordinary algebra. If $G$ is a group and $g \in G$ , then we define $g^{0} = e$ . For $n \in N$ , we define $g^{n} = n times g \circ g \circ \dots \circ g$ and $g^{- n} = n times g^{- 1} \circ g^{- 1} \circ \dots \circ g^{- 1}$

When dealing with additive abelian groups, we use additive notation for group operations and denote the identity element by $o$ instead of $e$ . We define: $[0] g = o$ , $[n] g = n times g + g + \dots + g$ and $[- n] g = n times (- g) + (- g) + \dots + (- g)$

Cyclic groups

A group $G$ is called cyclic if there exists an element $g \in G$ such that every element $a \in G$ can be written as $g^{n}$ (for some integer $n$ ).In other words: $G = g^{n} : n \in Z$ where $g^{n}$ means applying the group operation to $g$ $n$ times. In this case $g$ is a $g e n er a t or$ of $G$ .

ZK Book

Groups

Introduction

Groups And Abelian Groups

Basic Definitions

Example of Groups

Cyclic groups