Abstract Algebra in Modern Cryptography

Groups, rings, and fields made more sense to me once I started reading about cryptography. During Algebra at NTNU, I’d often wondered what I would use them for. Cryptography gave me concrete examples of why those definitions mattered.

The basics

A group \((G, \cdot)\) is a set with an operation that satisfies four conditions. Combining two elements gives another element in the set, and changing the grouping of an expression doesn’t change its result. There is also an identity element, which leaves other elements unchanged, and every element has an inverse. These conditions give us a common way to study operations that might otherwise look unrelated.

A homomorphism maps one group to another while preserving the operation. Applying the map after combining two elements gives the same result as mapping them first and then combining them:

\[\phi : G \rightarrow H \text{ such that } \phi(a \cdot b) = \phi(a) \star \phi(b)\]

This idea is useful in cryptography because it gives us a way to relate operations on messages to operations on ciphertexts. A Python wrapper for such a map might look like this, although the wrapper itself doesn’t check that the map preserves the operation:

1
2
3
4
5
6
7
8
9
10
11

from typing import TypeVar, Generic, Callable

T = TypeVar('T')
S = TypeVar('S')

class Homomorphism(Generic[T, S]):
    def __init__(self, mapping_func: Callable[[T], S]):
        self.mapping_func = mapping_func
        
    def map(self, element: T) -> S:
        return self.mapping_func(element)

Computing on encrypted data

Homomorphic encryption allows certain calculations on encrypted values. For a scheme that supports both addition and multiplication, the relationship can be written schematically as:

\[E(x + y) = E(x) \oplus E(y) \quad \text{and} \quad E(x \cdot y) = E(x) \otimes E(y)\]

The operations on the right happen on ciphertexts, and decrypting the result should recover the corresponding calculation on the original values. This small example illustrates the additive relationship, but it is not secure encryption:

1
2
3
4
5
6
7
8
9
10
11
12

from dataclasses import dataclass

@dataclass
class HomomorphicCipher:
    modulus: int
    key: int
    
    def encrypt(self, message: int) -> int:
        return (message * self.key) % self.modulus
    
    def bulk_add(self, ciphertexts: list[int]) -> int:
        return sum(ciphertexts) % self.modulus

Schemes such as BFV, BGV, and CKKS need much more machinery to make this useful and secure. The toy example only illustrates the property we want to preserve.

Why public-key crypto works at all

Public-key cryptography often relies on problems that are easy to compute in one direction and difficult to reverse without extra information. One example is the discrete logarithm problem:

\[\text{Given } g^x \equiv h \pmod{p}, \text{ find } x\]

Computing \(g^x \bmod p\) is efficient, while recovering \(x\) can be difficult when the group and its parameters are chosen appropriately. Cryptographic protocols use that difference to let people exchange information without also revealing their private keys.

RSA is related to the difficulty of factoring large semiprimes, while elliptic curve cryptography uses the discrete logarithm problem in elliptic curve groups. The algebra helps us describe these constructions and reason about their properties.

Reading cryptography papers

When I went back to quotient groups and the other material from the course, I had a better reason to care about the details. The definitions were giving me a way to follow cryptography papers that I couldn’t have read before.