Public-Key Cryptography from Classical Number Theory, with an Introduction to Lattices

Intro

Public-key cryptography, also called asymmetric cryptography, uses two different keys: a public key and a private key. The public key encrypts a message; the private key decrypts it. The public key is published, the private key kept secret. Its main uses are encryption and decryption (confidentiality), digital signatures (authentication), and key exchange (for session keys).

PS: the point of cryptography is to achieve four core properties — confidentiality, data integrity, authentication, and non-repudiation.

In symmetric cryptography, by contrast, the same key both encrypts and decrypts.

The core construction: the trapdoor one-way function

In public-key cryptography the encrypting key is public, so we need a structure under which undoing the encryption is easy for whoever holds the private key and extremely hard — effectively impossible — for anyone who does not.

The central idea is to construct a trapdoor one-way function:

Trapdoor one-way function

1. One-way: f(x) = y is very easy to compute forward, but given y it is computationally hard to find an x with f(x) = y.
2. Trapdoor: there is a special piece of secret information (the trapdoor) which, if known, lets one compute the inverse efficiently — recover x from y.

Two trapdoor one-way functions from classical number theory

1. Factoring the product of two primes

Given primes P and Q with N = P·Q, computing N is easy; given N, factoring it into P and Q is hard.

Used by RSA.

2. The discrete logarithm problem

Let b and g be elements of a finite group with bᵏ = g for some k. Given b and k, computing g is easy; given b and g, determining k is hard.

Used by Diffie–Hellman and its variant, elliptic-curve cryptography (ECC).

The RSA cryptosystem

Built on the factoring problem, RSA proceeds as follows.

Key generation:

1. Choose two distinct large primes p, q.
2. Compute the modulus n = p × q.
3. Compute Euler's totient φ(n) = (p − 1)(q − 1).
4. Choose a public exponent b with 1 < b < φ(n) and gcd(b, φ(n)) = 1.
5. Compute the private exponent a ≡ b⁻¹ mod φ(n).

The result: public key pk = (n, b); private key sk = (p, q, a).

Euler's totient φ(n) counts the integers between 1 and n that are coprime to n.

Encryption and decryption:

The ElGamal cryptosystem

Built on the discrete logarithm problem; its security rests on the hardness of computing discrete logarithms in a finite group.

• Public key: the group element g, and h = gˣ for private key x.
• Encryption: choose a random y and encrypt the message m as (c₁, c₂) = (gʸ, m·hʸ).
• Decryption: with the private key x, compute m = c₂ / c₁ˣ.

Elliptic-curve cryptography (ECC)

A variant of the discrete logarithm problem.

Defining an elliptic curve (modular arithmetic)

The solution set forms an abelian group.

The elliptic-curve discrete logarithm problem (ECDLP)

Given an elliptic curve E, a base point P, and a target point Q = kP, find the integer k with Q = kP.

Why finite fields in ECC?

In practical cryptosystems we define elliptic curves over a finite field rather than over the reals, because:

• Exactness: finite fields use exact integer arithmetic and avoid the rounding error of the reals.
• Storage: elements are fixed-length bit strings, which makes computation efficient.
• Security: finite fields make the discrete logarithm problem harder and avoid the weaknesses that come with the continuity of the reals.
• Speed: addition and multiplication are fast, suited to real use.

The finite fields in common use:

• prime fields GF(p), with p a large prime;
• binary extension fields GF(2ⁿ), especially suited to hardware.

The limits of number-theoretic public-key cryptography

• The quantum threat: Shor's algorithm breaks the classical number-theoretic problems in polynomial time.
• Key growth: raising the security level demands exponential growth in key size, which hurts efficiency.
• A narrow base: it rests on only a few number-theoretic problems (factoring, discrete logarithms).
• A theoretical bottleneck: there is a shortage of new, reliable hard problems to build on.

The complexity of the classical problems

• Integer factorization: not proven NP-complete. The best classical algorithms run in sub-exponential time, but Shor's quantum algorithm solves it in polynomial time.
• The discrete logarithm problem (DLP): not NP-complete, but regarded as computationally hard. Sub-exponential on classical machines; likewise polynomial for Shor's algorithm.
• The elliptic-curve discrete logarithm problem (ECDLP): harder than the general DLP — the best known algorithms are still exponential — yet equally exposed to quantum attack.

Introducing lattices

Lattice problems: complexity and use

• Shortest vector problem (SVP): find the shortest non-zero vector in a lattice. Proven NP-hard under certain norms; its approximate versions stay hard as well.
• Closest vector problem (CVP): given a target point, find the nearest lattice point. NP-hard, and often the basis of decryption algorithms.
• Learning with errors (LWE): solve the linear system As + e = b (mod q) for s, given A and b. It is hard on average, rests on worst-case lattice problems, and resists quantum attack well.
• Short integer solution (SIS): given a random matrix A, find a short vector x with Ax = 0 (mod q). Dual to LWE, with the same quantum resistance and average-case hardness.

Why lattices

Unlike classical number theory, average-case hardness in lattice problems reduces to worst-case hardness, which gives a stronger security guarantee — a sharp contrast with the average-to-special-case reductions of traditional cryptography. Lattices also supply a rich family of hard problems (SVP, CVP, LWE, SIS, and more), which makes the design of cryptographic schemes far more flexible.