Problem 14 - An Introduction to Mathematical Cryptography

Question

Prove that each of the following maps is a group homomorphism. (a) The \(\operatorname{map} \phi: \mathbb{Z} \rightarrow \mathbb{Z} / N \mathbb{Z}\) that sends \(a \in \mathbb{Z}\) to \(a \bmod N\) in \(\mathbb{Z} / N \mathbb{Z}\). (b) The map \(\phi: \mathbb{R}^{*} \rightarrow \mathrm{GL}_{2}(\mathbb{R})\) defined by \(\phi(a)=\left(\begin{array}{cc}a & 0 \\ 0 & a^{-1}\end{array}\right)\). (c) The discrete logarithm map \(\log _{g}: \mathbb{F}_{p}^{*} \rightarrow \mathbb{Z} /(p-1) \mathbb{Z}\), where \(g\) is a primitive root modulo \(p\).

Step-by-Step Solution

Answer

All maps are group homomorphisms as they respect the group operation.

Step 1: Understanding Group Homomorphism

A group homomorphism is a function between two groups that respects the group operation, which means if you have a homomorphism \( \phi: G \to H \) and elements \( a, b \in G \), then \( \phi(ab) = \phi(a)\phi(b) \). We will verify this property for all the given maps.

Step 1: Verify Homomorphism for \( \phi: \mathbb{Z} \to \mathbb{Z}/N\mathbb{Z} \)

Consider the map \( \phi(a) = a \mod N \). For \( a, b \in \mathbb{Z} \), we check that \( \phi(a + b) = (a + b) \mod N \) which simplifies to \( (a \mod N + b \mod N) \mod N = \phi(a) + \phi(b) \mod N = \phi(a) + \phi(b) \). Thus, \( \phi \) is a group homomorphism.

Step 2: Check Homomorphism for \( \phi: \mathbb{R}^{*} \to \mathrm{GL}_{2}(\mathbb{R}) \)

Here, \( \phi(a) = \begin{pmatrix} a & 0 \ 0 & a^{-1} \end{pmatrix} \). We want \( \phi(ab) = \phi(a) \phi(b) \). Computing \( \phi(ab) \) gives: \[ \begin{pmatrix} ab & 0 \ 0 & (ab)^{-1} \end{pmatrix} = \begin{pmatrix} a & 0 \ 0 & a^{-1} \end{pmatrix}\begin{pmatrix} b & 0 \ 0 & b^{-1} \end{pmatrix} = \begin{pmatrix} ab & 0 \ 0 & a^{-1}b^{-1} \end{pmatrix} \]. Therefore, \( \phi \) is a homomorphism.

Step 3: Verify Homomorphism for Discrete Log Map \( \log_g: \mathbb{F}_p^{*} \to \mathbb{Z}/(p-1)\mathbb{Z} \)

The function \( \log_g(x) \) gives the power to which \( g \) must be raised to obtain \( x \). For \( x, y \in \mathbb{F}_p^{*} \), \( g^{\log_g(xy)} = xy = g^{\log_g(x)}g^{\log_g(y)} \). Taking logs, \( \log_g(xy) = \log_g(x) + \log_g(y) \mod (p-1) \). Thus \( \log_g \) is a homomorphism.

Key Concepts

Discrete Logarithm

The discrete logarithm is an intriguing concept used in number theory, especially in cryptography. It involves taking a power of a fixed number, called a generator or a primitive root, and reversing the operation to find what the power must have been. In formal terms, for a group with a generator \( g \) and an element \( x \), the discrete log is the exponent \( k \) such that \( g^k \equiv x \mod p \), and this gives us \( \log_g(x) = k \).

• Important for cryptographic algorithms like Diffie-Hellman key exchange and ElGamal encryption.
• The problem is "hard"—believed to require a long time to solve, providing security.
• Relies on the idea that while computing \( g^k \mod p \) is simple, finding \( k \) is not.

When proving the discrete logarithm map is a homomorphism, we examine the property that \( \log_g(xy) = \log_g(x) + \log_g(y) \mod (p-1) \), ensuring the structure is preserved under multiplication and addition in modulo arithmetic.

Primitive Roots

Primitive roots are fundamental in the study of number theory, particularly within modular arithmetic. A primitive root mod \( n \) is a number \( g \) such that every number co-prime to \( n \) can be expressed as a power of \( g \). In simpler terms, it means that \( g \) can generate all the numbers in a given group through exponentiation.

• Exist only for certain values of \( n \). For instance, every prime number \( p \) has primitive roots.
• Defines a cyclic group of units mod \( n \).
• Helps in simplifying the computation of powers modulo \( n \).

For example, if \( g \) is a primitive root mod \( p \), then \( g^k \equiv a \mod p \) has solutions for each \( a \) that is coprime with \( p \). This property makes primitive roots vital in cryptography, as they are used to construct cyclic groups for secure operations.

Modular Arithmetic

Modular arithmetic is like regular arithmetic but with a catch—it wraps around upon reaching a certain value, much like a clock. When calculating "mod" operations, the result is the remainder after division. If \( a \equiv b \mod n \), it means \( a \) and \( b \) have the same remainder when divided by \( n \).

• Useful in computer science for hash functions and algorithms due to its predictable cycle behavior.
• Key for cryptography, especially in modulus operations for keys and encryption.
• Involves arithmetic operations addition, subtraction, multiplication, and sometimes division.

In the context of proving group homomorphisms, modular arithmetic helps us verify if certain properties hold. For instance, for an integer \( a \) mapped to \( a \mod N \) in \( \mathbb{Z}/N\mathbb{Z} \), showing \( (a + b) \mod N = (a \mod N + b \mod N) \mod N \) effectively proves the homomorphic property.