Abstract Algebra in Modern Cryptography

, ,

When I first took Algebra at NTNU, I had no idea why we were spending weeks on groups, rings, and fields. I kept asking myself when I’d actually use any of this. The answer turned out to be “constantly,” once I started reading how cryptography is actually built.

The basics

A group \((G, \cdot)\) is a set with an operation that has to be closed (the result stays in the set), associative (grouping doesn’t matter), have an identity element, and have an inverse for every element. That’s the whole definition. Once you have those four properties, all sorts of useful things become provable about the structure.

Where it gets interesting is in maps between groups that preserve their structure. Those are called homomorphisms:

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

Structure preservation sounds abstract until you realize it’s the property that lets you do useful things to ciphertext without ever decrypting it. A simple way to encode the idea:

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 lets you do math on encrypted values without ever decrypting them. The first time I read about it I assumed there had to be a catch. The math turns out to use ring homomorphisms where both addition and multiplication are preserved:

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

Once you spell that out, “computing on encrypted data” becomes the natural consequence of preserving structure. Here’s a toy version that handles the additive case:

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

Real schemes like BFV, BGV, and CKKS add a lot more machinery on top, but the algebraic core is the same.

Why public-key crypto works at all

Most public-key cryptography is built on problems that are easy to compute in one direction and very hard to reverse. The discrete logarithm problem is one of the canonical examples:

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

Computing \(g^x \bmod p\) is fast. Recovering \(x\) from \(g\), \(h\), and \(p\) alone is computationally brutal for large primes. That asymmetry is the whole reason your encrypted traffic stays encrypted.

The same shape shows up in other places. RSA leans on the difficulty of factoring large semiprimes. Elliptic curve cryptography leans on the discrete log problem in elliptic curve groups. Different groups, same trick.

Looking back

After a lot of late nights in the NTNU library staring at quotient groups, I started recognizing the same structures everywhere. What started as an abstract math course ended up being the language you need to read most cryptography papers. Pure math and applied cryptography turn out to be the same toolkit pointed at different problems. That’s the part of the connection I find most satisfying.