Textbook lessons with runnable snippets.

Divisibility is one of the most fundamental concepts in number theory and
forms the basis for understanding modular arithmetic, which is essential
for modern cryptography.

Mathematical Background:
We say that an integer a divides an integer b (written as a | b) if
there exists an integer k such that b = a * k.

For example:
• 3 | 12 because 12 = 3 * 4
• 5 | 0 because 0 = 5 * 0
• 1 | n for any integer n

Key properties of divisibility:

1. Reflexivity: a | a (every number divides itself)
2. Transitivity: if a | b and b | c, then a | c
3. Linear combinations: if a | b and a | c, then a | (bx + cy) for any x, y

Why This Matters for Cryptography:
Divisibility relationships underpin:
• RSA key generation (finding large primes)
• Modular arithmetic operations
• Group structure in elliptic curve cryptography
• Hash functions and message authentication

The Integer class provides a divides method that checks if the integer
divides another number. Note: a.divides(b) returns true if a | b.

The divisors of a number are all positive integers that divide it evenly.
Understanding divisors is crucial for:

• Factoring large numbers (the basis of RSA security)
• Computing Euler's totient function
• Analyzing group structures

A perfect number equals the sum of its proper divisors (divisors excluding itself).
The first few perfect numbers are: 6, 28, 496, 8128

Perfect numbers have fascinating connections to Mersenne primes:
If 2^p - 1 is prime (a Mersenne prime), then 2^(p-1) * (2^p - 1) is perfect.

Common divisors of two numbers are integers that divide both.
The greatest common divisor (GCD) is the largest such divisor.

This concept is fundamental to:

• Reducing fractions to lowest terms
• Computing modular inverses
• Key generation in cryptographic protocols

The Fundamental Theorem of Arithmetic states that every integer > 1
can be uniquely expressed as a product of primes.

This is the mathematical foundation for:

• RSA encryption (difficulty of factoring large semiprimes)
• Pollard's rho algorithm
• Index calculus methods

There are efficient divisibility rules for small primes that don't require
full division. These are useful for quick checks.

EXERCISE: Without using the divides() method or the % operator,
implement a function that checks if a divides b using only
addition and subtraction.

Hint: Keep subtracting a from b until you reach 0 or go negative.

Two numbers are coprime (relatively prime) if their GCD is 1.
This is essential in cryptography:

• RSA requires e and phi(n) to be coprime
• Modular inverses only exist for coprime numbers

The Extended Euclidean Algorithm is one of the most important algorithms
in cryptography. It not only computes gcd(a, b) but also finds integers
s and t such that: gcd(a, b) = sa + tb (Bezout's Identity)

Mathematical Background:
Bezout's Identity: For any integers a and b, there exist integers s and t
such that: gcd(a, b) = sa + tb

The coefficients s and t are called Bezout coefficients.
They are not unique, but the extended Euclidean algorithm finds one pair.

Why This Matters for Cryptography:
The Extended Euclidean Algorithm is THE fundamental algorithm for:
• Computing modular inverses (essential for RSA decryption)
• Solving linear Diophantine equations
• Chinese Remainder Theorem computations
• Lattice basis reduction

The xgcd() function returns [g, s, t] where:
g = gcd(a, b)
g = sa + tb

Let's trace through the extended Euclidean algorithm to see how
the Bezout coefficients are computed.

The modular inverse of a modulo n exists iff gcd(a, n) = 1.
When it exists, we can find it using the extended Euclidean algorithm:

If gcd(a, n) = 1 = sa + tn
Then sa = 1 - tn = 1 (mod n)
So s is the modular inverse of a modulo n.

In RSA, the private exponent d is the modular inverse of e mod phi(n).
This is computed using the extended Euclidean algorithm.

A linear Diophantine equation has the form: ax + by = c
where a, b, c are integers and we seek integer solutions (x, y).

Solution exists iff gcd(a, b) divides c.
If (x0, y0) is a particular solution, general solution is:
x = x0 + (b/g) * k
y = y0 - (a/g) * k
for any integer k.

For gcd(a, b) = g = sa + tb, the coefficients (s, t) are not unique.
All solutions are: (s + kb/g, t - ka/g) for any integer k.

The IntegerMod class provides an inv() method that uses
the extended Euclidean algorithm internally.

EXERCISE: Implement the extended Euclidean algorithm yourself.
Return [gcd, s, t] such that gcd = sa + tb.

Montgomery's trick allows computing n modular inverses with only
ONE extended GCD computation plus O(n) multiplications.

This is useful when you need many inverses modulo the same number.

The Greatest Common Divisor is arguably the most important function in
computational number theory. It's used everywhere in cryptography, from
computing modular inverses to determining if numbers are coprime.

Mathematical Background:
The GCD of two integers a and b, denoted gcd(a, b), is the largest
positive integer that divides both a and b.

Key properties:
• gcd(a, b) = gcd(b, a) (commutative)
• gcd(a, 0) = |a| (identity)
• gcd(a, b) = gcd(a - b, b) if a > b (subtraction property)
• gcd(a, b) = gcd(a mod b, b) (Euclidean property)

The Euclidean Algorithm:
The Euclidean Algorithm (c. 300 BCE) is one of the oldest known algorithms.
It computes gcd(a, b) by repeatedly applying: gcd(a, b) = gcd(b, a mod b)
until one operand becomes zero.

Time complexity: O(log(min(a, b)))

Why This Matters for Cryptography:
• RSA: Finding e coprime to phi(n)
• Extended GCD: Computing modular inverses
• Pollard's rho: Factoring based on GCD computations
• Lattice cryptography: Basis reduction algorithms

The gcd() function computes the greatest common divisor.
Results are always non-negative.

Let's trace through the Euclidean Algorithm step by step.
This helps understand why the algorithm works and is so efficient.

The GCD can also be computed by finding common prime factors.
For each prime p: the power of p in gcd(a,b) is min(power in a, power in b)

This method is educational but inefficient for large numbers.
The Euclidean algorithm is much faster in practice.

The gcd() function can take an array to compute the GCD of multiple numbers.
gcd(a, b, c) = gcd(gcd(a, b), c)

Two numbers are coprime if their GCD is 1.
This is crucial in cryptography:

• RSA: e must be coprime to phi(n)
• Modular inverse exists iff gcd(a, n) = 1

In RSA, we need to find e coprime to phi(n) = (p-1)(q-1).
Let's simulate finding such an e.

The Euclidean Algorithm is remarkably efficient.
Worst case: consecutive Fibonacci numbers (requires the most steps).

The Binary GCD (Stein's Algorithm) uses only subtraction, halving,
and comparisons - no division. This can be faster on some hardware.

Key observations:

• gcd(2a, 2b) = 2 * gcd(a, b)
• gcd(2a, b) = gcd(a, b) if b is odd
• gcd(a, b) = gcd(|a-b|, min(a,b)) if both odd

EXERCISE: Implement the Euclidean algorithm yourself.
Then verify it matches the library's gcd() function.

If two RSA moduli share a prime factor, we can factor both instantly
using GCD! This has been used to break real-world RSA keys with poor
random number generation.

The Least Common Multiple complements the GCD. While GCD finds the largest
common divisor, LCM finds the smallest common multiple.

Mathematical Background:
The LCM of two integers a and b, denoted lcm(a, b), is the smallest
positive integer that is divisible by both a and b.

Key relationship with GCD:
lcm(a, b) * gcd(a, b) = |a * b|

Therefore: lcm(a, b) = |a * b| / gcd(a, b)

Properties:
• lcm(a, b) = lcm(b, a) (commutative)
• lcm(a, 1) = |a| (identity)
• lcm(a, 0) = 0 (convention)
• lcm(a, a) = |a|
• lcm(a, b) >= max(|a|, |b|)

Why This Matters for Cryptography:
• Carmichael's lambda function uses LCM
• Key scheduling in block ciphers
• Order calculations in groups
• Chinese Remainder Theorem applications

The lcm() function computes the least common multiple.
Results are always non-negative.

The key identity: lcm(a, b) * gcd(a, b) = |a * b|

This is why we compute: lcm(a, b) = |a * b| / gcd(a, b)

For each prime p: the power of p in lcm(a,b) is max(power in a, power in b)
Compare this to GCD where we take the min.

The lcm() function can take an array to compute the LCM of multiple numbers.
lcm(a, b, c) = lcm(lcm(a, b), c)

When gcd(a, b) = 1 (coprime), then lcm(a, b) = |a * b|
This is because there are no shared prime factors.

Carmichael's lambda function lambda(n) is defined using LCM.
It's the smallest positive integer m such that a^m = 1 (mod n)
for all a coprime to n.

For n = p1^e1 * p2^e2 * ... * pk^ek:
lambda(n) = lcm(lambda(p1^e1), lambda(p2^e2), ..., lambda(pk^ek))

Where:
lambda(2) = 1
lambda(4) = 2
lambda(2^e) = 2^(e-2) for e >= 3
lambda(p^e) = p^(e-1) * (p-1) = phi(p^e) for odd prime p

When adding fractions, we need a common denominator.
The LCM of denominators gives the smallest such denominator.

LCM is used to find when periodic events coincide.
This is important in scheduling, signal processing, and cryptography.

In a group, if elements a and b have orders m and n respectively,
and they commute, then the order of ab divides lcm(m, n).

For the group (Z/nZ)*, the exponent (smallest e where a^e = 1 for all a)
is exactly the Carmichael function lambda(n).

EXERCISE: Implement LCM using the GCD-LCM relationship.
Remember: lcm(a, b) = |a * b| / gcd(a, b)

Some key schedules use LCM-related properties.
Here's a simple example: finding when two LFSR sequences align.

Modular arithmetic is the foundation of modern cryptography. Understanding
congruence relations and equivalence classes is essential for working with
finite fields, RSA, elliptic curves, and virtually every cryptographic system.

Mathematical Background:
We say a is congruent to b modulo n (written a = b (mod n)) if n divides (a - b).
Equivalently: a = b (mod n) iff a mod n = b mod n

Properties of congruence:
• Reflexive: a = a (mod n)
• Symmetric: if a = b (mod n), then b = a (mod n)
• Transitive: if a = b (mod n) and b = c (mod n), then a = c (mod n)

These properties make congruence an equivalence relation, which partitions
the integers into equivalence classes.

Why This Matters for Cryptography:
• All arithmetic in RSA is done modulo n = pq
• Elliptic curve operations are done modulo a prime p
• Hash functions produce outputs in a fixed range (equivalence class representatives)
• Finite field arithmetic is fundamentally about equivalence classes

Two integers are congruent modulo n if they have the same remainder
when divided by n, or equivalently, if their difference is divisible by n.

The equivalence class [a]_n is the set of all integers congruent to a mod n.
[a]_n = {..., a-2n, a-n, a, a+n, a+2n, ...}

There are exactly n distinct equivalence classes: [0], [1], ..., [n-1]

Z/nZ is the set of equivalence classes {[0], [1], ..., [n-1]} with
arithmetic operations defined on representatives.

The Zmod() function creates this ring.

When we create an element of Z/nZ, any integer is coerced to its
canonical representative in {0, 1, ..., n-1}.

Different programming languages handle negative modulo differently!
In cryptography, we always want the result in [0, n-1].

For -3 mod 7: some languages give -3, but we want 4.
The sagemath-ts library always gives the positive representative.

Any integer in an equivalence class can represent that class.
Sometimes we want different representatives for different purposes.

If a = a' (mod n) and b = b' (mod n), then:

• a + b = a' + b' (mod n)
• a - b = a' - b' (mod n)
• a * b = a' * b' (mod n)
• a^k = (a')^k (mod n)

This is why modular arithmetic works!

A complete residue system modulo n is a set of n integers, one from
each equivalence class. The standard system is {0, 1, ..., n-1}.

A reduced residue system contains only integers coprime to n.

a = b (mod n) means n | (a - b), i.e., n divides (a - b).
This connects congruence to divisibility.

EXERCISE: Verify that congruence is an equivalence relation by
testing the three properties for specific examples.

When a hash function produces a 256-bit output, it's selecting a
representative from one of 2^256 equivalence classes.

The collision resistance property means it's hard to find two
inputs that map to the same equivalence class.

Linear congruences are equations of the form ax = b (mod n).
Solving them is a fundamental skill in number theory and cryptography.

Mathematical Background:
The linear congruence ax = b (mod n) has a solution if and only if
gcd(a, n) divides b.

If gcd(a, n) = g and g | b, then:
• There are exactly g solutions modulo n
• Solutions differ by n/g
• General solution: x = x0 + k*(n/g) for k = 0, 1, ..., g-1

Special case: If gcd(a, n) = 1, there is exactly one solution:
x = a^(-1) * b (mod n)

Why This Matters for Cryptography:
• RSA key generation: Finding d such that ed = 1 (mod phi(n))
• Solving systems of congruences (Chinese Remainder Theorem)
• Lattice-based cryptography: Finding short vectors
• Discrete log problems can be viewed as linear congruences

When gcd(a, n) = 1, the equation ax = b (mod n) has exactly one solution.
Solution: x = a^(-1) * b (mod n)

When gcd(a, n) = g > 1 and g divides b, there are g solutions.

When gcd(a, n) does not divide b, there is no solution.

Algorithm to solve ax = b (mod n):

1. Compute g = gcd(a, n)
2. If g does not divide b, no solution
3. Divide through by g: (a/g)x = (b/g) (mod n/g)
4. Now gcd(a/g, n/g) = 1, so use inverse
5. x0 = (a/g)^(-1) * (b/g) mod (n/g)
6. General solution: x = x0 + k*(n/g) for k = 0, 1, ..., g-1

The Chinese Remainder Theorem (CRT) solves systems of linear congruences:
x = a1 (mod n1)
x = a2 (mod n2)
...

When n1, n2, ... are pairwise coprime, there is a unique solution mod (n1n2...).

For two congruences, the crt() function is convenient:
x = a (mod m)
x = b (mod n)

RSA decryption can be sped up using CRT.
Instead of computing c^d mod n directly, we compute:
mp = c^(d mod p-1) mod p
mq = c^(d mod q-1) mod q
Then combine using CRT.

Linear congruences generalize to polynomial congruences.
f(x) = 0 (mod n)

For prime n, a polynomial of degree d has at most d roots.

The discrete logarithm problem: find x such that g^x = h (mod p)
This can be viewed as solving: x * log(g) = log(h) in the exponent group.

For small groups, we can solve by exhaustive search.

EXERCISE: Solve this system step by step:
x = 3 (mod 4)
x = 1 (mod 5)
x = 4 (mod 7)

Shamir's Secret Sharing uses polynomial interpolation over a finite field.
To reconstruct, we solve a system of linear equations (or use Lagrange interpolation).

Secret S is hidden as f(0) where f is a degree k-1 polynomial.
We need k points (x_i, y_i = f(x_i)) to recover S.

The modular inverse is one of the most important concepts in cryptography.
It allows us to "divide" in modular arithmetic, which is essential for
RSA decryption, elliptic curve operations, and many other algorithms.

Mathematical Background:
The modular inverse of a modulo n is an integer a^(-1) such that:
a * a^(-1) = 1 (mod n)

The inverse exists if and only if gcd(a, n) = 1 (a and n are coprime).

There are several ways to compute modular inverses:

1. Extended Euclidean Algorithm: Most common, O(log n)
2. Fermat's Little Theorem: a^(-1) = a^(p-2) mod p (for prime p)
3. Euler's Theorem: a^(-1) = a^(phi(n)-1) mod n

Why This Matters for Cryptography:
• RSA: Private exponent d = e^(-1) mod phi(n)
• ECDSA: Signature computation requires modular inverse
• Division in finite fields (essential for ECC)
• Lagrange interpolation in secret sharing

The modular inverse of a mod n satisfies: a * a^(-1) = 1 (mod n)

The inverse of a mod n exists only when gcd(a, n) = 1.
Elements without inverses are called zero divisors.

If gcd(a, n) = 1, then xgcd(a, n) returns (1, s, t) where:
1 = sa + tn
So: sa = 1 - tn = 1 (mod n)
Therefore: a^(-1) = s (mod n)

For prime p and a not divisible by p:
a^(p-1) = 1 (mod p) [Fermat's Little Theorem]

Therefore:
a^(p-2) * a = a^(p-1) = 1 (mod p)

So: a^(-1) = a^(p-2) (mod p)

Euler's Theorem (generalizes Fermat's Little Theorem):
a^(phi(n)) = 1 (mod n) when gcd(a, n) = 1

Therefore: a^(-1) = a^(phi(n)-1) (mod n)

The IntegerMod class provides convenient methods for modular arithmetic
including .inv() for inverse and .div() for division.

In RSA, the private exponent d is computed as:
d = e^(-1) mod phi(n)

This requires computing a modular inverse.

In modular arithmetic, a/b = a * b^(-1) (when b is invertible).
This is how "division" works in finite fields.

Computing n inverses normally requires n extended GCD operations.
Montgomery's trick computes n inverses with just 1 extended GCD + 3(n-1) multiplications!

Key insight: If we know (a1a2...*an)^(-1), we can extract individual inverses.

EXERCISE: Implement modular inverse using the extended Euclidean algorithm.

ECDSA signature computation requires a modular inverse:
s = k^(-1) * (hash + private_key * r) mod n

Where n is the order of the elliptic curve group.

Modular arithmetic operations form the computational backbone of cryptography.
Every RSA encryption, every elliptic curve point addition, and every
hash function computation relies on efficient modular operations.

Mathematical Background:
For integers a, b and positive modulus n:
• (a + b) mod n = ((a mod n) + (b mod n)) mod n
• (a - b) mod n = ((a mod n) - (b mod n)) mod n
• (a * b) mod n = ((a mod n) * (b mod n)) mod n
• a^k mod n can be computed efficiently using square-and-multiply

The key insight: we can reduce intermediate results modulo n at any point
without affecting the final answer. This keeps numbers small!

Why This Matters for Cryptography:
• RSA: c = m^e mod n (encryption), m = c^d mod n (decryption)
• Diffie-Hellman: g^x mod p
• ECDSA: Computations in a prime field
• AES: Operations in GF(2^8)

Modular addition and subtraction work like a clock.
If you go past n-1, you wrap around to 0.
If you go below 0, you wrap around to n-1.

Modular multiplication is the workhorse of cryptography.
The key property: (a * b) mod n = ((a mod n) * (b mod n)) mod n

A crucial optimization: reduce after each operation to prevent overflow.
This is how cryptographic libraries handle large numbers efficiently.

Computing a^n mod m directly would be impossibly slow for cryptographic sizes.
The square-and-multiply algorithm computes this in O(log n) multiplications.

Key idea: a^13 = a^(1101 binary) = a^8 * a^4 * a^1

In real cryptography, exponents can be hundreds of bits long.
Square-and-multiply handles this efficiently.

The IntegerMod class provides a convenient interface for modular arithmetic.
All operations automatically reduce results modulo n.

Modular arithmetic preserves the familiar algebraic properties:

• Commutative: a + b = b + a, a * b = b * a
• Associative: (a + b) + c = a + (b + c)
• Distributive: a * (b + c) = ab + ac

a^(-k) mod n = (a^(-1))^k mod n, where a^(-1) is the modular inverse.
This only works when gcd(a, n) = 1.

For cryptographic applications, we need efficient implementations.
Key optimizations:

1. Reduce after each operation
2. Use square-and-multiply for exponentiation
3. Use Montgomery multiplication for repeated operations

EXERCISE: Implement the square-and-multiply algorithm for modular exponentiation.
This is one of the most important algorithms in cryptography!

RSA encryption: ciphertext = message^e mod n
RSA decryption: message = ciphertext^d mod n

All the modular arithmetic we've learned comes together here!

Cyclic groups are the simplest type of group and play a central role in
cryptography. Nearly all groups used in cryptographic protocols are either
cyclic or have cyclic components.

Mathematical Background:
A group G is CYCLIC if there exists an element g in G such that every element
of G can be written as a power of g:
G = = {g^0, g^1, g^2, ..., g^(n-1)}

Such an element g is called a GENERATOR of G.

Key facts:
• Every cyclic group of order n is isomorphic to (Z/nZ, +)
• If |G| = n, then G is cyclic iff G has an element of order n
• (Z/pZ)* is cyclic for any prime p
• A cyclic group of order n has phi(n) generators

Why This Matters for Cryptography:
• Diffie-Hellman requires a generator of (Z/p)*
• ECDSA uses generators of elliptic curve groups
• Schnorr signatures work in cyclic groups
• Pairings map between carefully chosen cyclic groups

(Z/nZ, +) is cyclic with generator 1.
Every element can be written as 1 + 1 + ... + 1 (some number of times).

For prime p, (Z/pZ)* is a cyclic group of order p-1.
A generator is called a "primitive root" modulo p.

The order of an element g is the smallest positive k such that g^k = e.
An element is a generator iff its order equals the group order.

A cyclic group of order n has exactly one subgroup for each divisor of n.
If G = has order n, and d | n, then <g^(n/d)> is the unique subgroup of order d.

A cyclic group of order n has exactly phi(n) generators.
The generators are g^k where gcd(k, n) = 1.

Algorithm to find a primitive root modulo prime p:

1. Compute p - 1 and its prime factorization
2. For each candidate g, check if g^((p-1)/q) != 1 for each prime q | (p-1)

Once we have one primitive root g, all others are g^k where gcd(k, p-1) = 1.

(Z/nZ)* is not always cyclic!
It's cyclic iff n = 1, 2, 4, p^k, or 2p^k for odd prime p.

EXERCISE: Verify that 2 is a primitive root modulo 13.

Diffie-Hellman key exchange requires:

1. A large prime p
2. A generator g of (Z/pZ)*

The security relies on the Discrete Log Problem being hard in this group.

Groups are the fundamental algebraic structure underlying almost all
modern cryptography. Understanding groups is essential for elliptic
curve cryptography, Diffie-Hellman, digital signatures, and more.

Mathematical Background:
A group (G, *) is a set G with a binary operation * satisfying:

1. CLOSURE: For all a, b in G, a * b is in G
2. ASSOCIATIVITY: For all a, b, c in G, (a * b) * c = a * (b * c)
3. IDENTITY: There exists e in G such that e * a = a * e = a for all a
4. INVERSE: For each a in G, there exists a^(-1) such that a * a^(-1) = e

If also: 5. COMMUTATIVITY: a * b = b * a for all a, b
then G is called an ABELIAN (or commutative) group.

Why This Matters for Cryptography:
• Diffie-Hellman: Security based on the discrete log problem in groups
• ECDSA: Digital signatures using elliptic curve groups
• RSA: Uses the multiplicative group (Z/nZ)*
• Pairings: Map between different groups for advanced protocols

The integers Z form a group under addition.
Let's verify all four group axioms.

Z/nZ under addition is a finite abelian group of order n.
This is the additive group of integers modulo n.

(Z/nZ)* is the set of elements in Z/nZ that are coprime to n.
Under multiplication, this forms a group.
Its order is phi(n) (Euler's totient function).

Let's see why integers under division don't form a group.

Symmetries of geometric objects form groups.
The dihedral group D_3 is the symmetries of an equilateral triangle.

GL_n(F) is the group of invertible n x n matrices over field F.
Let's look at GL_2(Z/2Z) - 2x2 invertible matrices over the field of 2 elements.

Let's build a tool to verify group axioms for finite sets.

EXERCISE: Create a FiniteGroup object for (Z/7Z)* and verify the axioms.

The order of an element is a fundamental concept that connects individual
elements to the structure of the group. Lagrange's theorem provides a
powerful constraint on possible orders.

Mathematical Background:
The ORDER of an element g in group G is the smallest positive integer n
such that g^n = e (identity).
ord(g) = min{n > 0 : g^n = e}

LAGRANGE'S THEOREM: If G is a finite group and H is a subgroup of G,
then |H| divides |G|.

Corollary: The order of any element divides the order of the group.
Corollary: g^|G| = e for all g in G.

Why This Matters for Cryptography:
• Fermat's Little Theorem: a^(p-1) = 1 mod p (p prime)
• Euler's Theorem: a^phi(n) = 1 mod n when gcd(a,n) = 1
• RSA: Works because d*e = 1 mod phi(n)
• Subgroup attacks: Exploiting small subgroups in DH

The order of g is found by computing g^1, g^2, g^3, ... until we get 1.

Lagrange's Theorem tells us that element orders must divide the group order.
Let's verify this experimentally.

For large groups, we don't want to compute all powers naively.
We can use the fact that ord(g) divides |G| to check only divisors.

Fermat's Little Theorem: For prime p and a not divisible by p,
a^(p-1) = 1 (mod p)

This is a direct consequence of Lagrange's theorem:
ord(a) divides |G| = p - 1
so a^(p-1) = a^(k * ord(a)) = (a^ord(a))^k = 1^k = 1

Euler's Theorem: For gcd(a, n) = 1,
a^phi(n) = 1 (mod n)

This generalizes Fermat's Little Theorem to composite moduli.

Each element g generates a cyclic subgroup of order ord(g).
The subgroup structure is determined by element orders.

The LCM of all element orders is called the "exponent" of the group.
For cyclic groups, exponent = group order.
For non-cyclic groups, exponent < group order.

Key formula: ord(g^k) = ord(g) / gcd(k, ord(g))

This tells us how to find elements of any desired order.

To find an element of order d, find a generator g and compute g^(|G|/d).
This only works if d divides |G|.

EXERCISE: Show that every element order in (Z/17Z)* divides 16.

RSA works because of Euler's theorem:
m^(ed) = m^(1 + k*phi(n)) = m * (m^phi(n))^k = m * 1^k = m (mod n)

The last step uses Euler's theorem: m^phi(n) = 1 when gcd(m, n) = 1.

Subgroups are groups within groups. Understanding subgroups and cosets
is essential for understanding group structure and for cryptographic
applications like small-subgroup attacks.

Mathematical Background:
A SUBGROUP H of G is a subset of G that is itself a group under the same operation.
Equivalently, H is a subgroup iff:

1. The identity is in H
2. H is closed under the group operation
3. H is closed under taking inverses

A LEFT COSET of H in G is a set gH = {gh : h in H} for some g in G.
A RIGHT COSET is Hg = {hg : h in H}.

Key facts:
• All cosets have the same size |H|
• Cosets partition G: every element is in exactly one coset
• |G| = |H| * [G : H] where [G : H] is the number of cosets (index)

Why This Matters for Cryptography:
• Small-subgroup attacks exploit subgroups of small order
• Safe primes: p = 2q + 1 where q is also prime (few subgroups)
• Cofactor multiplication in ECC to avoid subgroup attacks
• Quotient groups and normal subgroups in advanced protocols

Let's find all subgroups of (Z/12Z, +).
By Lagrange's theorem, subgroup orders must divide 12.

For prime p, (Z/pZ)* is cyclic of order p-1.
Subgroups have orders that divide p-1.

A coset gH is the set of all products gh for h in H.
Cosets partition the group.

Proof sketch of Lagrange's Theorem:

1. All cosets have the same size as H
2. Cosets partition G (every element is in exactly one coset)
3. Therefore |G| = (number of cosets) * |H|
4. So |H| divides |G|

The index [G:H] is the number of cosets of H in G.
[G:H] = |G| / |H|

A subgroup H is NORMAL if gH = Hg for all g in G.
In abelian groups, ALL subgroups are normal.

For non-abelian groups, this is more interesting.

If H is a normal subgroup of G, the quotient group G/H consists of
all cosets with operation (aH)(bH) = (ab)H.

A "safe prime" is p = 2q + 1 where q is also prime.
(Z/pZ)* then has only subgroups of order 1, 2, q, and 2q.

This is important for Diffie-Hellman security.

In Diffie-Hellman, if an attacker can get your public key into a small
subgroup, they can determine your private key modulo the subgroup order.

EXERCISE: Find all subgroups of (Z/20Z)*.
Note: This group may not be cyclic!

A field is a ring where every non-zero element has a multiplicative inverse.
Prime fields Z/pZ are the simplest finite fields and are fundamental to
cryptography.

Mathematical Background:
A FIELD is a set F with operations + and * such that:

1. (F, +) is an abelian group with identity 0
2. (F - {0}, *) is an abelian group with identity 1
3. Multiplication distributes over addition

Key properties:
• Every non-zero element is invertible
• No zero divisors (integral domain)
• Division is always defined (except by zero)

Z/pZ is a field iff p is prime. We denote it GF(p) or F_p.

Why This Matters for Cryptography:
• Elliptic curves are typically defined over prime fields
• Diffie-Hellman uses the multiplicative group of a prime field
• Many protocols need division, which requires fields
• Polynomial arithmetic over fields (e.g., AES)

Z/nZ is a field iff n is prime.
In a field, every non-zero element has a multiplicative inverse.

GF(p) denotes the finite field with p elements.
For prime p, GF(p) = Z/pZ.

In a field, division a/b is defined as a * b^(-1) for b != 0.
This is NOT possible in general rings!

The characteristic of a field is the smallest positive n such that
n * 1 = 0, or 0 if no such n exists.

For GF(p), the characteristic is p.

The non-zero elements of GF(p) form a multiplicative group GF(p)* of order p-1.
This group is always cyclic!

In a field, linear equations ax = b always have a unique solution
(when a != 0): x = b * a^(-1)

An element a in GF(p)* is a quadratic residue if a = x^2 for some x.
Exactly (p-1)/2 elements are quadratic residues in GF(p)*.

In GF(p), the Frobenius map is x -> x^p.
By Fermat's Little Theorem, x^p = x for all x in GF(p).
So Frobenius is the identity on prime fields!

GF(p) is the smallest field of characteristic p.
Larger finite fields GF(p^n) are built as extensions.

EXERCISE: Verify all field axioms for GF(11).

The multiplicative group (Z/nZ)* consists of all elements in Z/nZ that
have multiplicative inverses. This group is fundamental to RSA and
Diffie-Hellman cryptography.

Mathematical Background:
(Z/nZ)* = {a in Z/nZ : gcd(a, n) = 1}

Key properties:
• |(Z/nZ)| = phi(n) (Euler's totient function)
• (Z/nZ) is a group under multiplication
• For prime p: (Z/pZ)* is cyclic of order p-1
• For n = 2, 4, p^k, 2p^k (p odd prime): (Z/nZ)* is cyclic
• For other n: (Z/nZ)* is a direct product of cyclic groups

Why This Matters for Cryptography:
• RSA: Security relies on properties of (Z/nZ)* where n = pq
• Diffie-Hellman: Uses the cyclic group (Z/pZ)* for safe prime p
• ElGamal: Encryption in (Z/pZ)*
• Schnorr signatures: Work in subgroups of (Z/pZ)*

(Z/nZ)* contains exactly those elements coprime to n.

The group operation is multiplication modulo n.
Let's verify the group axioms.

The structure depends on the factorization of n.
By the Chinese Remainder Theorem:
(Z/nZ)* = (Z/p1^a1)* x (Z/p2^a2)* x ...

(Z/nZ)* is cyclic iff n = 1, 2, 4, p^k, or 2p^k for odd prime p.

(Z/8Z)* = {1, 3, 5, 7} is isomorphic to Z/2Z x Z/2Z, not Z/4Z.
Every non-identity element has order 2!

A primitive root modulo n is a generator of (Z/nZ).
These exist only when (Z/nZ) is cyclic.

Euler's Theorem: For gcd(a, n) = 1, a^phi(n) = 1 (mod n)
This is because phi(n) is the order of (Z/nZ)*.

The Carmichael function lambda(n) is the exponent of (Z/nZ):
the smallest m such that a^m = 1 for all a in (Z/nZ).

For cyclic groups: lambda(n) = phi(n)
For non-cyclic groups: lambda(n) < phi(n)

For prime p, (Z/pZ)* has exactly one subgroup for each divisor of p-1.
This is because (Z/pZ)* is cyclic.

EXERCISE: Analyze the structure of (Z/24Z)*.

A primitive root modulo n is a generator of the multiplicative group (Z/nZ)*.
For prime p, primitive roots are essential for Diffie-Hellman key exchange
and other cryptographic protocols.

Mathematical Background:
An element g in (Z/nZ)* is a PRIMITIVE ROOT if ord(g) = phi(n).
Equivalently, g generates the entire group: (Z/nZ)* = .

Key facts:
• Primitive roots exist iff n = 1, 2, 4, p^k, or 2p^k (p odd prime)
• For prime p, there are exactly phi(p-1) primitive roots
• If g is a primitive root, then g^k is a primitive root iff gcd(k, phi(n)) = 1

Why This Matters for Cryptography:
• Diffie-Hellman: The generator g must be a primitive root (or generate a large subgroup)
• Discrete Log Problem: Hardness depends on working in a large cyclic group
• ElGamal encryption: Requires a primitive root
• Schnorr signatures: Use a prime-order subgroup

A primitive root g has order phi(n).
We can find one by checking each candidate.

Instead of computing the full order, we can test if g is a primitive root
by checking that g^((p-1)/q) != 1 for each prime factor q of p-1.

If g is a primitive root mod p, then g^k is also a primitive root
iff gcd(k, p-1) = 1.

If g is a primitive root mod p, every element a in (Z/pZ)* can be written
as a = g^x for some x. The value x is the discrete logarithm of a base g.

Discrete logarithms satisfy:
log_g(ab) = log_g(a) + log_g(b) (mod p-1)
log_g(a^k) = k * log_g(a) (mod p-1)

Primitive roots exist for n = 2, 4, p^k, 2p^k (p odd prime).
Let's verify this for small moduli.

If g is a primitive root mod p, then either g or g + p is a
primitive root mod p^2, and can be lifted to any p^k.

A safe prime is p = 2q + 1 where q is also prime.
For safe primes, (Z/pZ)* has only subgroups of order 1, 2, q, and 2q.
Any element != +/-1 generates either the full group or the subgroup of order q.

The Pohlig-Hellman algorithm can solve the discrete log problem
efficiently if p-1 has only small prime factors.

EXERCISE: Find a primitive root modulo 41.

A ring is an algebraic structure with two operations: addition and multiplication.
The ring Z/nZ (integers modulo n) is fundamental to cryptography.

Mathematical Background:
A RING (R, +, *) is a set R with two binary operations satisfying:

1. (R, +) is an abelian group (with identity 0)
2. (R, *) is a monoid (associative with identity 1)
3. Multiplication distributes over addition

Key concepts in rings:
• ZERO DIVISORS: Elements a, b != 0 where ab = 0
• UNITS: Elements with multiplicative inverses
• INTEGRAL DOMAIN: A ring with no zero divisors
• FIELD: A ring where every non-zero element is a unit

Why This Matters for Cryptography:
• RSA operates in the ring Z/nZ where n = pq
• Zero divisors in Z/nZ reveal the factorization of n!
• Polynomial rings are used in lattice cryptography
• AES uses the ring GF(2^8)

Z/nZ is a ring with both addition and multiplication.
The Zmod() function creates this ring.

Let's verify that Z/nZ satisfies all ring axioms.

A zero divisor is a non-zero element a where ab = 0 for some non-zero b.
Zero divisors exist when n is composite.

In Z/nZ, an element is either a unit (invertible) OR a zero divisor.
a is a unit iff gcd(a, n) = 1.

In RSA, if we find a zero divisor in Z/nZ, we've factored n!
This is the basis of many factoring attacks.

The multiplication table reveals the ring structure.

An integral domain is a ring with no zero divisors.
Z/nZ is an integral domain iff n is prime.

An ideal I of ring R is an additive subgroup that "absorbs" multiplication:
for all r in R and a in I, ra is in I.

In Z/nZ, ideals are generated by divisors of n.

Z/nZ is itself a quotient ring: Z/nZ = Z / (n).
We can also form quotients of Z/nZ by its ideals.

EXERCISE: Find all zero divisor pairs in Z/30Z and relate them to factorization.

Fermat's Little Theorem has numerous applications in cryptography:

1. Fast modular inverse computation
2. Primality testing (Fermat test)
3. RSA encryption/decryption
4. Pseudorandom number generation
5. Hash functions and checksums

This tutorial explores these applications with practical examples.

@module tutorial/part2/fermat-applications

Fermat primality test.
If n is prime and gcd(a,n)=1, then a^(n-1) = 1 (mod n).
Contrapositive: If a^(n-1) != 1 (mod n), then n is composite.

Fermat's Little Theorem is one of the most important results in number theory,
forming the foundation for many cryptographic algorithms including RSA.

Statement:
If p is a prime number and a is any integer not divisible by p, then:

a^(p-1) = 1 (mod p)

Equivalently, for any integer a:

a^p = a (mod p)

Proof Intuition:
Consider the set {1, 2, 3, ..., p-1} of nonzero residues modulo p.
When we multiply each element by a (where gcd(a,p) = 1), we get
{a, 2a, 3a, ..., (p-1)a} mod p.

Key insight: This is just a permutation of {1, 2, ..., p-1}!
Why? Because multiplication by a invertible element permutes the group.

Therefore:
1 * 2 * 3 * ... * (p-1) = a * 2a * 3a * ... * (p-1)a (mod p)
(p-1)! = a^(p-1) * (p-1)! (mod p)

Since (p-1)! is coprime to p, we can cancel it:
1 = a^(p-1) (mod p)

@module tutorial/part2/fermat

Computing a^n mod m efficiently is fundamental to cryptography.
Naive exponentiation is O(n) multiplications, but we can do much better.

Square-and-Multiply Algorithm:
The key insight: express n in binary and use the property:
a^(2k) = (a^k)^2
a^(2k+1) = a * (a^k)^2

This reduces the computation to O(log n) multiplications.

Connection to Fermat's Theorem:
When computing a^n mod p (for prime p), we can first reduce:
n' = n mod (p-1)
Because a^(p-1) = 1 (mod p), so a^n = a^(n mod (p-1)) (mod p)

This is especially useful when n is very large.

@module tutorial/part2/modular-exponentiation

Euler's theorem and the totient function have numerous applications
in cryptography and number theory:

1. RSA cryptosystem
2. Computing multiplicative order
3. Primitive roots
4. Discrete logarithm
5. Modular arithmetic optimizations

@module tutorial/part2/euler-applications

This tutorial covers efficient algorithms for computing phi(n).

Methods::

1. Direct counting (slow, O(n) or O(n log n))
2. From prime factorization (efficient for single values)
3. Sieve method (efficient for computing phi for all n up to N)

Key Formulas::
phi(p^k) = p^(k-1) * (p - 1) for prime p
phi(mn) = phi(m) * phi(n) when gcd(m, n) = 1

@module tutorial/part2/computing-phi

Euler's totient function phi(n) counts the number of integers from 1 to n
that are coprime to n (i.e., gcd(k, n) = 1).

Definition:
phi(n) = |{k : 1 <= k <= n and gcd(k, n) = 1}|

Equivalently, phi(n) is the order of the multiplicative group (Z/nZ)*.

Key Formula:
For n = p1^e1 * p2^e2 * ... * pk^ek (prime factorization):

phi(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)

Or equivalently:

phi(n) = product over i of p_i^(e_i - 1) * (p_i - 1)

@module tutorial/part2/euler-totient

Euler's theorem is a generalization of Fermat's Little Theorem to
arbitrary moduli (not just primes).

Statement:
If gcd(a, n) = 1, then:

a^phi(n) = 1 (mod n)

where phi(n) is Euler's totient function.

Special Case: Fermat's Little Theorem:
When n = p is prime, phi(p) = p - 1, so:
a^(p-1) = 1 (mod p)

Proof Intuition:
The multiplicative group (Z/nZ)* has order phi(n).
By Lagrange's theorem, every element's order divides the group order.
Therefore a^phi(n) = 1 for all a in (Z/nZ)*.

@module tutorial/part2/eulers-theorem

CRT has wide applications in:

1. Solving systems of linear congruences
2. Calendar calculations (determining days)
3. Secret sharing
4. Parallel computation
5. Error-correcting codes

@module tutorial/part2/crt-applications

The CRT is not just an existence theorem - it provides an explicit
algorithm for constructing the solution.

The Construction:
Given the system:
x = a1 (mod m1)
x = a2 (mod m2)

where gcd(m1, m2) = 1:

1. Use extended Euclidean algorithm to find s, t with:
   sm1 + tm2 = 1

2. The solution is:
   x = a1tm2 + a2sm1 (mod m1*m2)

Why this works:
• x mod m1 = a1tm2 mod m1 = a1*(1 - sm1) mod m1 = a1
• x mod m2 = a2sm1 mod m2 = a2(1 - t*m2) mod m2 = a2

@module tutorial/part2/crt-construction

The Chinese Remainder Theorem provides a significant speedup
for RSA decryption and signing operations.

The Problem:
RSA decryption computes: m = c^d mod n
where n = p*q and d can be very large (typically 2048+ bits).

The CRT Speedup:
Instead of one large exponentiation mod n:

1. Compute m_p = c^(d mod (p-1)) mod p
2. Compute m_q = c^(d mod (q-1)) mod q
3. Combine using CRT: m = CRT(m_p, m_q, p, q)

This is approximately 4x faster because:
• Two exponentiations with half-size moduli
• Exponentiation is O(k^3) for k-bit numbers
• Two operations at k/2 bits: 2 * (k/2)^3 = k^3/4

@module tutorial/part2/crt-rsa

The Chinese Remainder Theorem (CRT) is one of the most important
results in number theory, with applications throughout cryptography.

Historical Note:
The theorem dates back to the 3rd century CE in China, where
mathematician Sun Tzu posed a problem: "Find a number which gives
remainder 2 when divided by 3, remainder 3 when divided by 5,
and remainder 2 when divided by 7."

Statement:
Let m1, m2, ..., mk be pairwise coprime positive integers.
For any integers a1, a2, ..., ak, the system of congruences:

x = a1 (mod m1)
x = a2 (mod m2)
...
x = ak (mod mk)

has a unique solution modulo M = m1 * m2 * ... * mk.

@module tutorial/part2/crt-statement

The Jacobi symbol generalizes the Legendre symbol to composite moduli.
It is essential for efficient computation without factoring.

Definition:
For positive odd integer n with prime factorization n = p1^e1 * ... * pk^ek,
and integer a, the Jacobi symbol (a/n) is:

(a/n) = (a/p1)^e1 * (a/p2)^e2 * ... * (a/pk)^ek

where (a/pi) are Legendre symbols.

Important Note:
(a/n) = 1 does NOT mean a is a quadratic residue mod n!
The Jacobi symbol only indicates QR status when n is prime.

@module tutorial/part2/jacobi-symbol

The Legendre symbol is a notation for determining whether an integer
is a quadratic residue modulo a prime.

Definition:
For odd prime p and integer a, the Legendre symbol (a/p) is:
• (a/p) = 0 if p | a
• (a/p) = 1 if a is a quadratic residue mod p
• (a/p) = -1 if a is a quadratic non-residue mod p

Euler's Formula:
(a/p) = a^((p-1)/2) (mod p)

@module tutorial/part2/legendre-symbol

Quadratic reciprocity is one of the most important and beautiful
theorems in number theory. It relates the solvability of x^2 = p (mod q)
to the solvability of x^2 = q (mod p).

Main Statement:
For distinct odd primes p and q:

(p/q)(q/p) = (-1)^((p-1)(q-1)/4)

This equals 1 unless both p and q are congruent to 3 (mod 4).

First Supplement:
(-1/p) = (-1)^((p-1)/2) = { 1 if p = 1 (mod 4)
{-1 if p = 3 (mod 4)

Second Supplement:
(2/p) = (-1)^((p^2-1)/8) = { 1 if p = +/-1 (mod 8)
{-1 if p = +/-3 (mod 8)

@module tutorial/part2/quadratic-reciprocity

A quadratic residue modulo n is a number that is a perfect square
modulo n. Understanding quadratic residues is fundamental to many
cryptographic constructions.

Definition:
An integer a is a quadratic residue modulo n if there exists an
integer x such that:
x^2 = a (mod n)

If no such x exists (and gcd(a, n) = 1), then a is a quadratic
non-residue modulo n.

@module tutorial/part2/quadratic-residues

Given a quadratic residue a modulo an odd prime p, how do we find
x such that x^2 = a (mod p)?

Simple Case: p = 3 (mod 4):
If p = 3 (mod 4) and a is a QR, then:
x = a^((p+1)/4) (mod p)

General Case: Tonelli-Shanks Algorithm:
Works for any odd prime p. Time complexity: O(log^2 p)

@module tutorial/part2/square-roots

Fermat's Little Theorem states: If p is prime and gcd(a, p) = 1, then
a^(p-1) = 1 (mod p)

The contrapositive gives us a primality test: If a^(n-1) != 1 (mod n)
for some a coprime to n, then n is definitely composite.

The Problem: Fermat Liars and Pseudoprimes:
Unfortunately, the converse isn't true. Some composite numbers n satisfy
a^(n-1) = 1 (mod n) for certain bases a. These are called:
• "Fermat pseudoprimes" to base a
• a is called a "Fermat liar" for n

Even worse, Carmichael numbers are composite but satisfy the Fermat
condition for ALL bases coprime to n!

Complexity Analysis:
Time: O(log n) multiplications, each with O((log n)^2) bit operations
Overall: O((log n)^3) bit operations

This is MUCH faster than trial division's O(sqrt(n))!

The Miller-Rabin test is a refinement of the Fermat test that is immune
to Carmichael numbers. It's based on a key observation about primes.

Mathematical Foundation:
For any odd prime p, we can write p - 1 = 2^s * d where d is odd.

By Fermat's Little Theorem, a^(p-1) = 1 (mod p) for gcd(a,p) = 1.

The key insight: In a field, the only square roots of 1 are 1 and -1.

So for the sequence: a^d, a^(2d), a^(4d), ..., a^(2^s * d) = a^(p-1)
• The final term must be 1
• Each term is the square of the previous
• Before we hit 1, we must see -1 (= p-1)

If we ever see a square root of 1 that isn't +/- 1, n is composite!

Complexity Analysis:
Time: O(k * (log n)^3) where k is the number of witnesses tested
For a single witness: same as Fermat test

Error probability: At most (1/4)^k for k random witnesses
With 20 witnesses, error probability < 10^(-12)

Generating large random primes is crucial for cryptography:
• RSA needs two large primes p and q
• DSA/ElGamal need a large prime modulus
• Diffie-Hellman needs a safe prime or Sophie Germain prime

The Prime Number Theorem:
The number of primes less than n is approximately n / ln(n).

This means the probability that a random n-bit number is prime is
about 1 / (n * ln(2)) ~ 1.44 / n.

For a 1024-bit prime: ~1 in 710 odd numbers is prime.

Algorithm:

1. Generate a random n-bit odd number
2. Test for primality (Miller-Rabin)
3. If not prime, try the next odd number (or generate new random)
4. Repeat until a prime is found

Expected number of trials: O(n) where n is the bit length.

Trial division is the most straightforward method to test whether a number
is prime. The idea is simple: if n is composite, it must have a factor
less than or equal to sqrt(n).

Algorithm Description:
To test if n is prime:

1. Check if n <= 1 (not prime by definition)
2. Check if n == 2 (prime)
3. Check if n is even (not prime if n > 2)
4. For each odd d from 3 to sqrt(n), check if d divides n

If no divisor is found, n is prime.

Complexity Analysis:
Time complexity: O(sqrt(n))
• We only need to check divisors up to sqrt(n)
• If n has k bits, this is O(2^(k/2)) operations

This becomes impractical for large numbers (e.g., 512-bit primes used
in cryptography), which is why we need probabilistic tests.

Why sqrt(n)?:
If n = a * b where a <= b, then a <= sqrt(n).
Proof: If a > sqrt(n) and b > sqrt(n), then a*b > n, contradiction.

Integer factorization is one of the fundamental hard problems in
cryptography. The security of RSA and many other cryptosystems
depends on the difficulty of factoring large integers.

The Factoring Hierarchy:
From simplest to most sophisticated:

1. Trial division: O(sqrt(n))
2. Pollard's rho: O(n^(1/4))
3. Pollard's p-1: O(B log B) when p-1 is B-smooth
4. Elliptic curve method (ECM): O(exp(sqrt(2 log p log log p)))
5. Quadratic sieve: O(exp(sqrt(log n log log n)))
6. Number field sieve (NFS): O(exp(c * (log n)^(1/3) * (log log n)^(2/3)))

Records and Estimates:
• RSA-250 (829 bits, 250 digits): Factored in 2020, ~2700 CPU years
• RSA-2048: Estimated >10^12 CPU years with current algorithms

This is why RSA-2048 is considered secure (for now).

Pollard's p-1 method exploits a weakness in primes p where p-1 is
"smooth" (has only small prime factors). It's based on Fermat's
Little Theorem.

Mathematical Foundation:
Fermat's Little Theorem: If p is prime and gcd(a, p) = 1, then
a^(p-1) = 1 (mod p)

If p-1 | M (M is a multiple of p-1), then a^M = 1 (mod p).

Key insight: If p | n but p-1 | M and q-1 does not divide M,
then gcd(a^M - 1, n) might be p (not n or 1).

Algorithm:

1. Choose a smoothness bound B
2. Compute M = lcm(1, 2, ..., B) or M = product of prime powers <= B
3. Compute a^M mod n for some base a
4. Compute gcd(a^M - 1, n)
5. If 1 < gcd < n, we found a factor!

Complexity:
Time: O(B * log(B) * log(n)^2) to check B-smoothness

Works when p-1 is B-smooth. Fails if p-1 has a large prime factor.

Pollard's rho is a probabilistic factorization algorithm that uses
the birthday paradox to find factors. It's much faster than trial
division for numbers with medium-sized factors.

The Birthday Paradox:
In a group of 23 people, there's a >50% chance two share a birthday.
With sqrt(N) random samples from N items, expect a collision.

Algorithm Idea:

1. We want to factor n = p * q
2. Generate a "pseudo-random" sequence: x_{i+1} = f(x_i) mod n
3. After O(sqrt(p)) steps, we expect x_i = x_j mod p for some i != j
4. This means p | (x_i - x_j) but likely n does not divide (x_i - x_j)
5. So gcd(x_i - x_j, n) gives us a factor!

Complexity:
Expected time: O(n^(1/4)) to find a factor of size sqrt(n)
This is MUCH better than trial division's O(n^(1/2))!

The "Rho" Shape:
The sequence eventually cycles (finite group), looking like ρ:
x_0 -> x_1 -> ... -> x_t -> x_{t+1} -> ... -> x_t (cycle)

Trial division is the simplest factorization algorithm. It finds the
prime factors of n by systematically dividing by potential prime factors.

Algorithm Description:

1. While n is even, divide by 2
2. For each odd number d from 3 to sqrt(n):
   • While d divides n, divide n by d
3. If n > 1 at the end, n is a prime factor

Complexity Analysis:
Time complexity: O(sqrt(n)) = O(2^(k/2)) for k-bit number

This is fine for small numbers but becomes impractical for:
• 40-digit numbers: millions of years
• RSA-sized numbers: longer than the age of the universe

When It's Useful:
• Factoring small numbers quickly
• Finding small factors of large numbers
• As a preprocessing step before other algorithms

The baby-step giant-step (BSGS) algorithm is a time-space tradeoff
for solving the discrete logarithm problem. It achieves O(sqrt(n))
time using O(sqrt(n)) space.

Algorithm Idea:
Let m = ceil(sqrt(n)). We can write any x in [0, n) as:
x = i * m + j where 0 <= i, j < m

So g^x = g^(im + j) = g^(im) * g^j

Rearranging: h * g^(-j) = g^(i*m)

Algorithm:

1. Baby steps: Compute g^0, g^1, ..., g^(m-1) and store in table
2. Giant steps: Compute h, hg^(-m), hg^(-2m), ... until match

When we find h * g^(-j) = g^(im), we have x = im + j.

Complexity:
Time: O(sqrt(n)) group operations
Space: O(sqrt(n)) group elements

The naive approach to solving the discrete logarithm problem:
try every possible exponent until we find a match.

Algorithm:
To find x such that g^x = h in a group of order n:

1. Compute g^0, g^1, g^2, ... until we find g^x = h
2. Return x

Complexity:
Time: O(n) group operations
Space: O(1)

For cryptographic groups (n ~ 2^256), this is completely infeasible.
But understanding brute force helps appreciate better algorithms.

The discrete logarithm problem is fundamental to many cryptographic
systems including Diffie-Hellman key exchange, ElGamal encryption,
DSA signatures, and elliptic curve cryptography.

Definition:
Given a cyclic group G with generator g and an element h in G,
find x such that g^x = h.

We write x = log_g(h) or x = dlog_g(h).

Examples of Groups:

1. Multiplicative group (Z/pZ)*: g^x mod p = h
2. Elliptic curve group: [x]P = Q (scalar multiplication)
3. Any cyclic group of prime order

Why It's Hard:
Exponentiation is easy: g^x mod p takes O(log x) multiplications
Discrete log is hard: Best known takes sub-exponential time

This asymmetry is the foundation of DL-based cryptography.

This tutorial explores why DLP is believed to be computationally hard
and how this assumption forms the foundation of modern cryptography.

The DLP Assumption:
Informally: In a properly chosen group G of order n, given g and h = g^x,
computing x requires time proportional to sqrt(n) or worse.

Related Assumptions:
• CDH (Computational Diffie-Hellman): Given g^a and g^b, compute g^(ab)
• DDH (Decisional Diffie-Hellman): Distinguish g^(ab) from random

These assumptions are what allow us to build secure cryptosystems.

The Pohlig-Hellman algorithm solves the discrete logarithm problem
efficiently when the group order has only small prime factors.

Key Insight:
If the group order n = p1^e1 * p2^e2 * ... * pk^ek, then:

1. Solve DLP in subgroups of order pi^ei
2. Combine solutions using Chinese Remainder Theorem

Complexity:
Time: O(sum of ei * (log n + sqrt(pi))) for n = prod(pi^ei)

If all pi are small (n is "smooth"), this is much faster than sqrt(n).

Security Implication:
Groups with smooth order are WEAK for cryptography!
This is why we use prime-order subgroups or safe primes.

This tutorial demonstrates common attacks on RSA implementations and
explains why certain parameter choices or practices are dangerous.

Attack Categories:

1. Mathematical attacks (small e, common modulus, etc.)
2. Implementation attacks (timing, padding oracle)
3. Key generation attacks (weak primes, close primes)

Understanding these attacks is crucial for secure RSA implementation.

DISCLAIMER:
These attacks are presented for educational purposes only.
Use this knowledge to build more secure systems, not to attack others.

If e is small (e.g., e=3) and the message m is small enough that
m^e < n, then the ciphertext c = m^e without any modular reduction.

Attack: Simply compute the e-th root of c.

If the same message m is encrypted with e different public keys,
all using exponent e, the message can be recovered using CRT.

Given:
c1 = m^e mod n1
c2 = m^e mod n2
c3 = m^e mod n3 (for e=3)

Find x such that:
x ≡ c1 (mod n1)
x ≡ c2 (mod n2)
x ≡ c3 (mod n3)

By CRT, x = m^e (no modular reduction if m^e < n1n2n3).
Then m = e-th root of x.

If the same message is encrypted under two different public exponents
e1 and e2 with gcd(e1, e2) = 1, using the same modulus n,
the message can be recovered without the private key.

Given c1 = m^e1 mod n and c2 = m^e2 mod n:

1. Find s, t such that se1 + te2 = 1 (by extended GCD)
2. Compute: c1^s * c2^t = m^(se1 + te2) = m^1 = m (mod n)

If p and q are close together, n can be factored quickly using
Fermat's factorization method.

For n = p * q where p > q:
n = ((p+q)/2)^2 - ((p-q)/2)^2
n = a^2 - b^2 = (a+b)(a-b)

Algorithm:
a = ceil(sqrt(n))
while a^2 - n is not a perfect square:
a += 1
b = sqrt(a^2 - n)
p = a + b, q = a - b

If p and q are close, this converges very quickly.

Wiener's attack applies when d < (1/3) * n^(1/4).
It uses continued fractions to find d from e and n.

The idea: ed = 1 + kphi(n) for some k.
So e/phi(n) ≈ k/d.
Since phi(n) ≈ n, we have e/n ≈ k/d.
The convergents of the continued fraction of e/n include k/d.

If RSA implementation time depends on the private key bits,
an attacker can recover d by measuring decryption times.

Square-and-multiply has different timing based on whether
each bit of d is 0 or 1:

• Bit = 0: Only squaring
• Bit = 1: Squaring AND multiplication

If a server reveals whether PKCS#1 v1.5 padding is valid,
an attacker can decrypt arbitrary ciphertexts.

PKCS#1 v1.5 padding: 0x00 || 0x02 || [random non-zero bytes] || 0x00 || [message]

Attack:

1. Multiply ciphertext by s^e mod n for various s
2. Server reveals if decryption has valid padding
3. Use this oracle to narrow down the plaintext range
4. After ~1 million queries, plaintext is recovered

The Chinese Remainder Theorem (CRT) can speed up RSA decryption by
approximately 4x. This is the standard optimization used in all
production RSA implementations.

The Basic Idea:
Instead of computing m = c^d mod n directly (expensive for large n),
we compute:
m_p = c^(d mod (p-1)) mod p
m_q = c^(d mod (q-1)) mod q

Then combine using CRT to get m mod n.

Why It's Faster:
• Operations mod p and mod q use half the bits of n
• Modular exponentiation is O(k^3) for k-bit numbers
• Two half-size operations: 2 * (k/2)^3 = k^3/4
• Plus small CRT overhead
• Net speedup: ~4x

Security Considerations:
CRT decryption can be vulnerable to fault attacks.
Always verify the result after CRT computation.

CRT Decryption Algorithm:

1. Compute m_p = c^(d_p) mod p
2. Compute m_q = c^(d_q) mod q
3. Combine: m = m_q + q * ((m_p - m_q) * q_inv mod p)

This is called "Garner's formula" for CRT.

Why CRT is faster:

For n-bit RSA modulus:

• Standard: One exponentiation with ~n-bit exponent mod n-bit number
• CRT: Two exponentiations with ~(n/2)-bit exponents mod (n/2)-bit numbers

Modular exponentiation cost is roughly O(k * k^2) = O(k^3) where k is bit size.

Standard: O(n^3)
CRT: 2 * O((n/2)^3) = 2 * O(n^3/8) = O(n^3/4)

Theoretical speedup: 4x
Practical speedup: ~3-4x (due to CRT combination overhead)

The CRT private key representation stores:

• p, q: The prime factors
• d_p = d mod (p-1): Private exponent mod (p-1)
• d_q = d mod (q-1): Private exponent mod (q-1)
• q_inv = q^(-1) mod p: CRT coefficient

Some implementations also store:

• d: The full private exponent (for verification)
• p_inv = p^(-1) mod q: Alternative CRT coefficient

CRT decryption is vulnerable to fault attacks!

If a computational fault occurs in one of the partial decryptions
(m_p or m_q), the attacker can factor n.

Attack:

1. Get correct signature s
2. Induce fault to get faulty signature s'
3. If fault was in m_q computation:
   • s ≡ m (mod p) and s ≡ m (mod q)
   • s' ≡ m (mod p) but s' ≢ m (mod q)
4. Compute gcd(s - s', n) = p

Defense: Always verify the result before outputting it.

Blinding protects against timing and power analysis attacks.

1. Generate random r, compute r^e mod n
2. Blind ciphertext: c' = c * r^e mod n
3. Decrypt with CRT: m' = (c')^d mod n = m * r
4. Unblind: m = m' * r^(-1) mod n

The decryption now operates on a randomized value,
preventing side-channel leakage.

This tutorial covers RSA decryption: recovering plaintext from ciphertext
using the private key.

The Decryption Function:
Given a private key (n, d) and ciphertext c:
m = c^d mod n

Why Decryption Works:
Since e * d ≡ 1 (mod phi(n)), we have e * d = 1 + k * phi(n).
By Euler's theorem, for gcd(m, n) = 1:
m^(phi(n)) ≡ 1 (mod n)

Therefore:
c^d = (m^e)^d = m^(ed) = m^(1 + kphi(n)) = m * (m^phi(n))^k ≡ m * 1 ≡ m (mod n)

Performance Considerations:
Decryption (c^d) is much slower than encryption (m^e) because d is large.
The CRT optimization (covered in crt-optimization.ts) speeds up decryption.

RSA Decryption:
m = c^d mod n

This reverses encryption (c = m^e mod n) by the mathematical
relationship between e and d.

Let's trace through the decryption calculation to understand
the modular exponentiation process.

The private exponent d is typically very large (close to n in size).
This is because:
d = e^(-1) mod phi(n)

With e = 65537 (small), d ends up being approximately the same
size as phi(n), which is close to n.

Number of modular multiplications:

• Encryption: ~17 for e = 65537 (only 2 one-bits)
• Decryption: ~bit_length(d) = ~bit_length(n) operations

Edge cases to consider:

1. m = 0: c = 0, decrypts to 0
2. m = 1: c = 1, decrypts to 1
3. gcd(m, n) > 1: Still works, but reveals information!

WARNING: If an attacker can get you to decrypt a message where
gcd(m, n) > 1, they can factor n!

If they know m shares a factor with n:
gcd(m, n) = p or q
This completely breaks the key!

To decrypt, you need d.
To compute d = e^(-1) mod phi(n), you need phi(n).
To compute phi(n) = (p-1)(q-1), you need to factor n.

The security of RSA rests on the difficulty of factoring n.

Even partial information about decryption can be dangerous:

1. Knowing whether m is even or odd (1 bit of m)
2. Knowing m's most significant bit
3. Knowing if decryption "succeeded" (padding oracle)

These can lead to attacks that recover the full message.

A production RSA decryption implementation should:

1. Use constant-time modular exponentiation
2. Validate padding before returning success/failure
3. Use blinding to prevent timing attacks
4. Return only valid/invalid, never partial information

This tutorial covers RSA encryption: how to encrypt messages using the public key.

The Encryption Function:
Given a public key (n, e) and a message m where 0 <= m < n:
c = m^e mod n

The ciphertext c can only be decrypted by someone who knows the private key d.

Important Constraints:

1. The message m must be less than the modulus n
2. The message should be coprime to n (almost always true for random m)
3. Raw RSA is deterministic - same message gives same ciphertext
4. Padding schemes (OAEP, PKCS#1) are essential for security

Security Considerations:
• Never use "textbook RSA" in practice
• Always use proper padding (OAEP for encryption)
• RSA is slow compared to symmetric encryption
• Hybrid encryption: Use RSA to encrypt a symmetric key

RSA Encryption:
c = m^e mod n

Where:

• m is the plaintext message (as an integer)
• e is the public exponent
• n is the modulus
• c is the ciphertext

To encrypt text:

1. Convert text to numbers (e.g., ASCII)
2. Ensure each number < n (may need to break into blocks)
3. Encrypt each number

NOTE: This is for educational purposes only.
Real systems use proper padding schemes.

When the message is larger than n, we must split it into blocks.
Each block is encrypted independently.

Block size = floor(log2(n)) bits
For n = 3233, block size = 11 bits (but we'll use byte-aligned blocks)

"Textbook RSA" (RSA without padding) has several weaknesses:

1. DETERMINISTIC: Same plaintext always gives same ciphertext

   • Attacker can build a dictionary of common messages

2. MALLEABILITY: Given c = m^e mod n, attacker can compute:

   • c' = c * 2^e mod n = (2m)^e mod n
   • Without knowing m, they created valid encryption of 2m

3. SMALL MESSAGE ATTACK: If m^e < n, then c = m^e (no modular reduction)

   • Attacker can just take e-th root to recover m

OAEP (Optimal Asymmetric Encryption Padding) adds randomness and structure:

1. Pad message m with zeros to fixed length
2. Generate random r
3. Compute: X = (m || zeros) XOR Hash(r)
4. Compute: Y = r XOR Hash(X)
5. Encrypt (X || Y) with RSA

Benefits:

• Randomness makes encryption non-deterministic
• Structure allows detection of tampering
• Proven secure under random oracle model

RSA is slow (complex modular exponentiation) and has message size limits.
In practice, we use HYBRID ENCRYPTION:

1. Generate a random symmetric key K
2. Encrypt message with symmetric cipher: C_sym = AES(K, message)
3. Encrypt key with RSA: C_key = RSA(K)
4. Send (C_key, C_sym)

Benefits:

• RSA only encrypts small key (fast)
• AES encrypts large message (fast)
• Combines benefits of both systems

RSA encryption speed depends on:

1. Size of the exponent e
2. Size of the modulus n
3. Implementation (square-and-multiply optimization)

Using e = 65537 (binary: 10000000000000001):

• Only 2 set bits (Hamming weight 2)
• Square-and-multiply requires only ~17 squarings and 2 multiplications
• Much faster than using a large random e

RSA (Rivest-Shamir-Adleman) is one of the first practical public-key cryptosystems
and is widely used for secure data transmission. This tutorial walks through the
mathematical foundations and implementation of RSA key generation.

Mathematical Foundation:
RSA security relies on the computational difficulty of factoring the product of
two large prime numbers (the "factoring problem").

Key Generation Algorithm:

1. Choose two distinct large prime numbers p and q
2. Compute n = p * q (the modulus)
3. Compute phi(n) = (p-1)(q-1) (Euler's totient)
4. Choose e such that 1 < e < phi(n) and gcd(e, phi(n)) = 1
5. Compute d = e^(-1) mod phi(n) (the private exponent)

Public key: (n, e)
Private key: (n, d) or equivalently (p, q, d)

Security Considerations:
• p and q should be of similar bit length but not too close
• |p - q| should not be too small (prevents Fermat factorization)
• p - 1 and q - 1 should have large prime factors (prevents Pollard's p-1)
• e = 65537 (0x10001) is commonly used as it's prime and has low Hamming weight

In practice, we use cryptographically secure random number generators
to find primes of 1024+ bits. For educational purposes, we use smaller primes.

Key insight: The primes should be "random" and of similar size, but not too close.
If |p - q| is small, Fermat's factorization can quickly find p and q.

The modulus n is public. Its security relies on the difficulty of
factoring it back into p and q.

Bit length of n determines the security level:

• 1024 bits: ~80 bits of security (deprecated)
• 2048 bits: ~112 bits of security (current minimum)
• 3072 bits: ~128 bits of security
• 4096 bits: ~140 bits of security

For n = p * q where p, q are distinct primes:
phi(n) = (p - 1)(q - 1)

This is because:

• phi(p) = p - 1 for prime p
• phi(q) = q - 1 for prime q
• phi(p*q) = phi(p) * phi(q) for coprime p, q

phi(n) counts integers in [1, n-1] that are coprime to n.
These are exactly the elements that have multiplicative inverses mod n.

IMPORTANT: phi(n) must be kept secret!
If an attacker knows phi(n), they can compute:
d = e^(-1) mod phi(n)
which breaks the cryptosystem.

In fact, knowing phi(n) is equivalent to knowing the factorization:
Given n and phi(n), we can solve for p and q:
p + q = n - phi(n) + 1
p * q = n
This is a quadratic equation with solutions p and q.

The public exponent e must satisfy:

1. 1 < e < phi(n)
2. gcd(e, phi(n)) = 1 (so e has an inverse mod phi(n))

Common choices:

• e = 3: Fast encryption but vulnerable to some attacks
• e = 17: Another small prime
• e = 65537 (2^16 + 1): Standard choice, good balance

The value 65537 is popular because:

• It's prime, so likely coprime to phi(n)
• It has only two 1-bits (Hamming weight 2), making exponentiation fast
• It's large enough to resist small exponent attacks

The private exponent d is the modular inverse of e modulo phi(n):
d * e ≡ 1 (mod phi(n))

This means: d * e = 1 + k * phi(n) for some integer k

d is computed using the Extended Euclidean Algorithm.

RSA relies on Euler's theorem (a generalization of Fermat's little theorem):

For any a coprime to n:
a^phi(n) ≡ 1 (mod n)

Since e * d ≡ 1 (mod phi(n)), we have:
e * d = 1 + k * phi(n) for some integer k

Therefore, for any message m coprime to n:
(m^e)^d = m^(ed) = m^(1 + kphi(n)) = m * (m^phi(n))^k ≡ m * 1^k ≡ m (mod n)

Similarly:
(m^d)^e ≡ m (mod n)

This shows that encryption and decryption are inverse operations.

Digital signatures provide authentication, integrity, and non-repudiation.
RSA signatures work by "encrypting" with the private key.

Signature Scheme:
• Sign: s = H(m)^d mod n (sign hash of message)
• Verify: H(m) = s^e mod n (verify using public key)

Why Signatures Work:
Only the holder of the private key d can compute s = h^d mod n.
Anyone with the public key (n, e) can verify s^e ≡ h (mod n).

Security Considerations:
• Always sign a hash of the message, not the message itself
• Use proper padding schemes (PSS for RSA signatures)
• The hash function must be collision-resistant

Textbook RSA Signature (for education only, not secure!):
Sign: s = m^d mod n
Verify: m' = s^e mod n, check if m' = m

This is insecure because:

1. Signatures are malleable
2. Existential forgery is possible
3. Long messages don't fit

Problem 1: Message Size
RSA can only sign messages m < n. Real messages are much larger.

Problem 2: Existential Forgery
Attacker can create valid signatures for "random" messages:

1. Pick random s
2. Compute m = s^e mod n
3. (s, m) is a valid signature pair!

Solution: Sign H(m) where H is a cryptographic hash function

Proper RSA signature:
Sign: s = H(m)^d mod n
Verify: H(m) = s^e mod n

The hash function H must be:

• Collision resistant: Hard to find m1 != m2 with H(m1) = H(m2)
• Preimage resistant: Hard to find m given H(m)
• Second preimage resistant: Given m1, hard to find m2 with H(m1) = H(m2)

RSA signatures can be malleable: given a valid signature,
an attacker can sometimes create another valid signature
for a related message.

Example: Given signatures s1 for m1 and s2 for m2,
attacker can create signature s1s2 for m1m2.

RSA-PSS is the recommended padding scheme for RSA signatures.
It adds randomness (salt) to make signatures non-deterministic.

PSS Signature:

1. Generate random salt s
2. Compute m' = Hash(padding || Hash(M) || salt)
3. Apply mask generation function
4. Sign the padded value

Benefits:

• Provably secure in the random oracle model
• Non-deterministic (different signature each time)
• Prevents various attacks on PKCS#1 v1.5

IMPORTANT: Never use the same key for both signing and encryption!

Reason: Different security requirements and attack surfaces.

Attack example:

1. Attacker sends ciphertext c to victim
2. Victim decrypts and "signs" the result: s = c^d mod n
3. Attacker now has m = c^d mod n (the decryption!)

Solution: Maintain separate key pairs for encryption and signing.

Blind signatures allow someone to get a signature without
revealing what they're signing. Useful for:

• Anonymous digital cash
• Secret voting
• Credential issuance

Protocol:

1. User blinds message: m' = m * r^e mod n (r is random)
2. Signer signs blinded message: s' = (m')^d mod n
3. User unblinds: s = s' * r^(-1) mod n
4. Result: s is valid signature on m!

ElGamal encryption is a public-key encryption scheme based on the
Diffie-Hellman key exchange. It was proposed by Taher ElGamal in 1985.

Key Insight:
ElGamal is "Diffie-Hellman with message blinding":

1. Perform ephemeral DH to get shared secret K = g^(xr)
2. Use K to blind the message: c2 = m * K

Security:
• IND-CPA secure under DDH assumption
• Ciphertext is 2x message size (expansion factor 2)
• Randomized: encrypting same message gives different ciphertexts

Properties:
• Homomorphic: E(m1) * E(m2) = E(m1 * m2)
• Probabilistic encryption
• Requires random number generation during encryption

ElGamal Key Generation:

1. Choose prime p and generator g
2. Choose random private key x in [1, p-2]
3. Compute public key y = g^x mod p

Public key: (p, g, y)
Private key: x

ElGamal Encryption:

To encrypt message m (0 < m < p):

1. Choose random r in [1, p-2]
2. Compute c1 = g^r mod p
3. Compute c2 = m * y^r mod p

Ciphertext: (c1, c2)

Understanding:

• c1 = g^r is ephemeral DH public value
• y^r = (g^x)^r = g^(xr) is shared DH secret
• c2 = m * g^(xr) blinds the message with shared secret

ElGamal Decryption:

Given ciphertext (c1, c2) and private key x:

1. Compute shared secret s = c1^x mod p
2. Compute message m = c2 * s^(-1) mod p

Why this works:

• c1 = g^r, so c1^x = g^(rx) = g^(xr)
• c2 = m * g^(xr), so c2 * (g^(xr))^(-1) = m

ElGamal is probabilistic: same message encrypts to different ciphertexts.
This is essential for semantic security (IND-CPA).

ElGamal is multiplicatively homomorphic:
E(m1) * E(m2) = E(m1 * m2)

Given (c1, c2) = E(m1) and (c1', c2') = E(m2):
(c1 * c1', c2 * c2') = E(m1 * m2)

This enables computation on encrypted data!

ElGamal security under DDH:

If DDH is hard, then ElGamal is IND-CPA secure.

Proof sketch:

• Real: (g, g^x, g^r, g^(xr))
• Fake: (g, g^x, g^r, g^z) for random z
• Ciphertext uses g^(xr), which is indistinguishable from random
• Therefore, c2 = m * g^(xr) hides m

ElGamal is malleable: given E(m), attacker can create E(k*m) for known k.

Attack: Given (c1, c2) = E(m), compute (c1, c2 * k) = E(m * k)

This means ElGamal is NOT CCA-secure (chosen ciphertext attack).
Use hybrid encryption or ElGamal-KEM for CCA security.

ElGamal encrypts elements of (Z/pZ)*, not arbitrary byte strings.
We need encoding schemes:

1. Simple: Interpret bytes as integer < p
2. With padding: Add structure for verification
3. Hybrid: Encrypt symmetric key, use symmetric cipher for data

This tutorial covers digital signatures based on the discrete logarithm problem:
ElGamal signatures and the more efficient Schnorr signature scheme.

Historical Context:
• ElGamal signatures (1985): First DL-based signature scheme
• Schnorr signatures (1989): More efficient, simpler security proof
• DSA (1991): NIST standard based on ElGamal
• ECDSA: Elliptic curve version of DSA
• EdDSA: Modern Schnorr-based scheme (Ed25519)

Security Basis:
All these schemes rely on the hardness of the Discrete Logarithm Problem.

ElGamal Signature Scheme:

Key Generation:

• Private key: x (random in [1, p-2])
• Public key: y = g^x mod p

Signing message m:

1. Choose random k coprime to p-1
2. r = g^k mod p
3. s = (H(m) - x*r) * k^(-1) mod (p-1)
4. Signature: (r, s)

Verification:
Check: g^H(m) = y^r * r^s (mod p)

Schnorr Signatures (simpler and more efficient):

Signing message m:

1. Choose random k
2. R = g^k mod p
3. e = H(R || m)
4. s = k + x*e mod q
5. Signature: (R, s) or (e, s)

Verification:
Check: R = g^s * y^(-e) mod p
Or equivalently: g^s = R * y^e mod p

Security of DL-based signatures:

1. Unforgeability: Relies on DLP

   • Finding x from y = g^x would allow forging signatures

2. Nonce reuse attack:

   • If same k is used twice, private key can be recovered!

3. Weak random k:

   • Biased k can leak information about x

RFC 6979: Deterministic DSA/ECDSA

Instead of random k, compute:
k = HMAC_DRBG(private_key, message_hash)

Benefits:

• No need for quality random numbers
• Same message always gives same signature (for same key)
• No risk of nonce reuse

This is used by Bitcoin and many other systems.

The Diffie-Hellman (DH) key exchange protocol allows two parties to establish
a shared secret over an insecure channel without prior shared secrets.

Historical Significance:
Published by Whitfield Diffie and Martin Hellman in 1976, this was the first
practical method for establishing a shared key over an insecure channel.
It revolutionized cryptography and laid the foundation for public-key crypto.

Protocol Overview:

1. Alice and Bob agree on public parameters: prime p and generator g
2. Alice picks secret a, sends A = g^a mod p
3. Bob picks secret b, sends B = g^b mod p
4. Alice computes K = B^a mod p = g^(ab) mod p
5. Bob computes K = A^b mod p = g^(ab) mod p
6. Both have the same shared secret K!

Security Basis:
Security relies on the Discrete Logarithm Problem (DLP):
Given g, p, and g^x mod p, it's hard to find x.

The public parameters are:

• A large prime p (the modulus)
• A generator g of the multiplicative group (Z/pZ)*

These are shared publicly and reused across many key exchanges.

A generator g of (Z/pZ)* satisfies:

• {g^1, g^2, ..., g^(p-1)} = {1, 2, ..., p-1} mod p
• The order of g is exactly p-1

To find a generator:

1. For each candidate g in {2, 3, ...}
2. Check that g^((p-1)/q) != 1 for all prime factors q of p-1
3. If all checks pass, g is a generator

DIFFIE-HELLMAN KEY EXCHANGE

Public parameters: p (prime), g (generator)

Alice: Bob:

Choose secret a Choose secret b
Compute A = g^a mod p Compute B = g^b mod p

         Alice sends A to Bob
         Bob sends B to Alice

Compute K = B^a mod p Compute K = A^b mod p
K = g^(ab) mod p K = g^(ab) mod p

Both now share secret K!

An eavesdropper (Eve) observes:

• Public parameters: p, g
• Alice's public value: A = g^a mod p
• Bob's public value: B = g^b mod p

To compute K = g^(ab), Eve would need to find a from A (or b from B).
This is the Discrete Logarithm Problem (DLP).

The Computational Diffie-Hellman (CDH) Problem:

Given: g, p, A = g^a, B = g^b
Compute: g^(ab) mod p

Note: CDH doesn't require finding a or b!
It only asks for the shared secret.

CDH is believed to be as hard as DLP, but this is not proven.

DH parameters can be reused. Each party keeps one private key
and can exchange keys with multiple parties.

Static DH: Same key pair used for many exchanges

• Pro: Can pre-compute public key
• Con: If private key is compromised, all past sessions are compromised

Ephemeral DH (DHE): New key pair for each exchange

• Pro: Forward secrecy (past sessions safe even if key leaked)
• Con: Must generate new keys each time

Best practice: Use ephemeral keys (DHE, ECDHE)

The shared secret K should NOT be used directly as an encryption key.
Instead, derive keys using a Key Derivation Function (KDF).

Common KDFs:

• HKDF (HMAC-based KDF)
• SHA-256(K || context)
• PBKDF2 (for password-based scenarios)

Choosing secure parameters for Diffie-Hellman is critical. Poor parameter
choice can make the system vulnerable to practical attacks.

Key Decisions:

1. Prime size: How large should p be?
2. Prime structure: Safe prime vs. DSA-style prime
3. Generator choice: What properties should g have?
4. Standard vs. custom: Use published parameters or generate new ones?

Historical Lessons:
• Logjam attack (2015): 512-bit DH was broken
• Weak DH study: 8% of HTTPS used shared 1024-bit primes
• NOBUS concerns: Pre-computed attacks on shared parameters

DH security level depends on the best known attack:

• Index calculus / Number Field Sieve
• Complexity: L[1/3, c] = exp(c * (log n)^(1/3) * (log log n)^(2/3))

Equivalent security levels:
Symmetric bits | RSA/DH bits | ECC bits
80 | 1024 | 160
112 | 2048 | 224
128 | 3072 | 256
192 | 7680 | 384
256 | 15360 | 512

A safe prime p satisfies: p = 2q + 1 where q is also prime.

Benefits:

• (Z/pZ)* has order p-1 = 2q with only one large factor
• Pohlig-Hellman attack gives no advantage
• Order-q subgroup is cyclic of prime order

Properties:

• ~50% of subgroup elements are generators
• Quadratic residues form the order-q subgroup

Alternative: p and q where q divides p-1, but q << p

Structure: p = kq + 1 for some k

Benefits:

• Smaller q means smaller exponents (faster)
• Can use 256-bit q with 2048-bit p

Used in:

• DSA (Digital Signature Algorithm)
• Some DH parameter sets

For safe prime p = 2q + 1:

To find generator of (Z/pZ)*:

• Check g^q != 1 and g^2 != 1 (mod p)
• Or simply check g^q != 1 and g != p-1

To find generator of order-q subgroup:

• Compute g = r^2 mod p for random r
• This gives element of order q (or 1, which we skip)

Standard parameters are published and widely reviewed.
Using standard parameters avoids the need to trust parameter generation.

RFC 3526: MODP Groups for IKE (IPsec):

• 1536-bit MODP Group
• 2048-bit MODP Group
• 3072-bit MODP Group
• 4096-bit MODP Group
• 6144-bit MODP Group
• 8192-bit MODP Group

RFC 7919: FFDHE (Finite Field DH with Ephemeral keys) for TLS:

• ffdhe2048, ffdhe3072, ffdhe4096, ffdhe6144, ffdhe8192

Dangers of generating your own parameters:

1. Trapdoor primes: p can be chosen so attacker knows factorization
2. Weak primes: Poor randomness leads to predictable parameters
3. NOBUS attacks: If parameters are shared, precomputation helps everyone

The Logjam attack showed that shared 1024-bit primes allowed
nation-state level attackers to break DH in real-time.

When receiving DH parameters, validate them:

1. p is prime (Miller-Rabin)
2. p is large enough (>= 2048 bits)
3. g is valid generator (check order)
4. For safe primes: (p-1)/2 is prime
5. Public value is in valid range: 2 <= y <= p-2
6. Public value is in correct subgroup: y^q = 1 (mod p)

When receiving a public value y = g^x:

1. Range check: 2 <= y <= p-2
2. Subgroup check: y^q = 1 (mod p) for order-q subgroup
3. Small subgroup attack prevention

Elliptic Curve Diffie-Hellman (ECDH) offers:

• Same security with smaller keys (256-bit vs 3072-bit)
• Faster computation
• Standard curves avoid parameter generation issues

Recommended curves:

• P-256 (NIST, widely supported)
• P-384 (NIST, higher security)
• X25519 (Curve25519, modern choice)
• X448 (Curve448, highest security)

This tutorial explores the security foundations of Diffie-Hellman:
the Discrete Logarithm Problem (DLP), Computational Diffie-Hellman (CDH),
and Decisional Diffie-Hellman (DDH) assumptions.

Security Assumptions Hierarchy:
DLP <= CDH <= DDH

If DLP is easy, then CDH is easy.
If CDH is easy, then DDH is easy.
(Reverse implications are not known to hold in general.)

Practical Implications:
Different cryptographic constructions rely on different assumptions.
Understanding these helps choose appropriate parameters and protocols.

DLP Definition:

Given: Prime p, generator g, and h = g^x mod p
Find: x (the discrete logarithm of h base g)

This is believed to be computationally hard for large p.

Methods for solving DLP (with increasing sophistication):

1. Brute Force: O(p) - try all exponents
2. Baby-Step Giant-Step: O(sqrt(p)) time and space
3. Pollard's Rho: O(sqrt(p)) time, O(1) space
4. Index Calculus: Sub-exponential for prime fields
5. Number Field Sieve: Best known for large primes

CDH Problem:

Given: Prime p, generator g, A = g^a mod p, B = g^b mod p
Compute: g^(ab) mod p

Note: CDH doesn't require finding a or b!

CDH is "weaker" than DLP:

• If you can solve DLP, you can solve CDH
• Reverse is not known (in general)

DDH Problem:

Given: Prime p, generator g, A = g^a, B = g^b, and C
Decide: Is C = g^(ab) or is C random?

DDH is "weaker" than CDH:

• If you can solve CDH, you can solve DDH (compute g^(ab) and compare)
• Reverse is not known

DDH is the weakest (easiest) of the three problems.

The hierarchy from hardest to easiest:

DLP >= CDH >= DDH

• DLP hard => CDH hard => DDH hard
• DDH easy does NOT imply CDH easy
• CDH easy does NOT imply DLP easy

In some groups, DDH is easy but CDH is hard!
Example: Bilinear groups (used in pairing-based crypto)

Security depends heavily on parameter choice:

1. Small p: DLP easily solved by baby-step giant-step
2. Smooth p-1: Pohlig-Hellman attack reduces DLP to small subgroups
3. Non-prime-order subgroup: Small subgroup attacks
4. Weak generator: May generate small subgroup

A safe prime p satisfies: p = 2q + 1 where q is also prime.
The prime q is called a Sophie Germain prime.

Benefits:

• p - 1 = 2q has only one large factor (q)
• Pohlig-Hellman gives no advantage
• The subgroup of order q has strong security

When using safe prime p = 2q + 1:

• (Z/pZ)* has order p-1 = 2q
• Subgroups have order 1, 2, q, or 2q
• We work in the order-q subgroup for security

Working in order-q subgroup:

• Use g = r^2 mod p for random r (squares form order-q subgroup)
• Or verify g^q = 1 mod p

If an attacker can force the DH computation into a small subgroup,
they can recover the private key modulo the subgroup order.

Attack:

1. Send A' = h where h has small order k
2. Victim computes K = A'^b = h^b = h^(b mod k)
3. Attacker can brute-force b mod k in k steps
4. Repeat with different small-order elements to recover full b

Defense: Validate received values are in the correct subgroup

This tutorial explores various elliptic curves and their properties,
building intuition for different curve types and their applications.

Curve Families:
Different curves have different properties:
• Supersingular curves: Special structure, used in isogeny crypto
• Ordinary curves: Most common, used in ECDSA/ECDH
• Curves with j = 0 or 1728: Extra automorphisms
• Anomalous curves: #E = p (insecure for ECDLP!)

@module tutorial/elliptic-curves/examples

Hasse's theorem: For an elliptic curve E over F_q,

|#E(F_q) - (q + 1)| <= 2*sqrt(q)

This means:
q + 1 - 2sqrt(q) <= #E <= q + 1 + 2sqrt(q)

For F_97: 97 + 1 - 2sqrt(97) = 78.3...
97 + 1 + 2sqrt(97) = 117.7...
So #E is between 79 and 117

A curve E over F_p is SUPERSINGULAR if p | trace(Frobenius)
Equivalently, if #E = p + 1 (trace = 0)

Properties of supersingular curves:

• Embedding degree divides 6 (small!)
• j-invariant in F_p^2
• Used in isogeny-based cryptography (SIDH, SIKE)

Most cryptographic curves are ORDINARY (not supersingular)

Curves with j = 0:

• Extra automorphisms (order 6 instead of 2)
• Form: y^2 = x^3 + b (a = 0)

Curves with j = 1728:

• Extra automorphisms (order 4 instead of 2)
• Form: y^2 = x^3 + ax (b = 0)

An ANOMALOUS curve over F_p has #E = p.

WARNING: These curves are INSECURE for ECDLP!
The Smart-ASS attack solves ECDLP in polynomial time.

Never use anomalous curves for cryptography!

The trace t = p + 1 - #E determines the curve order.
By Hasse: |t| <= 2*sqrt(p)

The distribution of traces is related to the Sato-Tate conjecture
(now a theorem, proved by Taylor and collaborators).

Two curves over F_q with the same j-invariant are isomorphic
over the algebraic closure. They may or may not be isomorphic
over F_q itself (quadratic twist).

Points on an elliptic curve form an ABELIAN GROUP under the addition operation.
This algebraic structure is what makes elliptic curves useful for cryptography.

Group Properties:
For a set G with operation + to be an abelian group, it must satisfy:

1. Closure: For all P, Q in G, P + Q is in G
2. Associativity: (P + Q) + R = P + (Q + R)
3. Identity: There exists O such that P + O = P for all P
4. Inverses: For every P, there exists -P such that P + (-P) = O
5. Commutativity: P + Q = Q + P (makes it abelian)

Scalar Multiplication:
Given a point P and integer n, we can compute:
nP = P + P + ... + P (n times)

This is the fundamental operation in elliptic curve cryptography.

The Discrete Logarithm Problem:
Given P and Q = nP, finding n is called the Elliptic Curve Discrete
Logarithm Problem (ECDLP). This is believed to be computationally hard
for properly chosen curves.

@module tutorial/elliptic-curves/group-law

Computing nP naively takes n additions. The double-and-add algorithm
computes nP in O(log n) operations using the binary representation.

Example: Compute 13P
13 = 1101 in binary = 8 + 4 + 1 = 2^3 + 2^2 + 2^0
So 13P = 8P + 4P + P

We compute:
P (2^0 * P)
2P (2^1 * P)
4P (2^2 * P) = 2 * 2P
8P (2^3 * P) = 2 * 4P
Then: 13P = 8P + 4P + P

This takes ~2*log2(13) = ~8 operations instead of 13

The ORDER of a point P is the smallest positive integer n such that nP = O.

Every point on E(F_q) has finite order, and this order divides #E(F_q).

If P has prime order, P is called a generator of a cyclic subgroup.

The set {O, P, 2P, 3P, ..., (n-1)P} forms a cyclic subgroup of order n.

In cryptography, we work in large prime-order subgroups to ensure
the discrete logarithm problem is hard.

The curve order #E(F_q) is the total number of points on E over F_q,
including the point at infinity.

By Lagrange's theorem, the order of any point divides the curve order.

Given: P (base point) and Q (target point)
Find: n such that Q = nP

This is easy when n is small (brute force) but believed to be hard
for large n with properly chosen curves (256+ bit order).

Best known algorithms:

• Baby-step giant-step: O(sqrt(n)) time and space
• Pollard's rho: O(sqrt(n)) time, O(1) space
• Index calculus: Does NOT work efficiently for elliptic curves!

This is why EC crypto uses 256-bit groups while RSA needs 2048+ bits.

The group E(F_q) is always isomorphic to Z/n1 x Z/n2 where n2 | n1.

• If n2 = 1: The group is cyclic (one generator suffices)
• If n2 > 1: The group needs two generators

For cryptographic curves, we typically use:

• Prime order curves: E(F_q) is cyclic of prime order p
• Cofactor curves: #E = h * p where p is prime and h (cofactor) is small

The magic of elliptic curves lies in the fact that points on the curve
can be "added" together to produce another point on the curve.

Geometric Intuition:
Consider two points P and Q on an elliptic curve y^2 = x^3 + ax + b.

To add P + Q:

1. Draw a line through P and Q
2. This line intersects the curve at exactly one more point, R
3. Reflect R across the x-axis to get P + Q

Why does this work? Bezout's theorem says a degree-2 curve (the line)
and a degree-3 curve (the cubic) intersect at exactly 2*3 = 6 points
(counting multiplicity and points at infinity). Since the line has
degree 1 in y, it contributes 3 intersection points: P, Q, and R.

To double P (compute P + P = 2P):

1. Draw the tangent line to the curve at P
2. This line intersects the curve at one more point, R
3. Reflect R across the x-axis to get 2P

The Point at Infinity:
When P = -Q (same x-coordinate, opposite y), the line through P and Q
is vertical and doesn't intersect the curve again. We say it intersects
at the "point at infinity" O.

The point at infinity O serves as the identity element: P + O = P for all P.

@module tutorial/elliptic-curves/point-addition

Elliptic curves are algebraic curves defined by cubic equations that have been
fundamental to number theory since the 17th century. In modern cryptography,
they provide the most efficient public-key cryptosystems known.

What is an Elliptic Curve?:
An elliptic curve is NOT an ellipse! The name comes from elliptic integrals,
which arise when computing the arc length of an ellipse.

An elliptic curve over a field K is the set of solutions (x, y) to a cubic
equation, together with a special "point at infinity" denoted O.

The Weierstrass Equation:
The most general form is the long Weierstrass form:

y^2 + a1xy + a3y = x^3 + a2x^2 + a4*x + a6

The coefficients [a1, a2, a3, a4, a6] are called the a-invariants.
The strange numbering comes from a weighted degree system.

Short Weierstrass Form:
For fields with characteristic not equal to 2 or 3, we can simplify to:

y^2 = x^3 + a*x + b

This is the short Weierstrass form, used in most cryptographic applications.
Here a = a4 and b = a6, with a1 = a2 = a3 = 0.

Non-Singularity Condition:
For the curve to be an elliptic curve (and not singular), the discriminant
must be non-zero:

Delta = -16(4a^3 + 27b^2) != 0

A singular curve has a "cusp" or "node" and does NOT form a group.

The j-Invariant:
The j-invariant classifies elliptic curves up to isomorphism:

j = 1728 * 4a^3 / (4a^3 + 27b^2)

Two curves over an algebraically closed field are isomorphic iff they have
the same j-invariant.

@module tutorial/elliptic-curves/weierstrass-form

Special values of j have extra symmetry:

• j = 0: Curves with automorphism group of order 6
• j = 1728: Curves with automorphism group of order 4
• Other j: Automorphism group of order 2 (just +P and -P)

A singular curve has discriminant = 0 and does NOT form a group.
The library will throw an error if you try to create one.

For y^2 = x^3 + ax + b, singularity occurs when 4a^3 + 27b^2 = 0.

Example: y^2 = x^3 (both a=0 and b=0) has a cusp at (0,0).
Example: y^2 = x^3 + x^2 has a node at (0,0).

The Weierstrass form is universal:

1. Every elliptic curve over a field can be written in Weierstrass form
   (possibly the long form for char 2 or 3)

2. Standard form makes comparison easy (via j-invariant)

3. Formulas for point addition are well-known and optimized

4. Cryptographic standards (NIST, SEC, etc.) use this form

Other forms exist and can be more efficient:

• Montgomery form: By^2 = x^3 + Ax^2 + x (used in Curve25519)
• Edwards form: x^2 + y^2 = 1 + dx^2y^2 (used in Ed25519)
• But these can all be converted to Weierstrass form

Elliptic curves over prime fields F_p are the workhorses of modern cryptography.
Every standard curve (secp256k1, P-256, P-384, etc.) is defined over a prime field.

Why Prime Fields?:

1. Simple arithmetic: Operations are just modular arithmetic
2. Well-understood: Decades of cryptanalysis and optimization
3. Hardware support: Many CPUs have optimized big integer ops
4. Standards compliance: NIST, SEC, Brainpool all use prime fields

The Curve Equation:
Over F_p (p > 3), elliptic curves are given in short Weierstrass form:

y^2 = x^3 + ax + b (mod p)

where a, b are elements of F_p and 4a^3 + 27b^2 != 0 (non-singular).

@module tutorial/elliptic-curves/ec-over-fp

In F_p, all arithmetic is done modulo p:

• Addition: (a + b) mod p
• Subtraction: (a - b) mod p
• Multiplication: (a * b) mod p
• Division: a * b^(-1) mod p (using Fermat's little theorem: b^(-1) = b^(p-2))

Random point generation is crucial for:

• Key generation (private key -> random scalar -> public key)
• Randomized protocols (e.g., ElGamal encryption)
• Testing and verification

Real cryptographic curves use primes of 256+ bits.
Common choices:

• secp256k1: p = 2^256 - 2^32 - 977
• P-256: p = 2^256 - 2^224 + 2^192 + 2^96 - 1
• P-384: p = 2^384 - 2^128 - 2^96 + 2^32 - 1

These primes are chosen for:

1. Efficient reduction (special form)
2. Security (large enough to resist attacks)
3. Compatibility (standard bit sizes)

A point (x, y) exists on y^2 = x^3 + ax + b iff x^3 + ax + b is a
quadratic residue (QR) in F_p.

In F_p with p odd:

• Exactly (p-1)/2 non-zero elements are QRs
• Testing: a is QR iff a^((p-1)/2) = 1 (Euler's criterion)
• Square root: Use Tonelli-Shanks algorithm

For E/F_p, the Hasse bound says:

|#E(F_p) - (p + 1)| <= 2*sqrt(p)

Write #E = p + 1 - t, where t is the "trace of Frobenius".
Then |t| <= 2*sqrt(p).

While most cryptographic applications use prime fields F_p, elliptic curves
can also be defined over extension fields F_q where q = p^n for some n > 1.

Extension Fields:
An extension field F_q = F_{p^n} is constructed by:

1. Taking a prime field F_p
2. Adjoining a root of an irreducible polynomial of degree n

Example: F_4 = F_2[x]/(x^2 + x + 1)
Elements: {0, 1, alpha, alpha+1} where alpha^2 + alpha + 1 = 0

Characteristic 2 Fields:
Binary extension fields F_{2^n} were popular for:
• Hardware efficiency (XOR and shift operations)
• NIST B-curves (B-163, B-233, B-283, B-409, B-571)

However, recent index calculus advances have made them less attractive.

Tower Fields:
For pairing-based cryptography, we often work with tower extensions:
• F_p -> F_{p^2} -> F_{p^6} -> F_{p^12}
• Used in BLS signatures, BN curves, etc.

@module tutorial/elliptic-curves/ec-over-fq

While sagemath-ts currently focuses on prime fields, understanding
extension fields is important for:

• Pairing-based cryptography
• Characteristic 2 curves (historical)
• Torsion point analysis
• Complex multiplication theory

For a curve E over F_q, the Frobenius map is:
phi: (x, y) -> (x^q, y^q)

Properties:

1. phi is an endomorphism of E
2. phi fixes exactly E(F_q) (the F_q-rational points)
3. phi satisfies: phi^2 - t*phi + q = 0 (in the endomorphism ring)
   where t = trace of Frobenius

For prime fields F_p:
(x, y) -> (x^p, y^p) = (x, y) for all points in E(F_p)
(since x, y are in F_p and x^p = x by Fermat's little theorem)

Given E/F_p, we can consider points with coordinates in extension fields:

E(F_p) subset E(F_{p^2}) subset E(F_{p^3}) subset ...

Example: E might have 100 points over F_p but 10000 points over F_{p^2}.

The TORSION POINTS E[n] (points P with nP = O) often require
extension fields to exist fully.

For E[n] to be fully defined over F_q:

• We need q^k - 1 divisible by n for some k (the embedding degree)

The EMBEDDING DEGREE k of E with respect to n is the smallest k such that
n divides q^k - 1.

This is the extension degree needed for the n-torsion to embed into
the multiplicative group F_{q^k}*.

For pairing-based crypto:

• k should be moderate (6-48) for efficiency
• k must provide adequate security in F_{q^k}*

BN curves: k = 12 (popular for SNARKs)
BLS curves: k = 12 or 24

Binary fields F_{2^n} were popular because:

• Addition is XOR (very fast in hardware)
• Squaring is efficient (Frobenius map)
• Field multiplication can use shift-and-XOR

Curve equation in characteristic 2 (non-supersingular):
y^2 + xy = x^3 + ax^2 + b

NIST B-curves: B-163, B-233, B-283, B-409, B-571

HOWEVER: Recent advances in index calculus for binary fields
(Joux et al., 2014) have made them less attractive for new deployments.
Modern recommendations favor prime fields.

Pairing-based cryptography uses bilinear maps:
e: G1 x G2 -> GT

where G1, G2 are subgroups of E and GT is a subgroup of F_{q^k}*.

For efficiency, F_{q^k} is constructed as a tower:
F_p -> F_{p^2} -> F_{p^6} -> F_{p^12}

Example for BN254 (k=12):
F_{p^2} = F_p[u]/(u^2 + 1)
F_{p^6} = F_{p^2}[v]/(v^3 - (9+u))
F_{p^12} = F_{p^6}[w]/(w^2 - v)

This tower structure enables efficient arithmetic and the
"optimal ate pairing" computation.

The Weil pairing e_n: E[n] x E[n] -> mu_n is a bilinear map where
mu_n is the group of n-th roots of unity in F_{q^k}*.

Properties:

1. Bilinear: e_n(aP, bQ) = e_n(P, Q)^(ab)
2. Non-degenerate: e_n(P, Q) != 1 for independent P, Q
3. Alternating: e_n(P, P) = 1

The Tate pairing and its variants (ate, optimal ate) are used in practice.

Applications:

• Identity-based encryption
• Short signatures (BLS)
• Zero-knowledge proofs (Groth16, PLONK)

The set of rational points E(F_q) on an elliptic curve forms an
abelian group under point addition. Understanding this structure
is crucial for cryptographic applications.

The Structure Theorem:
For any elliptic curve E over F_q:

E(F_q) is isomorphic to Z/n1 x Z/n2

where n2 divides n1, and n1 * n2 = #E(F_q).
• If n2 = 1: The group is CYCLIC (one generator suffices)
• If n2 > 1: The group needs TWO generators

Cryptographic Implications:
• We want large prime-order subgroups for ECDLP hardness
• Ideally, #E is prime (fully cyclic)
• Small cofactor h = #E / (prime order) is acceptable

@module tutorial/elliptic-curves/group-structure

E(F_q) = Z/n1 x Z/n2 where:

• n2 divides n1
• n2 divides gcd(n1, q-1)
• n1 * n2 = #E(F_q)

Most commonly, n2 = 1 and the group is cyclic.

When E(F_q) is cyclic:

• Any non-identity point of order #E generates the whole group
• Every point P satisfies P = nG for some n (discrete log exists)
• This is the ideal case for ECDH and ECDSA

When n2 > 1, the group has the form Z/n1 x Z/n2.
This happens when the curve has "extra" torsion points.

For example, if #E = 12 and n2 = 2:
E(F_q) = Z/6 x Z/2

This means there are three points of order 2 (the full 2-torsion is rational).

By Lagrange's theorem, the order of any point divides #E(F_q).

For cryptography, we want points of LARGE PRIME ORDER.
If #E = h * n where n is prime:

• h is the "cofactor"
• Points of order n form a subgroup where G has order n

To find a generator of the prime-order subgroup:

1. Factor #E = h * n where n is the largest prime factor
2. Pick a random point P
3. Compute G = h * P
4. If G != O, then G has order n (or a divisor)

Repeat until you get a point of order exactly n.

Given G (generator) and P = nG (public key), finding n is the ECDLP.

The baby-step giant-step algorithm solves this in O(sqrt(order)) time.

For cryptographic sizes (256 bits), sqrt(2^256) = 2^128, which is
still infeasible.

The n-TORSION subgroup E[n] consists of all points P with nP = O.

Over an algebraically closed field:
E[n] is isomorphic to Z/n x Z/n (for n coprime to characteristic)

Over F_q, E[n] might be smaller:
En is a subgroup of E[n]

The full n-torsion becomes rational over F_{q^k} where k is the
embedding degree.

Determining the number of points on an elliptic curve is fundamental
to elliptic curve cryptography. The curve order affects:
• Security (larger order = harder ECDLP)
• Protocol correctness (need to know group structure)
• Cofactor handling (order = h * n where n is prime)

Hasse's Theorem:
For an elliptic curve E over F_q:

|#E(F_q) - (q + 1)| <= 2*sqrt(q)

This means the order is roughly q, within a "square root error".

The Trace of Frobenius:
Define t = q + 1 - #E(F_q). This "trace" satisfies |t| <= 2*sqrt(q).
The trace encodes all information about the curve order.

@module tutorial/elliptic-curves/point-counting

Hasse's Theorem (1933):

For E/F_q, let N = #E(F_q). Then:
(sqrt(q) - 1)^2 <= N <= (sqrt(q) + 1)^2

Or equivalently: |N - (q + 1)| <= 2*sqrt(q)

The ratio t/sqrt(q) (where t is the trace) is bounded between -2 and 2.

The Sato-Tate conjecture (now theorem) describes how traces
are distributed as we vary over curves:

For random curves over F_p, the normalized trace t/(2*sqrt(p))
follows the semicircle distribution: f(x) = (2/pi)*sqrt(1 - x^2)

This has important implications for:

• Expected security of random curves
• Statistical tests for curve generation

Schoof's algorithm (1985) computes #E(F_q) in polynomial time.

Key insight: Work modulo small primes l and use the Chinese Remainder Theorem.

For each prime l:

1. Find the l-torsion polynomial (division polynomial)
2. Compute Frobenius action on E[l]
3. Determine t mod l

Continue until we have enough primes to determine t uniquely
(need product > 4*sqrt(q)).

Improvements (SEA algorithm):

• Schoof-Elkies-Atkin uses isogenies for "Elkies primes"
• Much faster in practice: quasi-quadratic time

The library uses PARI's implementation internally.

Some curves have special structure that makes counting easier:

1. Supersingular curves: t = 0 (mod p), so #E = p + 1 for p > 3
2. Anomalous curves: #E = p (trace t = 1)
3. Curves with CM: Order determined by CM discriminant

Given #E(F_q), we can compute #E(F_{q^n}) using the trace.

The recurrence:
#E(F_{q^n}) = q^n + 1 - alpha^n - beta^n

where alpha, beta are roots of X^2 - tX + q = 0.

Equivalently, there's a linear recurrence:
a_n = t * a_{n-1} - q * a_{n-2}
where a_n = alpha^n + beta^n = q^n + 1 - #E(F_{q^n})

Choosing the right elliptic curve is critical for security and performance.
This tutorial covers standard curves used in practice and their properties.

Why Standard Curves?:
Using well-vetted, standardized curves provides:
• Security assurance (extensive cryptanalysis)
• Interoperability (everyone uses the same parameters)
• Optimized implementations (hardware and software)
• Regulatory compliance (NIST, FIPS requirements)

Curve Families:

1. NIST curves (P-256, P-384, P-521)
2. Koblitz curves (secp256k1 used by Bitcoin)
3. Modern curves (Curve25519, Ed25519)
4. Pairing-friendly curves (BN254, BLS12-381)

@module tutorial/elliptic-curves/curve-selection

secp256k1 Parameters:

Prime p = 2^256 - 2^32 - 977
= 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE FFFFFC2F

Curve: y^2 = x^3 + 7 (a = 0, b = 7)

Order n = 0xFFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFE BAAEDCE6 AF48A03B BFD25E8C D0364141

Generator G:
Gx = 0x79BE667E F9DCBBAC 55A06295 CE870B07 029BFCDB 2DCE28D9 59F2815B 16F81798
Gy = 0x483ADA77 26A3C465 5DA4FBFC 0E1108A8 FD17B448 A6855419 9C47D08F FB10D4B8

Cofactor h = 1 (prime order - ideal!)

P-256 Parameters:

Prime p = 2^256 - 2^224 + 2^192 + 2^96 - 1

Curve: y^2 = x^3 - 3x + b (a = -3 for efficiency)

The parameter b is chosen using SHA-1 of a seed (verifiably random).

Properties:

• Random curve (not Koblitz)
• a = -3 optimization for point doubling
• Prime order (cofactor h = 1)
• Widely deployed in TLS, code signing, etc.

Curve25519 (Montgomery form):
y^2 = x^3 + 486662x^2 + x over F_p where p = 2^255 - 19

Ed25519 (twisted Edwards form):
-x^2 + y^2 = 1 - (121665/121666)x^2y^2 over the same field

These are birationally equivalent curves designed by Daniel J. Bernstein.

Advantages:

• Complete addition formulas (no special cases)
• Fast, constant-time implementations
• Designed to resist implementation errors
• Smaller code size

Curve25519: Used for ECDH (X25519)
Ed25519: Used for signatures (EdDSA)

BLS12-381 is designed for efficient pairings:
e: G1 x G2 -> GT

Parameters:

• Embedding degree k = 12
• ~128-bit security for both ECDLP and pairing attacks
• Supports BLS signatures and SNARKs

G1: Points on E(F_p)
G2: Points on E'(F_{p^2}) (twisted curve)
GT: Subgroup of F_{p^12}*

When implementing EC crypto, use standardized parameters:

1. For general TLS/HTTPS: P-256
2. For Bitcoin/Ethereum: secp256k1
3. For modern protocols: X25519 (ECDH), Ed25519 (signatures)
4. For zk-proofs: BLS12-381

NEVER generate your own curve parameters!

• Curve generation is subtle and easy to get wrong
• Standard curves have been extensively analyzed
• Custom curves raise red flags in security audits

ECDH is a key agreement protocol that allows two parties to establish
a shared secret over an insecure channel. It is the elliptic curve
analog of the classic Diffie-Hellman protocol.

The Protocol:
Setup: A curve E over F_p, a base point G of prime order n.

1. Alice picks random a in [1, n-1], computes A = aG (public key)
2. Bob picks random b in [1, n-1], computes B = bG (public key)
3. Alice and Bob exchange A and B publicly
4. Alice computes S = a * B = a * (bG) = abG
5. Bob computes S = b * A = b * (aG) = abG

Both arrive at the same shared secret S = abG!

Security:
An eavesdropper sees G, A = aG, B = bG but cannot compute S = abG.
This is the Elliptic Curve Computational Diffie-Hellman (ECCDH) problem,
which is believed to be as hard as ECDLP.

@module tutorial/elliptic-curves/ecdh

Each party generates a key pair:

• Private key: random integer a in [1, n-1]
• Public key: A = aG

Public information (visible to eavesdroppers):

• Curve E, base point G, order n
• Alice's public key A = aG
• Bob's public key B = bG

Secret information:

• Alice's private key a
• Bob's private key b
• Shared secret S = abG

The shared secret S is a point on the curve.
To use it as a symmetric key, we need to derive bytes from it.

Common approaches:

1. Use the x-coordinate: key = Hash(x-coordinate of S)
2. Use both coordinates: key = Hash(x || y)
3. Use a KDF: key = HKDF(S, info, length)

Standards like ECIES, X25519, ECDH in TLS specify exact methods.

The ECDH Problem:
Given G, A = aG, B = bG, compute S = abG.

This is the Computational Diffie-Hellman (CDH) problem on elliptic curves.

Reductions:

• CDH <= ECDLP: If you can solve ECDLP, recover a from (G, aG),
  then compute S = a * B.

It's unknown whether CDH = ECDLP, but they're believed equivalent.

Best attacks:

• Generic: Pollard rho, O(sqrt(n)) time
• No index calculus attack for properly chosen curves!

ECDH alone does NOT provide authentication!

A man-in-the-middle (Mallory) can:

1. Intercept Alice's A, send own M_A to Bob
2. Intercept Bob's B, send own M_B to Alice
3. Establish separate keys with Alice and Bob
4. Relay and read all messages

Solution: Authenticated Key Exchange

• ECDH + Digital Signatures (e.g., TLS)
• ECDH + MACs with pre-shared key
• ECDH + Identity-based cryptography

ECDSA is the elliptic curve variant of DSA, providing digital signatures
with much smaller key sizes than RSA for equivalent security.

What is a Digital Signature?:
A digital signature provides:
• Authentication: Verifies the signer's identity
• Integrity: Detects if the message was modified
• Non-repudiation: Signer cannot deny having signed

ECDSA Overview:
• Key generation: Private key d, Public key Q = dG
• Signing: Uses private key and message hash to create (r, s)
• Verification: Uses public key and message hash to verify (r, s)

Security:
Security is based on:
• Hardness of ECDLP (recovering d from Q = dG)
• Quality of random number k used in signing

@module tutorial/elliptic-curves/ecdsa

Key Generation:

1. Pick random d in [1, n-1]
2. Compute Q = dG
3. Private key: d
4. Public key: Q

ECDSA Signing Algorithm:

Input: Private key d, message hash e (as integer)
Output: Signature (r, s)

1. Pick random k in [1, n-1] (CRITICAL: must be unique and secret!)
2. Compute R = kG
3. Let r = x_R mod n. If r = 0, go to step 1.
4. Compute s = k^(-1) * (e + d*r) mod n. If s = 0, go to step 1.
5. Return (r, s)

ECDSA Verification Algorithm:

Input: Public key Q, message hash e, signature (r, s)
Output: VALID or INVALID

1. Verify r, s are in [1, n-1]
2. Compute w = s^(-1) mod n
3. Compute u1 = ew mod n and u2 = rw mod n
4. Compute R' = u1G + u2Q
5. If R' = O, reject
6. Let v = x_{R'} mod n
7. Accept if v = r, reject otherwise

Mathematical justification:

We have: s = k^(-1) * (e + dr) mod n
So: k = s^(-1) * (e + dr) mod n
k = es^(-1) + drs^(-1) mod n
k = ew + drw mod n
k = u1 + d*u2 mod n

Therefore:
R' = u1G + u2Q
= u1G + u2(dG)
= (u1 + du2)G
= kG
= R

So x_{R'} = x_R = r (mod n)

THE MOST IMPORTANT SECURITY RULE IN ECDSA:

The nonce k MUST be:

1. Randomly generated
2. Unique for every signature
3. Kept completely secret

If k is reused or leaked, THE PRIVATE KEY IS COMPROMISED!

Attack if k is known:
s = k^(-1) * (e + dr) mod n
sk = e + dr mod n
d = (sk - e) * r^(-1) mod n

Attack if k is reused on two messages e1, e2:
s1 = k^(-1) * (e1 + dr) mod n
s2 = k^(-1) * (e2 + dr) mod n
s1 - s2 = k^(-1) * (e1 - e2) mod n
k = (e1 - e2) * (s1 - s2)^(-1) mod n
Then recover d as above.

Real-world examples:

• PlayStation 3 hack (2010): Sony used same k for all signatures
• Bitcoin thefts: Poor random number generators leaked k

The security of elliptic curve cryptography rests on the hardness of
the Elliptic Curve Discrete Logarithm Problem (ECDLP). This tutorial
explores what makes ECDLP hard and how curves can be weak.

The ECDLP:
Given: E, P (base point), Q (target point where Q = nP for some n)
Find: n

Best generic attack: O(sqrt(n)) using Pollard's rho algorithm.
For 256-bit n, this requires 2^128 operations - infeasible.

Why Not Index Calculus?:
Unlike classical DLP in Z_p*, there is no known sub-exponential
index calculus attack on general elliptic curves. This is why ECC
can use smaller keys than RSA for equivalent security.

@module tutorial/elliptic-curves/security

ECDLP: Given P and Q = nP, find n.

This is the foundation of ECC security.

• ECDH security: Can't find ab from aP and bP
• ECDSA security: Can't find d from Q = dG

Generic attacks work on any group:

1. BRUTE FORCE: O(n)
   Try k = 1, 2, 3, ... until kP = Q

2. BABY-STEP GIANT-STEP: O(sqrt(n)) time and space

   • Baby steps: Store {iP : i = 0, 1, ..., m} where m = ceil(sqrt(n))
   • Giant steps: Check if Q - jmP matches any baby step

3. POLLARD'S RHO: O(sqrt(n)) time, O(1) space

   • Random walk in the group
   • Detect cycle using Floyd's algorithm
   • Most practical generic attack

For 256-bit curves: sqrt(2^256) = 2^128 operations
At 10^12 ops/second, this takes 10^25 years

If the group order n has small prime factors, ECDLP is easier.

Pohlig-Hellman:

1. Factor n = p1^e1 * p2^e2 * ...
2. Solve DLP in each prime-power subgroup
3. Combine with CRT

Complexity: O(sum(e_i * (sqrt(p_i) + log(n))))

This is why we need LARGE PRIME ORDER subgroups!

The MOV attack transfers ECDLP to DLP in a finite field extension.

Using the Weil or Tate pairing:
e(P, Q) is an element of F_{q^k}*

If k (embedding degree) is small, we can:

1. Compute e(G, Q) and e(G, G)^n in F_{q^k}
2. Solve DLP in F_{q^k}* using index calculus

Index calculus in F_{q^k}* has sub-exponential complexity!

For security:

• k must be large enough that q^k is too big for index calculus
• Standard curves have astronomical k (safe)
• Pairing-friendly curves have moderate k by design

Supersingular curves have special properties:

• Trace t = 0 (mod p)
• Embedding degree k divides 6 (SMALL!)
• Endomorphism ring is non-commutative (quaternion algebra)

For cryptographic ECDLP, avoid supersingular curves!
(But they're useful for isogeny-based crypto like SIDH/SIKE)

An ANOMALOUS curve has #E(F_p) = p.

Smart's attack (1999) solves ECDLP on anomalous curves in polynomial time!

The attack:

1. Lift curve and points to Q_p (p-adic numbers)
2. Use the p-adic logarithm
3. Reduces to linear algebra

NEVER use anomalous curves for cryptography!

If implementations don't validate points, attackers can:

1. Send points NOT on the curve
2. These points might be on a different curve with weak properties
3. Recover private key through multiple queries

Mitigation:

• Always verify received points are on the correct curve
• Check x^3 + ax + b is a quadratic residue
• Check point is in the correct subgroup

Even with secure curves, implementations can leak information:

1. TIMING ATTACKS

   • Branching on secret data reveals information
   • Mitigation: Constant-time implementations

2. POWER ANALYSIS

   • Power consumption reveals operations
   • Mitigation: Balanced operations, masking

3. ELECTROMAGNETIC EMANATIONS

   • Similar to power analysis
   • Mitigation: Shielding, masking

4. CACHE ATTACKS

   • Memory access patterns reveal secrets
   • Mitigation: Constant-time table lookups

Bilinear maps are one of the most powerful tools in modern cryptography.
They enable constructions that were previously thought impossible, including:
• Identity-Based Encryption (IBE)
• Short signatures (BLS)
• Tripartite key exchange
• Attribute-Based Encryption
• Zero-Knowledge Proofs (SNARKs)

What is a Bilinear Map?:
A bilinear map (or pairing) is a function e: G1 x G2 -> GT where:
• G1 and G2 are additive groups (typically points on elliptic curves)
• GT is a multiplicative group (typically in a finite field extension)

The key property is BILINEARITY:
e(aP, bQ) = e(P, Q)^(ab) for all scalars a, b

This seemingly simple property is what makes pairings so powerful.

Why Bilinearity Matters:
Without pairings, we can compute:
• aP (scalar multiplication in G1)
• bQ (scalar multiplication in G2)

But there's NO efficient way to compute:
• Given P, aP, Q, bQ -> compute abP (this would break Diffie-Hellman!)

WITH pairings, we CAN verify relationships:
• e(aP, bQ) = e(P, Q)^(ab) = e(abP, Q) = e(P, abQ)

This enables checking multiplicative relationships between discrete logs!

@module tutorial/part6-advanced/17-pairings/bilinear-maps

MATHEMATICAL DEFINITION

A bilinear map e: G1 x G2 -> GT satisfies:

1. BILINEARITY (the key property):

   • e(P1 + P2, Q) = e(P1, Q) * e(P2, Q) (linear in first argument)
   • e(P, Q1 + Q2) = e(P, Q1) * e(P, Q2) (linear in second argument)

2. NON-DEGENERACY:

   • If P generates G1 and Q generates G2, then e(P, Q) generates GT
   • Equivalently: e(P, Q) != 1 for generators P, Q

3. COMPUTABILITY:

   • e(P, Q) can be computed efficiently (polynomial time)

From bilinearity, we can derive:
e(aP, bQ) = e(P, Q)^(ab)

Proof:
e(aP, bQ) = e(P + P + ... + P, Q + Q + ... + Q) (a copies, b copies)
= e(P, Q) * e(P, Q) * ... * e(P, Q) (ab times, by bilinearity)
= e(P, Q)^(ab)

SYMMETRIC vs ASYMMETRIC PAIRINGS

Type 1 (Symmetric): G1 = G2 = G

• e: G x G -> GT
• Typically on supersingular curves
• Simpler but less efficient

Type 2: G1 != G2, but there exists an efficient map phi: G2 -> G1

• e: G1 x G2 -> GT
• Used in some protocols

Type 3 (Asymmetric): G1 != G2, no efficient map between them

• e: G1 x G2 -> GT
• Most common in modern protocols
• BLS12-381, BN254 are Type 3

The embedding degree k determines:

• GT is a subgroup of F_{q^k}*
• Security: discrete log in GT should be hard
• Efficiency: smaller k means faster pairings but lower security

BILINEARITY ENABLES NEW CRYPTOGRAPHIC PRIMITIVES

1. THREE-PARTY KEY EXCHANGE (Joux's Protocol)
   Alice: a, broadcasts aP
   Bob: b, broadcasts bP
   Carol: c, broadcasts cP

   Shared key = e(aP, bP)^c = e(aP, cP)^b = e(bP, cP)^a = e(P, P)^(abc)

   Without pairings, three-party key exchange requires two rounds.
   With pairings, it's done in ONE round!

2. BLS SIGNATURES
   Sign: sigma = sk * H(m) where H: message -> G1
   Verify: e(sigma, g) == e(H(m), pk) where pk = sk * g

   Why it works:
   e(sk * H(m), g) = e(H(m), sk * g) = e(H(m), pk)

3. IDENTITY-BASED ENCRYPTION
   Master secret: s
   User's private key: s * H(identity)
   Anyone can encrypt to "user@example.com" without pre-shared keys!

DECISIONAL DIFFIE-HELLMAN (DDH) AND PAIRINGS

DDH Problem: Given (g, g^a, g^b, Z), determine if Z = g^(ab)

In groups WITHOUT pairings:
DDH is believed to be hard (basis of ElGamal security)

In groups WITH pairings:
DDH is EASY to solve!
Check: e(g^a, g^b) ?= e(g, Z)
If Z = g^(ab): e(g, g)^(ab) = e(g, g^(ab)) = e(g, Z) CHECK
If Z != g^(ab): the check fails

This creates a "GAP GROUP":

• CDH (Computational DH) is still hard: can't COMPUTE g^(ab)
• DDH (Decisional DH) is easy: can CHECK if Z = g^(ab)

Gap groups enable:

• Signature schemes where verification is efficient
• Encryption schemes with special properties
• Zero-knowledge proofs with efficient verification

STANDARD ASSUMPTIONS IN PAIRING-BASED CRYPTOGRAPHY

1. Bilinear Diffie-Hellman (BDH):
   Given (P, aP, bP, cP), compute e(P, P)^(abc)
   This is hard if CDH is hard in G1.

2. Decisional BDH (DBDH):
   Given (P, aP, bP, cP, Z), decide if Z = e(P, P)^(abc)
   Stronger assumption (implies BDH).

3. q-Strong DH (q-SDH):
   Given (g, g^s, g^(s^2), ..., g^(s^q)), compute (c, g^(1/(s+c)))
   Used in some signature schemes and SNARKs.

4. Knowledge of Exponent (KoE):
   If you can produce (g^a, h^a), you "know" a
   Used in SNARKs (Groth16, etc.)

SECURITY LEVELS

For 128-bit security:

• G1, G2: ~256-bit groups (elliptic curve points)
• GT: ~3072-bit groups (finite field extension)

Common choices:

• BN254: 254-bit, embedding degree 12, ~100-bit security
• BLS12-381: 381-bit, embedding degree 12, ~128-bit security
• BLS12-377: 377-bit, embedding degree 12, used in SNARKs

BLS (Boneh-Lynn-Shacham) signatures are a remarkable application of pairings
that achieve properties impossible with traditional signatures:
• SHORTEST SIGNATURES: Only ~48 bytes (vs ~64 for ECDSA, ~3000 for RSA)
• AGGREGATABLE: Combine n signatures into 1 signature of same size!
• THRESHOLD-FRIENDLY: Natural support for t-of-n signing

Used in: Ethereum 2.0, Zcash, Chia, many blockchain protocols

The Key Insight:
Traditional signatures prove you know a secret key sk.
BLS uses pairings to verify this WITHOUT revealing anything about sk.

Sign: sigma = sk * H(m) (multiply hash by secret)
Verify: e(sigma, g) ?= e(H(m), pk) (check with pairing)

@module tutorial/part6-advanced/17-pairings/bls-signatures

BLS SIGNATURE SCHEME (Boneh-Lynn-Shacham 2001)

SETUP:

• Pairing e: G1 x G2 -> GT
• G1, G2: groups of prime order r
• H: {0,1}* -> G1 (hash to curve)
• g2: generator of G2

KEY GENERATION:
sk <- random in Z_r (secret key)
pk = sk * g2 in G2 (public key)

SIGNING:
sigma = sk * H(m) in G1 (signature)

VERIFICATION:
Accept iff e(sigma, g2) == e(H(m), pk)

WHY IT WORKS:
e(sigma, g2) = e(sk * H(m), g2)
= e(H(m), g2)^sk (bilinearity)
= e(H(m), sk * g2) (bilinearity again)
= e(H(m), pk) (definition of pk)

The bilinearity of the pairing is what makes the verification work!

SIGNATURE AGGREGATION

The most powerful feature of BLS: combine n signatures into ONE!

BASIC AGGREGATION (same message):
Given signatures sigma_1, ..., sigma_n on message m:
sigma_agg = sigma_1 + sigma_2 + ... + sigma_n (point addition)

Verification:
e(sigma_agg, g2) ?= e(H(m), pk_agg)
where pk_agg = pk_1 + pk_2 + ... + pk_n

PROOF:
e(sigma_agg, g2) = e(sum_i sigma_i, g2)
= e(sum_i sk_i * H(m), g2)
= e(H(m), g2)^{sum_i sk_i}
= e(H(m), sum_i sk_i * g2)
= e(H(m), pk_agg)

AGGREGATE SIGNATURE (different messages):
Given (m_1, sigma_1, pk_1), ..., (m_n, sigma_n, pk_n):
sigma_agg = sigma_1 + ... + sigma_n

Verification:
e(sigma_agg, g2) ?= prod_i e(H(m_i), pk_i)

This requires n pairing computations, but only ONE signature to transmit!

SPACE SAVINGS:

• Individual: n signatures * 48 bytes = 48n bytes
• Aggregated: 1 signature * 48 bytes = 48 bytes
• Savings: (n-1) * 48 bytes

For Ethereum 2.0 with 500,000 validators:

• Before: 500,000 * 96 bytes = 48 MB per epoch
• After: 1 * 96 bytes = 96 bytes (plus pubkey aggregation)

ROGUE KEY ATTACK

A subtle attack on naive BLS aggregation.

ATTACK SCENARIO:

1. Honest Alice publishes pk_A = sk_A * g2
2. Malicious Bob sees pk_A
3. Bob creates pk_B = sk_B * g2 - pk_A
   (Bob doesn't know the discrete log of pk_B!)

Now pk_A + pk_B = sk_B * g2, which Bob DOES know!

Bob can forge "aggregate" signatures from Alice + Bob:
sigma_forge = sk_B * H(m) (Bob's signature alone!)

Verification passes because:
e(sigma_forge, g2) = e(sk_B * H(m), g2)
= e(H(m), sk_B * g2)
= e(H(m), pk_A + pk_B) WRONG!

DEFENSES:

1. PROOF OF POSSESSION (PoP):
   Require each participant to prove knowledge of sk:

   • Publish PoP = sk * H(pk)
   • Verify PoP before accepting pk into aggregate

2. MESSAGE AUGMENTATION:
   Include pk in the hash: H(pk || m)
   Now each signature is bound to its specific pk

3. DISTINCT MESSAGES:
   If all messages are guaranteed distinct, attack fails
   (Automatic in many applications)

Ethereum 2.0 uses PoP during validator registration.

THRESHOLD BLS SIGNATURES

t-of-n threshold signatures: any t signers can create a valid signature,
but fewer than t cannot.

SETUP (using Shamir's Secret Sharing):

1. Dealer generates random polynomial f(x) of degree t-1
   with f(0) = sk (the master secret)
2. Dealer gives share sk_i = f(i) to participant i
3. Public key: pk = sk * g2 = f(0) * g2

SIGNING:

1. Each participant i computes partial signature:
   sigma_i = sk_i * H(m)

2. Collect t partial signatures

3. Combine using Lagrange interpolation:
   sigma = sum_i (lambda_i * sigma_i)

   where lambda_i are Lagrange coefficients

WHY IT WORKS:

• f(0) = sum_i (lambda_i * f(i)) (Lagrange interpolation)
• So: sigma = sum_i (lambda_i * sk_i * H(m))
  = (sum_i lambda_i * sk_i) * H(m)
  = f(0) * H(m)
  = sk * H(m)

The result is IDENTICAL to a regular BLS signature!
Verifier cannot tell if signature was threshold or not.

APPLICATIONS:

• Distributed key generation (no trusted dealer needed!)
• Secure custody (multisig wallets)
• Random beacons (DFINITY)
• Decentralized oracles

HASH TO CURVE

BLS needs H: {0,1}* -> G1, a hash function mapping to curve points.
This is surprisingly tricky to do securely!

NAIVE APPROACH (INSECURE):

1. Hash message to get x-coordinate
2. Compute y = sqrt(x^3 + ax + b)

Problems:

• Not all x values have a valid y (only ~50%)
• Must handle "try again" securely
• Timing attacks if not constant-time

MODERN APPROACH: SSWU (Simplified SWU)

Based on Shallue-van de Woestijne map.
Always produces a valid point, constant-time.

Algorithm (simplified):

1. u = hash_to_field(message)
2. Apply rational map to get (x, y)
3. Clear cofactor: P = h * (x, y) where h = |E| / r

The standard is IETF "hash_to_curve" (RFC 9380):

• Domain separation tags
• Specified for various curves
• Constant-time implementations available

For BLS12-381:

• G1: hash_to_curve to E(F_p)
• G2: hash_to_curve to E'(F_{p^2}) (twisted curve)

BLS IN PRODUCTION SYSTEMS

ETHEREUM 2.0:

• Uses BLS12-381 with signatures in G1, public keys in G2
• Aggregates ~hundreds of thousands of attestations per epoch
• PoP required during validator registration
• Signature: 96 bytes, Public key: 48 bytes

CHIA:

• Uses BLS12-381 for plot signatures
• Aggregate signatures for space proofs
• Non-interactive aggregation

DFINITY (Internet Computer):

• Threshold BLS for random beacon
• Distributed key generation among subnet nodes
• Provides unpredictable randomness

ZCASH SAPLING:

• BLS12-381 for both pairings (in SNARKs) and signatures
• Rerandomizable signatures for privacy

FILECOIN:

• BLS aggregate signatures for storage proofs
• Reduces on-chain data significantly

CONCEPTUAL BLS IMPLEMENTATION

This shows the structure of BLS signatures.
In practice, use a battle-tested library like:

• blst (fastest)
• noble-bls12-381 (TypeScript)
• arkworks (Rust)

Pairings enable cryptographic constructions that were previously thought
impossible. This tutorial explores the major applications beyond BLS signatures.

Overview of Applications:

1. Identity-Based Encryption (IBE)
2. Attribute-Based Encryption (ABE)
3. Short Signatures (beyond BLS)
4. Zero-Knowledge Proofs (SNARKs)
5. Verifiable Random Functions (VRF)
6. Key Exchange Protocols

The Unifying Theme:
Pairings let us verify relationships between discrete logs:
• Given g^a and g^b, check if some value equals g^(ab)

This simple capability enables remarkable constructions.

@module tutorial/part6-advanced/17-pairings/pairing-applications

IDENTITY-BASED ENCRYPTION (Boneh-Franklin 2001)

Traditional PKI Problem:
To send encrypted email to alice@example.com, you need:

1. Look up Alice's public key certificate
2. Verify the certificate chain
3. Check for revocation
4. Only then can you encrypt!

IBE Solution:
Alice's public key IS her identity (email address).
Anyone can encrypt to "alice@example.com" directly!

SETUP:

• Key Generation Center (KGC) with master key msk
• Public parameters (pairing groups, hash function, mpk = msk * g2)

KEY EXTRACTION:

• Alice authenticates to KGC
• KGC computes: sk_Alice = msk * H(alice@example.com)
• Alice receives her private key over secure channel

ENCRYPTION (to identity ID):

• Sender computes: Q_ID = H(ID) in G1
• Choose random r
• Ciphertext: (r*g, m XOR H2(e(Q_ID, mpk)^r))

DECRYPTION:

• Compute: e(C1, sk_ID) = e(rg, mskH(ID)) = e(g, H(ID))^(r*msk)
  = e(H(ID), mpk)^r
• Recover m by XORing with H2(...)

ADVANTAGES:

• No certificate lookup needed
• Natural key escrow (KGC can decrypt)
• Ideal for enterprise/closed systems

LIMITATIONS:

• KGC has master key (key escrow by design)
• Requires secure channel for key extraction

ATTRIBUTE-BASED ENCRYPTION

Generalization of IBE where keys and ciphertexts are associated with
attributes and policies.

KEY-POLICY ABE (KP-ABE):

• Ciphertext tagged with attributes: {doctor, cardiology, hospital-A}
• Secret key associated with policy: (doctor AND hospital-A) OR admin
• Decryption succeeds if attributes satisfy policy

CIPHERTEXT-POLICY ABE (CP-ABE):

• Ciphertext has policy: (clearance=TOP_SECRET AND department=RESEARCH)
• Secret key has attributes: {clearance=TOP_SECRET, dept=RESEARCH, ...}
• Decryption succeeds if attributes satisfy ciphertext's policy

CONSTRUCTION (simplified):

• Master key generates attribute keys
• Encryption embeds policy using Lagrange interpolation
• Decryption requires combining correct attribute keys
• Pairing enables checking attribute combinations

EXAMPLE USE CASE (Healthcare):

Policy: "(role=doctor AND dept=oncology) OR role=patient_self"

Dr. Smith's key: {role=doctor, dept=oncology, employee_id=12345}
-> Can decrypt medical records for oncology

Patient's key: {role=patient_self, patient_id=67890}
-> Can decrypt their own records

Nurse's key: {role=nurse, dept=oncology}
-> CANNOT decrypt (nurse != doctor)

ADVANCED ABE:

• Multi-authority ABE: No single trusted party
• Decentralized ABE: Collusion-resistant even across authorities
• Revocable ABE: Can revoke specific user's access

SNARKs: SUCCINCT NON-INTERACTIVE ARGUMENTS OF KNOWLEDGE

SNARKs are perhaps the most impactful application of pairings today.
They enable proving arbitrary computations with:

• Succinct proofs: ~200-300 bytes regardless of computation size
• Fast verification: milliseconds regardless of computation
• Zero-knowledge: proof reveals nothing about inputs

WHY PAIRINGS?

SNARKs work by encoding computations as polynomial equations.
The prover must show they know polynomials satisfying constraints
WITHOUT revealing the polynomials.

Pairings enable polynomial commitment schemes:

• Commit to polynomial f(x) as [f(s)]_1 for secret s
• Prove f(z) = y without revealing f
• Uses: e([f(s)]_1, [1]_2) checks

GROTH16 (most common SNARK):

• Setup: Trusted ceremony generates proving/verification keys
• Prove: ~seconds for complex computations
• Verify: ~milliseconds, 3 pairings
• Proof size: 192 bytes (3 G1 elements)

PLONK:

• Universal trusted setup (one ceremony for all circuits)
• More flexible constraint system
• Slightly larger proofs than Groth16

APPLICATIONS:

• Zcash: Private transactions (prove valid without revealing amounts)
• Ethereum: Rollups (prove thousands of txs in one proof)
• Filecoin: Storage proofs (prove you're storing data)
• Identity: Prove age > 18 without revealing birthday

VERIFIABLE RANDOM FUNCTIONS (VRF)

A VRF is like a keyed hash where you can PROVE the output is correct.

PROPERTIES:

• Deterministic: VRF(sk, x) always gives same output
• Unpredictable: Without sk, output looks random
• Verifiable: Can prove output is correct using pk

PAIRING-BASED VRF:

KeyGen:
sk <- random, pk = sk * g

Eval(sk, x):
h = H(x) // Hash to curve
gamma = sk * h // VRF "proof point"
output = H'(gamma) // Final random output
return (output, gamma)

Verify(pk, x, output, gamma):
h = H(x)
Check: e(gamma, g) == e(h, pk) // Pairing verification!
Check: output == H'(gamma)

WHY IT WORKS:
e(sk * h, g) = e(h, g)^sk = e(h, sk * g) = e(h, pk)

The pairing proves gamma = sk * H(x) without revealing sk!

APPLICATIONS:

• Blockchain leader election (Cardano, Algorand)
• Random beacons (unbiasable randomness)
• Lottery systems (prove fairness)
• Private information retrieval

TRIPARTITE KEY EXCHANGE (Joux 2000)

Classical DH requires two rounds for 3 parties.
Pairings enable ONE-ROUND tripartite key exchange!

PROTOCOL:

• Alice, Bob, Carol each pick secrets a, b, c
• Alice broadcasts aP
• Bob broadcasts bP
• Carol broadcasts cP

Shared key computation:

• Alice: K = e(bP, cP)^a
• Bob: K = e(aP, cP)^b
• Carol: K = e(aP, bP)^c

All compute the same K = e(P, P)^{abc}!

PROOF (bilinearity):
e(bP, cP)^a = e(P, P)^{bc * a} = e(P, P)^{abc}

SECURITY:

• Based on Bilinear Diffie-Hellman (BDH) assumption
• Passive adversary cannot compute e(P, P)^{abc}
  from (P, aP, bP, cP)

Note: This basic protocol lacks authentication.
Practical protocols add signatures or MACs.

IDENTITY-BASED KEY EXCHANGE:
Combine IBE with key exchange for certificate-free authenticated
key exchange. Users derive keys from identities!

MORE PAIRING APPLICATIONS

SHORT SIGNATURES (Waters, etc.):

• Even shorter than BLS in some settings
• Structure-preserving signatures
• Useful for anonymous credentials

GROUP SIGNATURES:

• User signs on behalf of group
• Verifier knows "someone in group signed"
• Group manager can open to reveal signer
• Privacy + accountability

BLIND SIGNATURES:

• Signer signs without seeing message
• Used for anonymous voting, e-cash
• Pairing-based schemes very efficient

FUNCTIONAL ENCRYPTION:

• Decrypt only f(m) from encrypted m
• Example: Compute on encrypted data
• Inner-product functional encryption from pairings

PROXY RE-ENCRYPTION:

• Transform ciphertext from pk_A to pk_B
• Without decrypting or learning message
• Useful for secure data sharing

BROADCAST ENCRYPTION:

• Encrypt to subset of users efficiently
• Revoke users without re-keying others
• Pairing-based schemes achieve optimal parameters

WHEN TO USE PAIRING-BASED CRYPTOGRAPHY

GOOD USE CASES:

1. Signature Aggregation:

   • Many signers, limited bandwidth
   • Example: Blockchain consensus, IoT sensor networks

2. Identity-Based Systems:

   • Controlled environments with key authority
   • Example: Enterprise encryption, smart cards

3. Advanced Access Control:

   • Complex policies, attribute-based
   • Example: Healthcare records, classified documents

4. Zero-Knowledge Proofs:

   • Proving computations without revealing inputs
   • Example: Privacy coins, scaling solutions

5. Threshold Cryptography:

   • Distributed trust, no single point of failure
   • Example: Key custody, random beacons

LESS SUITABLE:

1. Simple Encryption:

   • ECIES or hybrid encryption is simpler

2. Resource-Constrained Devices:

   • Pairing computation is heavy
   • Consider ECDSA for IoT

3. Post-Quantum Security:

   • Pairings are NOT quantum-resistant
   • Use lattice-based alternatives for PQ

PERFORMANCE CONSIDERATIONS:

• Pairing: ~1-2ms (BLS12-381)
• EC scalar mult: ~0.1-0.2ms
• RSA-2048: ~0.5ms sign, ~0.02ms verify
• Post-quantum (Dilithium): ~0.1ms

The Tate pairing is an alternative to the Weil pairing that is more
efficient to compute. It was introduced by John Tate in 1958 and became
important for cryptography when Miller showed how to compute it efficiently.

Key Differences from Weil Pairing:
• Requires only ONE Miller loop (vs two for Weil)
• NOT alternating: <P, Q> != <Q, P>^{-1}
• Needs "final exponentiation" for unique result
• Roughly 2x faster than Weil pairing

Mathematical Definition:
For P in E[n] and Q in E(F_q)/nE(F_q):
<P, Q>n : E[n] x E(F_q)/nE(F_q) -> F{q^k}* / (F_{q^k}*)^n

After final exponentiation:
e(P, Q) = <P, Q>^{(q^k - 1)/n} in mu_n

@module tutorial/part6-advanced/17-pairings/tate-pairing

THE TATE PAIRING: FORMAL DEFINITION

Let E be an elliptic curve over F_q, n an integer with gcd(n, q) = 1,
and k the embedding degree (smallest k with n | q^k - 1).

The Tate pairing is defined on:
<., .>_n : E(F_q^k)[n] x E(F_q^k)/nE(F_q^k) -> F_q^k* / (F_q^k*)^n

CONSTRUCTION:
For P in E[n] and Q representing a class in E/nE:

1. Choose D_Q ~ (Q) - (O) as a divisor
2. Let f_P be a function with div(f_P) = n(P) - n(O)
3. Define: <P, Q> = f_P(D_Q)

The result is only well-defined up to n-th powers.

REDUCED TATE PAIRING:
To get a unique result in mu_n, apply final exponentiation:
e(P, Q) = <P, Q>^{(q^k - 1)/n}

This is what cryptographic protocols use.

PROPERTIES OF THE TATE PAIRING

1. BILINEARITY (in both arguments):
   <P1 + P2, Q> = <P1, Q> * <P2, Q>
   <P, Q1 + Q2> = <P, Q1> * <P, Q2>

   Consequence: <aP, bQ> = <P, Q>^{ab}

2. NOT ALTERNATING (unlike Weil):
   In general: <P, Q> != <Q, P>^{-1}
   This is because P and Q live in different groups!

3. NON-DEGENERATE:
   For P != O in E[n], there exists Q with <P, Q> != 1.
   (After choosing appropriate representatives)

4. WELL-DEFINED:
   The reduced pairing is well-defined (independent of choices)
   after the final exponentiation.

COMPARISON WITH WEIL:

If both P and Q are in E[n] (and the Weil pairing is defined):
e_Weil(P, Q) = <P, Q> / <Q, P> (up to sign/power)

The Tate pairing is "half" of the Weil pairing in some sense.

FINAL EXPONENTIATION

The raw Tate pairing value is only defined up to n-th powers.
To get a unique element in mu_n, we compute:

e(P, Q) = <P, Q>^{(q^k - 1)/n}

WHY THIS WORKS:

• mu_n consists of the n-th roots of unity
• (q^k - 1)/n is the cofactor in F_{q^k}*
• Raising to this power projects onto mu_n

DECOMPOSITION FOR EFFICIENCY:

The exponent (q^k - 1)/n can be factored:
(q^k - 1)/n = (q^{k/2} - 1) * (q^{k/2} + 1) / n [for even k]

Easy part: (q^{k/2} - 1)

• Computed via Frobenius conjugation
• Very cheap (just field operations)

Hard part: (q^{k/2} + 1) / n (when n | q^{k/2} + 1)

• Requires actual exponentiation
• Can use cyclotomic structure for speedup

For BLS12-381 (k=12, q = p):
Easy part: (p^6 - 1)
Hard part: (p^6 + 1) / r, uses Frobenius maps

The final exponentiation takes about 25-30% of total pairing time.

THE ATE PAIRING

The Ate pairing is an optimized variant of the Tate pairing that uses
the Frobenius endomorphism to shorten the Miller loop.

KEY INSIGHT:
Instead of computing f_{n,P}(Q), we can compute f_{t-1,Q}(P) where
t is the trace of Frobenius. Since |t| << n, the loop is shorter!

For a curve over F_q with trace t:
|t| <= 2*sqrt(q) (Hasse bound)
n ~ q (for prime-order curves)

So the Ate loop length is ~log(t) vs ~log(n) for Tate.
This is roughly a 50% improvement!

DEFINITION:
a(Q, P) = f_{t-1,Q}(P)^c

where c is an appropriate cofactor for the final exponentiation.

TWISTED ATE PAIRING:
Uses curve twists to move one argument to a smaller group:

• G1: points on E(F_q)
• G2: points on twisted curve E'(F_{q^{k/d}})

This further optimizes both Miller loop and final exponentiation.

OPTIMAL ATE PAIRING

The optimal Ate pairing achieves the theoretical minimum loop length.

THEOREM (Vercauteren 2008):
The shortest possible Miller loop for a pairing on E/F_q has length

= log_2(n) / phi(k)
where phi is Euler's totient function and k is the embedding degree.

For k = 12: phi(12) = 4, so minimum loop is ~log(n)/4

The optimal Ate pairing achieves this bound (or close to it) using:

1. Multiple short Miller loops
2. Frobenius and twist maps
3. Careful selection of loop parameters

EXAMPLE: BLS12-381

• Parameter x = -0xd201000000010000 (64-bit)
• Miller loop has length ~64 bits (vs ~256 for full n)
• Additional structure from BLS construction

MULTI-PAIRING:
When computing products of pairings (common in SNARKs):
prod_i e(P_i, Q_i)

Can share the final exponentiation:
(prod_i <P_i, Q_i>)^{(q^k-1)/n}

This is faster than computing each pairing separately.

PAIRING COMPUTATION STRUCTURE

function optimal_ate_pairing(P in G1, Q in G2):
// 1. Miller loop (~60-70% of time)
f = miller_loop(P, Q)

// 2. Final exponentiation (~30-40% of time)
//    Split into easy and hard parts

// Easy part: f^(q^6 - 1) - uses Frobenius, very fast
f = f * conjugate(f)^(-1)

// Easy part: f^(q^2 + 1) - more Frobenius
f = f^(q^2) * f

// Hard part: f^((q^4 - q^2 + 1)/r)
//   Uses addition chain specific to curve parameters
f = hard_exponentiation(f)

return f

LINE FUNCTION COMPUTATION (in Miller loop):

function line_function(T, P, Q):
if T == P: // Doubling
lambda = (3x_T^2 + a) / (2y_T)
else: // Addition
lambda = (y_P - y_T) / (x_P - x_T)

l = y_Q - y_T - lambda * (x_Q - x_T)
v = x_Q - x_R  // vertical line at R = T + P

return l / v  // or just l for projective coordinates

SECURITY OF TATE/ATE PAIRINGS

The security of pairing-based schemes depends on:

1. ECDLP in G1 and G2:

   • Best attack: Pollard-rho, O(sqrt(n))
   • For BLS12-381: ~128-bit security

2. DLP in GT (F_{q^k}*):

   • Best attack: Number Field Sieve, subexponential
   • For BLS12-381: q^12 ~ 4569 bits, ~128-bit security

3. Pairing-specific problems (BDH, DBDH, etc.):

   • No known attacks better than generic
   • Security reduces to hardness in G1/G2/GT

KNOWN ATTACKS:

• MOV attack (1993): Reduces ECDLP to DLP in F_{q^k}*
  This is why embedding degree matters!
  Random curves: k ~ q (safe)
  Pairing-friendly curves: k small (need large q^k)

• FR attack (1994): Similar to MOV, uses Tate pairing

• Cheon attack (2006): Given (g, g^x, g^{x^d}), find x
  Applies to some protocols using polynomial evaluations
  Mitigated by parameter choices

PARAMETER SELECTION:

The Weil pairing is a bilinear map on the n-torsion points of an elliptic curve.
It was discovered by Andre Weil in the 1940s as a tool for studying the arithmetic
of elliptic curves, but has become fundamental to modern cryptography.

Mathematical Definition:
For an elliptic curve E and integer n coprime to the characteristic:
e_n: E[n] x E[n] -> mu_n

where:
• E[n] = {P in E : nP = O} is the n-torsion subgroup
• mu_n = {z : z^n = 1} is the group of nth roots of unity

Key Properties:

1. BILINEARITY: e_n(aP, bQ) = e_n(P, Q)^(ab)
2. ALTERNATING: e_n(P, P) = 1 for all P
3. NON-DEGENERATE: If e_n(P, Q) = 1 for all Q, then P = O
4. COMPATIBILITY: e_n(P, Q)^m = e_{nm}(P, Q) when defined

@module tutorial/part6-advanced/17-pairings/weil-pairing

THE WEIL PAIRING: FORMAL DEFINITION

Let E be an elliptic curve over a field K, and let n be a positive integer
coprime to char(K).

The n-torsion subgroup E[n] consists of all points P such that nP = O.
Over the algebraic closure, E[n] is isomorphic to (Z/nZ)^2.

The Weil pairing e_n: E[n] x E[n] -> mu_n is defined using divisors:

DIVISOR APPROACH:
For P, Q in E[n] with P != Q:

1. Let f_P be a function with divisor n(P) - n(O)
   (i.e., f_P has a zero of order n at P and a pole of order n at O)
2. Similarly, f_Q has divisor n(Q) - n(O)

Then: e_n(P, Q) = f_P(Q+S) / f_P(S) * f_Q(S) / f_Q(P+S)

where S is a point chosen so all evaluations are defined.

In practice, we use Miller's algorithm to compute the pairing efficiently.

PROPERTIES OF THE WEIL PAIRING

1. BILINEARITY (in both arguments):
   e_n(P1 + P2, Q) = e_n(P1, Q) * e_n(P2, Q)
   e_n(P, Q1 + Q2) = e_n(P, Q1) * e_n(P, Q2)

   Consequence: e_n(aP, bQ) = e_n(P, Q)^(ab)

2. ALTERNATING (skew-symmetric):
   e_n(P, Q) = e_n(Q, P)^(-1)
   e_n(P, P) = 1 for all P

   The alternating property distinguishes the Weil pairing from
   the Tate pairing, which is not alternating.

3. NON-DEGENERATE:
   If e_n(P, Q) = 1 for all Q in E[n], then P = O.
   Equivalently: for non-trivial P, there exists Q with e_n(P, Q) != 1.

4. GALOIS EQUIVARIANCE:
   For sigma in Gal(K-bar/K):
   sigma(e_n(P, Q)) = e_n(sigma(P), sigma(Q))

5. COMPATIBILITY:
   e_{nm}(P, Q) = e_n(mP, Q) = e_n(P, mQ) when defined
   e_n(P, Q)^m = e_{nm}(P, Q)

FINDING n-TORSION POINTS

For P to be n-torsion (nP = O), we need ord(P) | n.

If the curve order is N, then n | N ensures E[n] is non-trivial.

For E[n] to be fully defined over F_q, we need the embedding degree k
(smallest k such that n | q^k - 1) to be 1.

MILLER'S ALGORITHM

Victor Miller (1986) gave an efficient algorithm to compute pairings.

The idea: Build the function f_P with divisor n(P) - n(O) iteratively
using the double-and-add structure.

ALGORITHM (simplified):

Input: P, Q in E[n], n > 0
Output: e_n(P, Q)

1. f := 1
2. V := P
3. For each bit b_i of n (from high to low):
   a. f := f^2 * l_{V,V}(Q) / v_{2V}(Q) // doubling
   b. V := 2V
   c. If b_i = 1:
   f := f * l_{V,P}(Q) / v_{V+P}(Q) // addition
   V := V + P
4. Return f

Where:

• l_{V,V}(Q) = value of tangent line at V, evaluated at Q
• l_{V,P}(Q) = value of line through V and P, evaluated at Q
• v_{V}(Q) = value of vertical line at V, evaluated at Q

The function f accumulates the value of f_P(Q) as we compute nP.

EMBEDDING DEGREE

The embedding degree k of a curve E with respect to n is the smallest
positive integer such that n | q^k - 1.

Significance:

• E[n] is fully defined over F_{q^k}
• The Weil pairing maps to mu_n in F_{q^k}*
• k determines the security-efficiency tradeoff

For cryptography:

• Small k (e.g., k = 2, 4, 6): efficient pairings but smaller GT
• Large k (e.g., k = 12, 24): slower pairings but better security ratio

PAIRING-FRIENDLY CURVES

Most random curves have k ~ q (embedding degree roughly field size).
Pairing-friendly curves are specially constructed with small k:

• Supersingular curves: k | 6 (k = 1, 2, 3, or 6)
• BN curves: k = 12
• BLS12: k = 12
• BLS24: k = 24

Security consideration:

• DLP in E: O(sqrt(q)) with Pollard-rho
• DLP in F_{q^k}*: subexponential (index calculus)

Need q^k large enough to resist index calculus attacks.

WEIL vs TATE vs ATE PAIRINGS

WEIL PAIRING e_n:

• Symmetric: e_n(P, Q) and e_n(Q, P) both well-defined
• Alternating: e_n(P, Q) = e_n(Q, P)^{-1}
• Self-pairing trivial: e_n(P, P) = 1
• Miller loop runs twice (once for each argument)

TATE PAIRING <P, Q>_n:

• NOT alternating: <P, Q> != <Q, P>^{-1} in general
• Only one Miller loop needed
• Result needs "final exponentiation" to be well-defined
• More efficient than Weil (roughly 2x faster)

ATE PAIRING:

• Optimized version of Tate
• Shorter Miller loop (uses Frobenius structure)
• Even more efficient than Tate

OPTIMAL ATE / R-ATE / ETA PAIRINGS:

• Further optimizations using curve-specific structure
• Used in practice (BN254, BLS12-381 implementations)

In practice, cryptographic libraries use Ate or optimal Ate pairings
for efficiency, while the Weil pairing is mainly of theoretical interest.

Lattices are the foundation of post-quantum cryptography. Unlike elliptic
curve cryptography, lattice problems remain hard even for quantum computers
(as far as we know). This makes lattices crucial for the future of security.

What is a Lattice?:
A lattice is a discrete additive subgroup of R^n. Think of it as an
infinite grid of points in space, generated by integer combinations
of basis vectors.

Why Lattices Matter for Cryptography:

1. POST-QUANTUM: Resistant to Shor's algorithm
2. VERSATILE: Enables FHE, signatures, encryption, ZK proofs
3. EFFICIENT: Often faster than elliptic curves
4. STANDARDIZED: NIST PQC standards use lattices (Kyber, Dilithium)

@module tutorial/part6-advanced/18-lattices-intro/lattice-basics

DEFINITION

A lattice L is a discrete subgroup of R^n that is generated by
integer linear combinations of a finite set of basis vectors.

Given basis vectors b_1, b_2, ..., b_d in R^n:
L = {a_1b_1 + a_2b_2 + ... + a_d*b_d : a_i in Z}

The vectors b_i form a BASIS for L.
The number d is the RANK of the lattice.
The lattice lives in R^n where n is the DIMENSION.

FULL-RANK: When d = n (most common in crypto)

EXAMPLE: The simplest lattice Z^2
Basis: b_1 = (1, 0), b_2 = (0, 1)
Lattice points: all (a, b) with integer a, b

EXAMPLE: A skewed lattice
Basis: b_1 = (1, 0), b_2 = (0.5, 0.866)
Still has "grid" structure but rotated/skewed

BASIS NON-UNIQUENESS

A lattice has INFINITELY many bases!

Any unimodular transformation (matrix with det = +/- 1)
gives a new valid basis for the same lattice.

Example: Z^2 has many bases:
Standard: {(1,0), (0,1)}
Rotated: {(1,1), (1,-1)} (same lattice!)
Skewed: {(1,0), (1,1)} (same lattice!)

KEY INSIGHT: Some bases are "better" than others:

• Short vectors are useful (LLL reduction finds them)
• Nearly orthogonal is useful (easier to solve problems)

DETERMINANT (Volume)

The determinant of a lattice is invariant under basis change:
det(L) = |det(B)| for any basis matrix B

Geometric interpretation:
det(L) = volume of the fundamental parallelepiped
= "density" of lattice points

For a full-rank lattice in R^n:
det(L) = sqrt(det(B * B^T))

Smaller det(L) means denser lattice (more points per unit volume).

GRAM-SCHMIDT ORTHOGONALIZATION

Given a basis B = (b_1, ..., b_d), produce an orthogonal basis
B* = (b_1*, ..., b_d*):

b_1* = b_1
b_i* = b_i - sum_{j<i} mu_{i,j} * b_j*

where mu_{i,j} = <b_i, b_j*> / <b_j*, b_j*>

The mu coefficients measure "how non-orthogonal" the basis is.
For an orthogonal basis: all mu_{i,j} = 0 for i != j.

IMPORTANCE FOR CRYPTOGRAPHY:

The Gram-Schmidt vectors tell us about:

1. How "good" a basis is (orthogonal = good)
2. Lower bound on shortest vector: min_i ||b_i*||
3. Quality of LLL reduction

HADAMARD RATIO:

H(B) = (det(L) / (prod_i ||b_i||))^{1/n}

Range: 0 < H(B) <= 1
H(B) = 1 iff basis is orthogonal
Higher H(B) = better basis

SUCCESSIVE MINIMA

The i-th minimum lambda_i(L) is the smallest r such that
L contains i linearly independent vectors of length <= r.

lambda_1(L): length of shortest nonzero vector
lambda_2(L): length such that we have 2 independent short vectors
...

MINKOWSKI'S BOUND:

For a full-rank lattice in R^n:
lambda_1(L) <= sqrt(n) * det(L)^{1/n}

This gives an UPPER BOUND on the shortest vector length.
In practice, the shortest vector is often much shorter.

GAUSSIAN HEURISTIC:

For a "random" lattice, we expect:
lambda_1(L) ~ sqrt(n / (2pie)) * det(L)^{1/n}

This is used to estimate lattice problem hardness.

FINDING SHORT VECTORS:

Finding the exact shortest vector (SVP) is NP-hard under
randomized reductions. But we CAN find:

• Approximately shortest: LLL finds 2^{n/2} approximation
• Better approximations: BKZ, enumeration, sieving

DUAL LATTICE

The dual lattice L* of L is:
L* = {v in R^n : <v, u> in Z for all u in L}

Properties:

• (L*)* = L (double dual is original)
• det(L*) = 1 / det(L)
• If B is a basis for L, then (B^{-1})^T is a basis for L*

For full-rank lattices:
L* = {v : <v, b_i> in Z for all basis vectors b_i}

IMPORTANCE IN CRYPTOGRAPHY:

Many lattice problems have "dual" versions:

• SIS (Short Integer Solution) uses primal
• LWE (Learning With Errors) uses dual

The dual lattice appears in:

• Regev's encryption scheme
• Lattice-based signatures
• Security reductions

HARD LATTICE PROBLEMS

These problems are believed hard even for quantum computers!

SVP (Shortest Vector Problem):
Given a lattice L, find a shortest nonzero vector.

• Exact SVP: NP-hard under randomized reductions
• gamma-SVP: Find vector within factor gamma of shortest

CVP (Closest Vector Problem):
Given a lattice L and target t, find lattice point closest to t.

• At least as hard as SVP
• gamma-CVP: Find point within factor gamma of closest

SIVP (Shortest Independent Vectors Problem):
Find n linearly independent vectors, each short.

GapSVP (Decision version):
Distinguish lattices with lambda_1 <= 1 from lambda_1 > gamma.

LWE (Learning With Errors):
Given (A, b = A*s + e), find s.

• As hard as worst-case lattice problems
• Foundation of most lattice crypto

SIS (Short Integer Solution):
Given random A, find short s with A*s = 0.

• Used in hash functions and signatures

Lattice-based cryptography is the leading approach to post-quantum security.
NIST has standardized lattice-based schemes for encryption (Kyber) and
signatures (Dilithium), which will replace RSA and ECC in coming years.

Why Lattices for Post-Quantum?:

1. NO KNOWN QUANTUM ATTACKS: Unlike factoring/DLP, no quantum speedup
2. EFFICIENT: Often faster than RSA, competitive with ECC
3. VERSATILE: Enables FHE, IBE, ABE, ZK proofs
4. WELL-STUDIED: Decades of cryptanalysis, strong reductions

This tutorial covers the key concepts: LWE, Ring-LWE, and the schemes
built from them.

@module tutorial/part6-advanced/18-lattices-intro/lattice-crypto

LEARNING WITH ERRORS (LWE)

The LWE problem is the foundation of most lattice cryptography.

SETUP:

• Dimension n (security parameter)
• Modulus q (typically polynomial in n)
• Error distribution chi (typically Gaussian with small std dev)
• Secret vector s in Z_q^n

LWE DISTRIBUTION:
Generate samples (a, b) where:
a <- uniform random in Z_q^n
e <- error from chi
b = <a, s> + e mod q

SEARCH LWE:
Given many samples (a_i, b_i), find s

DECISION LWE:
Distinguish LWE samples from uniform random pairs

WHY IT'S HARD:

Without noise: Solving linear systems is easy (Gaussian elimination)
With noise: The error "hides" the linear relationship

SECURITY REDUCTION (Regev 2005):
If there's an efficient algorithm for LWE,
there's an efficient quantum algorithm for worst-case lattice problems
(GapSVP, SIVP with gamma = O(n/alpha))

This is a WORST-CASE TO AVERAGE-CASE reduction!
Breaking random LWE instances implies solving any lattice instance.

STRUCTURED LWE VARIANTS

Plain LWE has large keys: secret s has n independent components.
For n = 1024, keys are ~1024 * log(q) bits.

RING-LWE:
Work in polynomial ring R_q = Z_q[x] / (x^n + 1) for n = power of 2.

• Secret s is now ONE polynomial in R_q
• Sample a is also ONE polynomial
• Product a*s is polynomial multiplication (fast via NTT)
• Keys are n times smaller!

Sample: a <- R_q, e <- small polynomial, b = a*s + e in R_q

SECURITY:
Reduction to worst-case ideal lattice problems.
Slightly stronger assumption than plain LWE.

MODULE-LWE:
Interpolation between LWE and Ring-LWE.
Work with k x k matrices of ring elements.

• k = 1: Ring-LWE
• k = n: Plain LWE (roughly)

Module-LWE with k = 2, 3, or 4 gives good balance.
KYBER uses Module-LWE with k in {2, 3, 4}.

ADVANTAGES OF RING/MODULE:

• Smaller keys and ciphertexts
• Fast operations (NTT for multiplication)
• Still quantum-resistant

CONCERNS:

• Algebraic structure might help attacks
• No known concrete attacks, but less studied than plain LWE

KYBER - ML-KEM (Module-Lattice Key Encapsulation)

Kyber is the NIST-standardized post-quantum key encapsulation mechanism.
It's based on Module-LWE.

KEY GENERATION:

1. Generate random secret s (vector of small polynomials)
2. Generate random A (matrix of polynomials, from seed)
3. Compute b = A*s + e for error e
4. Public key: (A, b) [actually just seed + b]
5. Secret key: s

ENCAPSULATION (encrypt random key):

1. Sample random r (used for encryption randomness)
2. Compute u = A^T * r + e1
3. Compute v = b^T * r + e2 + encode(key)
4. Ciphertext: (u, v)

DECAPSULATION (decrypt to get key):

1. Compute v - s^T * u = (b^T - s^T * A^T) * r + noise + encode(key)
   = (s^T * A + e^T - s^T * A^T) * r + noise + encode(key)
   = e^T * r + noise + encode(key)
2. The error is small, so round to decode the key

PARAMETERS (Kyber-768):

• n = 256 (ring dimension)
• k = 3 (module rank)
• q = 3329 (modulus)
• Error distribution: binomial with eta = 2

PERFORMANCE:

• KeyGen: ~30 microseconds
• Encaps: ~40 microseconds
• Decaps: ~40 microseconds
• Public key: 1,184 bytes
• Ciphertext: 1,088 bytes

Much faster than RSA, comparable to ECC!

DILITHIUM - ML-DSA (Module-Lattice Digital Signature)

Dilithium is the NIST-standardized post-quantum signature scheme.
Based on the "Fiat-Shamir with aborts" technique.

BASED ON:
Short Integer Solution (SIS) problem:
Given random A, find short z with A*z = 0 mod q

KEY GENERATION:

1. Generate random A (from seed)
2. Sample short secrets s1, s2
3. Compute t = A*s1 + s2
4. Public key: (A, t) [seed + t]
5. Secret key: (s1, s2)

SIGNING:

1. Sample random y (masking vector)
2. Compute w = A*y
3. Compute challenge c = H(w, message)
4. Compute z = y + c*s1
5. If z is too large, REJECT and try again (abort)
6. Signature: (z, h) where h encodes some hint

VERIFICATION:

1. Compute challenge c = H(Az - ct, message)
2. Check that z is small enough

WHY ABORT?
Without rejection sampling, z would leak information about s1.
By rejecting "bad" z values, the distribution of z becomes
independent of s1.

PARAMETERS (Dilithium3):

• n = 256, k = 6, l = 5
• q = 8380417
• Signature: 3,293 bytes
• Public key: 1,952 bytes
• ~128-bit security

NTRU - OLDER LATTICE ENCRYPTION

NTRU predates LWE (published 1998) and has a different structure.
It's also being standardized as an alternative to Kyber.

RING:
Work in R = Z[x] / (x^n - 1) (note: NOT x^n + 1)
Elements are polynomials of degree < n

KEY GENERATION:

1. Sample small polynomials f, g
2. Require f invertible mod q and mod p
3. Public key h = g * f^{-1} mod q
4. Secret key: f (and derived values)

ENCRYPTION:

1. Sample small random r
2. Ciphertext c = prh + m mod q

DECRYPTION:

1. Compute a = f * c mod q
   = f * (prh + m) mod q
   = f * (prgf^{-1} + m) mod q
   = prg + fm mod q
2. Reduce a mod p to get f*m mod p
3. Multiply by f^{-1} mod p to get m

This works because prg is "small" and reduces to 0 mod p.

COMPARISON WITH KYBER:

• NTRU: older, more studied algebraic structure
• Kyber: based on (Module-)LWE, cleaner security proofs
• Both are being standardized by NIST

NTRU is also efficient and has very compact ciphertexts.

FULLY HOMOMORPHIC ENCRYPTION (FHE)

FHE allows computation on encrypted data without decryption.
The holy grail of cryptography, first achieved in 2009 using lattices!

WHAT FHE ENABLES:

• Cloud computing on private data
• Privacy-preserving machine learning
• Secure multi-party computation
• Private database queries

LWE-BASED FHE:

Encryption: ct = (a, b = <a,s> + e + m*q/2) for bit m

ADDITION: ct1 + ct2 = (a1+a2, b1+b2)
Decrypts to m1 + m2 (errors add up)

MULTIPLICATION: Much more complex!

• Requires "relinearization" to keep ciphertext size bounded
• Noise grows multiplicatively

NOISE MANAGEMENT (The Key Challenge):

• Each operation increases noise
• Eventually noise exceeds threshold and decryption fails
• BOOTSTRAPPING: Homomorphically evaluate decryption to reduce noise
• Bootstrapping enables unlimited computation (but slow!)

SCHEMES:

• BGV/BFV: Integer arithmetic, good for ML
• CKKS: Approximate arithmetic, good for floats
• TFHE: Boolean circuits, fastest bootstrapping

PERFORMANCE:

• Still 1000-10000x slower than plaintext
• Active research area
• Practical for some applications today

MIGRATION TO POST-QUANTUM CRYPTOGRAPHY

NIST PQC STANDARDS (2024):

Key Encapsulation:

• ML-KEM (Kyber): Primary standard
• Alternate candidates in evaluation

Digital Signatures:

• ML-DSA (Dilithium): Primary lattice-based
• SLH-DSA (SPHINCS+): Hash-based backup
• More signatures being evaluated

TIMELINE:
2024: Final standards published
2025-2030: Transition period
2030+: Deprecation of RSA/ECC for sensitive data

"HARVEST NOW, DECRYPT LATER" THREAT:
Adversaries may store encrypted data today,
wait for quantum computers, then decrypt.
This motivates EARLY migration for sensitive data.

HYBRID APPROACH:
Combine classical + PQC algorithms during transition:

• TLS: Use both ECDH and Kyber
• Signatures: Use both ECDSA and Dilithium
  If either breaks, the other provides security.

IMPLEMENTATION CHALLENGES:

• Larger keys and ciphertexts (network overhead)
• Different side-channel characteristics
• New implementation bugs to discover
• Hardware acceleration not yet widespread

The Lenstra-Lenstra-Lovasz (LLL) algorithm is one of the most important
algorithms in computational mathematics. Published in 1982, it efficiently
finds "short" vectors in lattices and has applications far beyond cryptography.

What LLL Does:
Given a lattice basis, LLL produces a "reduced" basis where:
• Vectors are relatively short
• Vectors are nearly orthogonal
• First vector approximates the shortest vector (within 2^{n/2})

Why LLL Matters:
• BREAKING CRYPTO: Coppersmith's attack on RSA uses LLL
• BUILDING CRYPTO: LLL is used in lattice scheme implementations
• DIOPHANTINE: Solves approximate integer relation problems
• POLYNOMIAL FACTORING: Original motivation for LLL

@module tutorial/part6-advanced/18-lattices-intro/lll-algorithm

LLL-REDUCED BASIS

A basis B = (b_1, ..., b_n) is LLL-reduced with parameter delta if:

1. SIZE REDUCTION:
   |mu_{i,j}| <= 1/2 for all i > j

   where mu_{i,j} = <b_i, b_j*> / <b_j*, b_j*>

   Meaning: each vector is "almost orthogonal" to previous GS vectors

2. LOVASZ CONDITION:
   For all i = 1, ..., n-1:
   delta * ||b_i*||^2 <= ||b_{i+1}* + mu_{i+1,i} * b_i*||^2

   Simplifies to:
   delta * ||b_i*||^2 <= ||b_{i+1}||^2 + mu_{i+1,i}^2 * ||b_i||^2

   Or:
   (delta - mu_{i+1,i}^2) * ||b_i*||^2 <= ||b_{i+1}*||^2

PARAMETER DELTA:

• Must satisfy: 1/4 < delta <= 1
• Standard choice: delta = 3/4 or delta = 0.99
• Larger delta = better basis but slower algorithm

GUARANTEE:
For an LLL-reduced basis with delta = 3/4:
||b_1|| <= 2^{(n-1)/2} * lambda_1(L)

The first vector is within 2^{n/2} of the shortest!

LLL ALGORITHM

Input: Basis B = (b_1, ..., b_n), parameter delta in (1/4, 1]
Output: LLL-reduced basis B' for the same lattice

Algorithm:

1. Compute Gram-Schmidt orthogonalization B*, mu

2. k = 2

3. While k <= n:
   a. SIZE REDUCE b_k:
   For j = k-1, k-2, ..., 1:
   If |mu_{k,j}| > 1/2:
   b_k = b_k - round(mu_{k,j}) * b_j
   Update mu values
   b. CHECK LOVASZ:
   If delta * ||b_{k-1}||^2 > ||b_k||^2 + mu_{k,k-1}^2 * ||b_{k-1}*||^2:
   SWAP b_k and b_{k-1}
   Update Gram-Schmidt
   k = max(k-1, 2)
   Else:
   k = k + 1

4. Return B

COMPLEXITY:

• Number of swaps: O(n^2 log B) where B = max ||b_i||
• Each iteration: O(n^2) arithmetic operations
• Total: O(n^5 log^3 B) bit operations

In practice, LLL is very fast - usually runs in near-linear time.

APPLICATIONS OF LLL

1. POLYNOMIAL FACTORING (original application):

   • Factor polynomials over Q in polynomial time
   • Groundbreaking when published in 1982

2. INTEGER RELATIONS:

   • Given reals x_1, ..., x_n, find integers a_i with
     a_1x_1 + ... + a_nx_n = 0
   • Used to discover identities in computer algebra

3. DIOPHANTINE APPROXIMATION:

   • Find good rational approximations
   • Solve systems of linear Diophantine equations

4. CRYPTANALYSIS:

   • Coppersmith's attack: Find small roots of polynomials mod N
   • Break weak RSA keys
   • Attack knapsack cryptosystems
   • Solve hidden number problems

5. LATTICE CRYPTOGRAPHY:

   • Basis reduction in key generation
   • Decryption in some schemes
   • Security analysis

6. SIGNAL PROCESSING:

   • MIMO detection
   • GPS signal processing

7. LEARNING THEORY:

   • Solve subset-sum problems
   • Learning parity with noise

BKZ (Block Korkine-Zolotareff) ALGORITHM

BKZ is a generalization of LLL that achieves better reduction
at the cost of more computation time.

IDEA:
Instead of just comparing adjacent pairs (b_i, b_{i+1}),
BKZ considers blocks of size beta and finds the shortest
vector within each block using enumeration.

PARAMETERS:

• Block size beta: larger = better reduction, slower
• BKZ-2 = LLL (special case)
• BKZ-n = HKZ (Hermite-Korkine-Zolotareff, optimal but slow)

APPROXIMATION:
BKZ-beta achieves approximation factor roughly:
gamma = (beta)^{n/(2*beta)}

For beta = 2: gamma = 2^{n/2} (same as LLL)
For beta = n: gamma = 1 (exact shortest vector)

COMPLEXITY:
Each block requires SVP in dimension beta:

• Using enumeration: 2^{O(beta^2)} per block
• Using sieving: 2^{O(beta)} per block

Total time: roughly 2^{O(beta)} * poly(n)

BKZ-2.0 (improved version):

• Uses pruned enumeration
• Incorporates preprocessing
• Faster in practice

LLL VARIANTS AND IMPROVEMENTS

DEEP LLL (L^3 algorithm):

• Check Lovasz condition with all previous vectors, not just adjacent
• Better output quality
• Still polynomial time

FLOATING-POINT LLL:

• Use floating-point arithmetic for speed
• Carefully track precision to ensure correctness
• Much faster in practice

PROGRESSIVE BKZ:

• Start with small beta, increase gradually
• Often finds good vectors faster than fixed beta

SLIDE REDUCTION:

• Variant that gives comparable results to BKZ
• Different block structure

LLL FOR SPECIFIC LATTICES:

• Ideal lattices: Use ring structure for speedup
• q-ary lattices: Exploit modular structure

IMPLEMENTATIONS:

• fpLLL: Reference implementation, very fast
• NTL: Number Theory Library, good for large integers
• FLINT: Fast Library for Number Theory
• Our sagemath-ts: Educational implementation

COPPERSMITH'S METHOD (simplified)

Problem: Given polynomial f(x) and modulus N,
find small x with f(x) = 0 mod N

This is useful for:

• Attacking RSA with small private exponent
• Factoring N when partial information is known
• Breaking many cryptographic schemes

IDEA:

1. Construct a lattice from f(x) and its shifts
2. Apply LLL to find short vectors
3. Short vectors correspond to polynomials with small roots

EXAMPLE CONSTRUCTION:
For f(x) = x^2 + ax + b mod N and bound X:

Consider polynomials: f(x), xf(x), N, Nx
Write as vectors of coefficients scaled by powers of X

      x^0    x^1    x^2    x^3

f(x): [ b, aX, X^2, 0 ]
xf(x): [ 0, bX, aX^2, X^3 ]
N: [ N, 0, 0, 0 ]
Nx: [ 0, NX, 0, 0 ]

LLL finds a short vector, corresponding to a polynomial g(x)
with g(x_0) = 0 over the integers (not just mod N!)

Then solve g(x) = 0 to find the small root x_0.

The Shortest Vector Problem (SVP) and Closest Vector Problem (CVP) are
the foundational hard problems in lattice cryptography. Understanding
these problems is essential for understanding why lattice crypto works.

Why These Problems Matter:

1. SECURITY FOUNDATION: Lattice crypto assumes these are hard
2. QUANTUM RESISTANCE: No known quantum speedup for SVP/CVP
3. PRACTICAL ATTACKS: Solving SVP/CVP breaks lattice schemes

@module tutorial/part6-advanced/18-lattices-intro/svp-cvp

SHORTEST VECTOR PROBLEM (SVP)

EXACT SVP:
Given: A lattice L (specified by basis B)
Find: A shortest nonzero vector v in L

That is, find v in L with ||v|| = lambda_1(L)

APPROXIMATE SVP (gamma-SVP):
Given: A lattice L
Find: A nonzero vector v in L with ||v|| <= gamma * lambda_1(L)

gamma = 1: exact SVP
gamma > 1: allows approximation factor gamma

HARDNESS:

Exact SVP:

• NP-hard under randomized reductions (Ajtai 1998)
• Best known algorithms: 2^O(n) time

gamma-SVP:

• gamma = poly(n): NP-hard (assuming NP != coNP)
• gamma = 2^sqrt(n): can be solved in poly time (LLL-based)
• gamma = 2^n/log(n): best quantum algorithms

The hardness of gamma-SVP for "medium" gamma (like 2^sqrt(n))
is the security assumption for most lattice crypto.

ALGORITHMS:

1. Enumeration: Deterministic 2^{O(n^2)} time, poly space
2. Sieving: Randomized 2^{O(n)} time AND space
3. LLL: Polynomial time but only gamma = 2^{n/2} approximation
4. BKZ: Trade-off between time and approximation factor

CLOSEST VECTOR PROBLEM (CVP)

EXACT CVP:
Given: A lattice L and a target vector t in R^n
Find: A lattice point v in L closest to t

That is, find v in L minimizing ||t - v||

APPROXIMATE CVP (gamma-CVP):
Given: A lattice L and target t
Find: v in L with ||t - v|| <= gamma * dist(t, L)

where dist(t, L) = min_{u in L} ||t - u||

RELATION TO SVP:

• CVP is at least as hard as SVP
• Can reduce SVP to CVP (but not other direction in general)
• Both are NP-hard under randomized reductions

ALGORITHMS:

1. Babai's Nearest Plane:

   • Use Gram-Schmidt, round to nearest lattice point
   • Polynomial time
   • Approximation: 2^{n/2} factor

2. Babai's Rounding:

   • Simpler version, slightly worse approximation
   • Also called "round-off" algorithm

3. Enumeration:

   • Exact solution
   • Exponential time: 2^{O(n)}

4. Embedding technique:

   • Reduce CVP to SVP in dimension n+1
   • Not always practical but theoretically nice

BABAI'S NEAREST PLANE ALGORITHM

Given: LLL-reduced basis B = (b_1, ..., b_n), target t
Output: Lattice point close to t

Algorithm:

1. Compute Gram-Schmidt basis B* = (b_1*, ..., b_n*)
2. Set b = t
3. For i = n, n-1, ..., 1:
   a. c_i = round(<b, b_i*> / ||b_i*||^2)
   b. b = b - c_i * b_i
4. Return t - b = sum_i c_i * b_i

Why it works:

• Projects t onto each orthogonal direction
• Rounds to nearest integer in each direction
• LLL reduction ensures basis is "nice" enough

APPROXIMATION GUARANTEE:

For an LLL-reduced basis with parameter delta:
||Babai(t) - v_closest|| <= ||t - v_closest|| * (2/sqrt(4*delta - 1))^n

With standard delta = 3/4:
Approximation factor: 2^{n/2}

Better approximation requires better basis reduction (BKZ).

COMPLEXITY OF SVP AND CVP

EXACT PROBLEMS:

Exact SVP:

• NP-hard under randomized reductions [Ajtai 1998]
• In NP intersect coNP (so unlikely to be NP-complete)
• Best deterministic: 2^{2n + o(n)} time [AKS]
• Best randomized: 2^{n + o(n)} time and space [ADRS, Laarhoven]

Exact CVP:

• NP-hard [GMSS]
• At least as hard as SVP
• Similar algorithmic complexity

APPROXIMATE PROBLEMS:

gamma-SVP for gamma = 2^{n^eps}:

• Can be solved in poly time (LLL for eps = 0.5)

gamma-SVP for gamma = poly(n):

• NP-hard assuming NP != coNP [Khot 2005]

gamma-SVP for gamma = O(sqrt(n)):

• Believed hard (basis of cryptography)
• Not known to be NP-hard!

QUANTUM COMPLEXITY:

No known quantum speedup for SVP or CVP!

• Shor's algorithm doesn't help
• Grover gives at most sqrt speedup on search
• Best quantum: still 2^{O(n)} for exact

This is why lattice crypto is post-quantum secure.

ALGORITHM COMPARISON

ENUMERATION (Schnorr-Euchner 1994):

• Deterministic
• Time: 2^{O(n^2)} (or 2^{O(n log n)} with preprocessing)
• Space: Polynomial
• Finds exact shortest vector
• Practical for n ~ 60-80

SIEVING (AKS 2001, Laarhoven 2015):

• Randomized
• Time: 2^{O(n)}
• Space: 2^{O(n)} (main drawback!)
• Finds exact shortest vector
• Practical for n ~ 70-90 with huge memory

LLL (Lenstra-Lenstra-Lovasz 1982):

• Polynomial time: O(n^5 log^3 B) for B-bit entries
• Finds 2^{n/2} approximation
• Practical for any n
• The workhorse of lattice algorithms

BKZ (Block Korkine-Zolotareff):

• Combines LLL and enumeration
• Parameter: block size beta
• Time: 2^{O(beta)}
• Approximation: roughly beta^{n/beta}
• Trade-off between time and quality

ALGORITHM SELECTION:

For crypto attacks:

• Low dimension (n < 60): Enumeration
• Medium dimension (60 < n < 90): Sieving (if memory available)
• High dimension (n > 90): BKZ with increasing block size

For crypto construction:

• Always use LLL for efficiency
• Security parameter chosen so BKZ attacks infeasible

SECURITY OF LATTICE CRYPTOGRAPHY

The security of lattice schemes depends on the hardness of
gamma-SVP (and related problems) for specific gamma.

TYPICAL REDUCTION:

Breaking Kyber/Dilithium =>
Solving LWE with specific parameters =>
Solving gamma-SVP with gamma ~ sqrt(n)

CONCRETE SECURITY:

Security level is measured by the "bit security" - the log of
the number of operations needed to break the scheme.

Current estimates for SVP in dimension n:

• Classical: ~0.29n bits (sieving lower bound)
• Quantum: ~0.26n bits (estimated)

NIST parameter choices:

Kyber-512: n768, ~128-bit security (classical)
Kyber-768: n1024, 192-bit security
Kyber-1024: n1280, ~256-bit security

ATTACKS IN PRACTICE:

Current records (as of 2024):

• Exact SVP solved up to n ~ 155
• approx-SVP attacks limited by memory

Cryptographic parameters are chosen with n ~ 500-1000,
providing large security margins.

OPEN QUESTIONS:

• Exact complexity of SVP (are current algorithms optimal?)
• Quantum algorithms for lattice problems
• Structured lattice problems (Ring-LWE, Module-LWE)

The SumCheck protocol is one of the most fundamental building blocks in
modern zero-knowledge proof systems. It allows a prover to convince a
verifier about the sum of a multivariate polynomial over a boolean hypercube.

Why SumCheck Matters:
SumCheck is the backbone of:
• HyperPlonk (this tutorial series)
• GKR protocol
• Spartan
• Lasso/Jolt
• Many lookup arguments

The Problem Statement:
Given a multivariate polynomial f(x_1, x_2, ..., x_n) over a field F,
the prover wants to convince the verifier of the claimed sum:

H = sum_{(b_1,...,b_n) in {0,1}^n} f(b_1, b_2, ..., b_n)

This sum has 2^n terms, which is exponential in n!

The Key Insight:
The verifier CANNOT check all 2^n evaluations (that would be expensive).
Instead, SumCheck reduces the claim to a SINGLE random evaluation point.

After n rounds, the verifier only needs to evaluate f at ONE point:
f(r_1, r_2, ..., r_n)

This reduction is what makes SumCheck so powerful.

@module tutorial/part7-hyperplonk/19-sumcheck/sumcheck-intro

THE BOOLEAN HYPERCUBE

B_n = {0, 1}^n is the set of all n-bit binary strings.

For n = 2: B_2 = {(0,0), (0,1), (1,0), (1,1)} - 4 points
For n = 3: B_3 = {(0,0,0), (0,0,1), ..., (1,1,1)} - 8 points

|B_n| = 2^n (exponential in n)

The boolean hypercube is fundamental because:

1. It represents all possible variable assignments
2. Multilinear polynomials are uniquely determined by values on B_n
3. Circuit satisfiability can be encoded as sums over B_n

MULTILINEAR POLYNOMIALS

A polynomial f(x_1, ..., x_n) is MULTILINEAR if each variable
appears with degree at most 1 in every term.

Examples:
f(x, y) = 3xy + 2x + y + 5 -- multilinear
g(x, y) = x^2 + y -- NOT multilinear (x has degree 2)
h(x, y, z) = xyz + x + z -- multilinear

UNIQUE EXTENSION PROPERTY:

Given ANY function f: B_n -> F (values on the boolean hypercube),
there is a UNIQUE multilinear polynomial that agrees with f on B_n.

This is because:

• A multilinear polynomial in n variables has at most 2^n terms
• We have exactly 2^n constraints (one for each point in B_n)
• The system is uniquely determined

This unique polynomial is called the MULTILINEAR EXTENSION (MLE).

THE SUMCHECK CLAIM

Prover claims: H = sum_{b in B_n} f(b)

Naive verification: Check all 2^n evaluations and add them up.

• Time: O(2^n * cost to evaluate f)
• Completely impractical for large n!

EXAMPLE:
For n = 100 variables, the hypercube has 2^100 points.
Even at 10^15 evaluations per second, this would take
more than 10^14 years.

THE SUMCHECK SOLUTION:
Reduce verification to:

• n rounds of interaction
• O(n) total verifier work (excluding final evaluation)
• ONE evaluation of f at a random point

The verifier's work is LINEAR in n, not exponential!

SUMCHECK PROTOCOL INTUITION

The key idea is to "peel off" one variable at a time.

Original claim: H = sum_{x1 in {0,1}} sum_{x2 in {0,1}} ... f(x1, x2, ...)

ROUND 1:
Define g_1(X_1) = sum_{x2,...,xn in {0,1}} f(X_1, x2, ..., xn)

Note: g_1(X_1) is a polynomial in one variable X_1.
Its degree in X_1 equals f's degree in x_1.

Crucially: H = g_1(0) + g_1(1)

The prover sends g_1(X_1) to the verifier.
The verifier:

1. Checks that g_1(0) + g_1(1) = H (the claimed sum)
2. Picks random r_1 and sends it to prover
3. New claim: g_1(r_1) = sum_{x2,...,xn} f(r_1, x2, ..., xn)

The verifier has reduced a sum over 2^n points to a sum over 2^{n-1} points!

ROUNDS 2 through n:
Repeat: prover sends a univariate polynomial, verifier checks and sends challenge.

FINAL CHECK:
After n rounds, the claim is: g_n(r_n) = f(r_1, r_2, ..., r_n)
The verifier evaluates f at this random point (or uses an oracle).

WORKED EXAMPLE WITH f(x,y) = 2xy + 3x + 5y + 7

Claim: H = 46 (computed above)

ROUND 1:
g_1(X) = f(X, 0) + f(X, 1)
= (2X0 + 3X + 50 + 7) + (2X1 + 3X + 51 + 7)
= (3X + 7) + (2X + 3X + 5 + 7)
= (3X + 7) + (5X + 12)
= 8X + 19

Check: g_1(0) + g_1(1) = 19 + 27 = 46 = H PASS

Verifier sends random r_1 (say, r_1 = 2)

ROUND 2:
Now we need: g_2(Y) = f(r_1, Y) = f(2, Y)
= 22Y + 32 + 5Y + 7
= 4Y + 6 + 5Y + 7
= 9Y + 13

Check: g_2(0) + g_2(1) = 13 + 22 = 35 = g_1(2) = 8*2 + 19 = 35 PASS

Verifier sends random r_2 (say, r_2 = 3)

FINAL CHECK:
g_2(r_2) = g_2(3) = 93 + 13 = 40
f(r_1, r_2) = f(2, 3) = 223 + 32 + 5*3 + 7 = 12 + 6 + 15 + 7 = 40 PASS

SECURITY OF SUMCHECK

COMPLETENESS:
If the prover is honest and H is correct, the verifier always accepts.

SOUNDNESS:
If H is incorrect, the verifier rejects with high probability.

Why soundness holds:

• In each round, the prover commits to a univariate polynomial g_i
• The check g_i(0) + g_i(1) = (previous claim) constrains g_i
• The verifier's random challenge r_i "tests" g_i at a random point
• If the prover cheated (sent wrong g_i), it can only pass if
  the true polynomial and fake polynomial agree at r_i
• By Schwartz-Zippel lemma, this happens with probability <= d/|F|
  where d is the degree

SOUNDNESS ERROR:
After n rounds, total error probability <= (d_1 + d_2 + ... + d_n) / |F|

For multilinear polynomials: each d_i = 1
So error <= n / |F|

For |F| >> n, this is negligible!

THE POWER OF SUMCHECK

1. REDUCES EXPONENTIAL TO LINEAR
   Verifier work: O(n) rounds instead of O(2^n) evaluations

2. COMPOSABILITY
   Can be combined with other protocols (polynomial commitments, IOP)

3. MULTILINEAR FRIENDLY
   Perfect for constraint systems expressed as multilinear polynomials

4. LINEAR-TIME PROVER (for structured polynomials)
   If f has special structure, prover can work in O(n * 2^n) time
   rather than O(n^2 * 2^n)

5. MINIMAL INTERACTION
   n rounds, each with one polynomial (few field elements) from prover
   and one random challenge from verifier

APPLICATIONS IN ZK PROOFS:

• Spartan: constraint satisfaction via SumCheck
• HyperPlonk: gate constraints + wiring via SumCheck
• Lasso/Jolt: lookup arguments via SumCheck
• GKR: layered circuit computation via SumCheck

ZEROCHECK: A SUMCHECK VARIANT

ZeroCheck asks: Does f(b) = 0 for all b in B_n?

This can be reduced to SumCheck!

Key idea: f(b) = 0 for all b in B_n
<=> sum_{b in B_n} eq(x, b) * f(b) = 0 for random x

where eq(x, b) is the multilinear extension of the "equality" function.

HyperPlonk uses ZeroCheck to verify:

• Gate constraints (all gates satisfied)
• Wiring constraints (all connections correct)

Next: sumcheck-protocol.ts - The full protocol implementation

The basic SumCheck protocol assumes multilinear polynomials (degree 1 per variable).
However, many applications require higher-degree polynomials:
• Gate constraints: f(x) * g(x) has degree 2
• Custom gates: can have degree 3, 4, or higher
• Lookup arguments: involve products of many terms

This file covers optimizations for high-degree SumCheck.

Key Insights:

1. For degree-d polynomial in variable i, the round polynomial g_i has degree d
2. Prover sends d+1 evaluations of g_i (enough to interpolate)
3. Verifier checks g_i(0) + g_i(1) = claimed sum

@module tutorial/part7-hyperplonk/19-sumcheck/sumcheck-optimizations

Univariate polynomial in evaluation form.
For degree d, we store d+1 evaluations at points 0, 1, 2, ..., d.

A function on the hypercube that may have higher degree.

HIGHER DEGREE POLYNOMIALS IN ZK

Many ZK constraint systems involve products:

1. MULTIPLICATION GATES:
   For a circuit with multiplication, we have constraints like:
   a(x) * b(x) - c(x) = 0

   If a, b, c are multilinear, then a*b has degree 2 in each variable.

2. PLONK-STYLE GATES:
   q_L * a + q_R * b + q_O * c + q_M * a * b + q_C = 0

   The term a*b makes this degree 2.

3. CUSTOM GATES:
   Higher-degree gates can represent more complex operations:

   • Degree 3: a * b * c (triple products)
   • Degree 4: (a * b) * (c * d) (double products)

4. LOOKUP ARGUMENTS:
   Grand product arguments involve products over all rows,
   leading to very high effective degree.

IMPACT ON SUMCHECK:

• Round polynomial g_i has degree = degree of f in variable i
• Prover sends more evaluations per round
• Communication increases linearly with degree

POLYNOMIAL REPRESENTATIONS

COEFFICIENT FORM:
g(X) = c_0 + c_1 * X + c_2 * X^2 + ... + c_d * X^d

• Good for: polynomial operations (add, multiply)
• Cost: O(d) to evaluate at a point

EVALUATION FORM:
g specified by values at d+1 points: g(0), g(1), ..., g(d)

• Good for: SumCheck (we need g(0) and g(1))
• Cost: O(d^2) to convert to coefficients (Lagrange interpolation)

IN SUMCHECK:

• Prover computes g_i at points 0, 1, 2, ..., d
• Sends these d+1 evaluations
• Verifier checks g_i(0) + g_i(1) = current claim
• Verifier evaluates g_i(r_i) via Lagrange interpolation

OPTIMIZATION:
With precomputed Lagrange basis at 0, 1, ..., d:

• Verifier can evaluate g_i(r_i) in O(d) field operations

LAGRANGE INTERPOLATION

Given evaluations at points 0, 1, ..., d, recover g(r):

g(r) = sum_{i=0}^{d} g(i) * L_i(r)

where L_i(r) = prod_{j != i} (r - j) / (i - j)

For evaluation points {0, 1, ..., d}:

L_i(r) = prod_{j=0, j!=i}^{d} (r - j) / (i - j)

BARYCENTRIC FORM (more efficient):
Precompute weights w_i = 1 / prod_{j != i} (i - j)

Then: g(r) = (sum_i w_i * g(i) / (r - i)) / (sum_i w_i / (r - i))

This requires O(d) operations instead of O(d^2).

Computes Lagrange basis polynomial L_i at point r.
L_i(r) = prod_{j != i} (r - j) / (i - j)

Evaluates polynomial at r given evaluations at 0, 1, ..., d.
Uses Lagrange interpolation.

HIGH-DEGREE SUMCHECK

For f with degree d_i in variable x_i:

PROVER in round i:

1. Compute g_i(j) for j = 0, 1, ..., d_i
   g_i(j) = sum_{remaining vars in {0,1}} f(r_1, ..., r_{i-1}, j, ...)
2. Send evaluations g_i(0), g_i(1), ..., g_i(d_i)

VERIFIER in round i:

1. Check g_i(0) + g_i(1) = current claim
2. Pick random r_i
3. Compute g_i(r_i) via Lagrange interpolation
4. Update claim to g_i(r_i)

TOTAL COMMUNICATION:
sum_{i=1}^{n} (d_i + 1) field elements

For constant max degree d:
O(n * d) field elements

Generates all points in {0,1}^n.

Computes round polynomial for high-degree SumCheck.

@param f - Function with potentially high degree
@param challenges - Previous challenges
@param round - Current round (0-indexed)
@returns Evaluation polynomial (evaluations at 0, 1, ..., degree)

Example: f(x, y) = x*y + x + y + 1

This is multilinear, but consider g(x, y) = x^2 * y + x + y
which has degree 2 in x.

For demonstration, let's use a degree-2 polynomial:
h(x, y) = (x^2 + x + 1) * (y + 1)
= x^2y + x^2 + xy + x + y + 1

Degree 2 in x, degree 1 in y.

COMMUNICATION COMPLEXITY

For multilinear SumCheck:

• Each round: 2 field elements
• Total: 2n field elements

For high-degree SumCheck (max degree d):

• Each round: d+1 field elements
• Total: n(d+1) field elements

EXAMPLE COMPARISON (256-bit field, n = 20):
Multilinear: 2 * 20 * 32 bytes = 1.28 KB
Degree 3: 4 * 20 * 32 bytes = 2.56 KB
Degree 7: 8 * 20 * 32 bytes = 5.12 KB

Communication is still very efficient compared to other ZK systems!

PROVER COMPLEXITY ANALYSIS

Naive approach:

• Each round: compute g_i at d+1 points
• Each point: sum over 2^{n-i} hypercube points
• Total: O(n * d * 2^n) work

OPTIMIZATION 1: Incremental Updates
When moving from round i to round i+1:

• Partial sums can be updated incrementally
• Save factor of 2 per round
• Total: O(d * 2^n)

OPTIMIZATION 2: Bookkeeping (CTY10)

• Maintain partial evaluation tables
• Update tables after each challenge
• Total: O(d * 2^n) with small constants

OPTIMIZATION 3: Structure-Specific
For structured polynomials (sparse, tensor):

• Can achieve sub-2^n prover time
• Example: Spartan for R1CS

Optimized SumCheck prover using bookkeeping.

Key idea: Maintain tables of partial evaluations that
can be updated in O(2^{n-i}) time after round i.

@throws NotImplementedError - Production implementation not yet complete

SumCheck prover for structured polynomials.

For sparse or tensor-product polynomials, we can achieve
better than O(2^n) prover time.

@throws NotImplementedError - Structure-specific optimization not implemented

VERIFIER COMPLEXITY

Per round:

• Receive d+1 field elements
• Check g(0) + g(1) = claim: O(1)
• Compute g(r) via Lagrange: O(d^2) naive, O(d) with precomputation

Total verifier work: O(n * d)

PRECOMPUTATION:
Lagrange denominators only depend on evaluation points {0, 1, ..., d}.
Precompute: w_i = 1 / prod_{j != i} (i - j)
Then g(r) can be computed in O(d) time per round.

BARYCENTRIC INTERPOLATION:
g(r) = (sum_i w_i * g(i) / (r-i)) / (sum_i w_i / (r-i))

Precomputes barycentric weights for Lagrange interpolation.
w_i = 1 / prod_{j != i} (i - j)

Evaluates polynomial at r using barycentric interpolation.
O(d) instead of O(d^2).

This file implements the SumCheck protocol with prover and verifier roles.
We build the protocol step by step, demonstrating how each round works.

Protocol Overview:
Goal: Verify that H = sum_{b in {0,1}^n} f(b) for multilinear f.

The protocol proceeds in n rounds:
• Round i: Prover sends univariate polynomial g_i(X)
• Verifier checks g_i(0) + g_i(1) = claimed value
• Verifier sends random challenge r_i
• Proceed to round i+1 with updated claim

After n rounds, verifier checks final evaluation of f.

@module tutorial/part7-hyperplonk/19-sumcheck/sumcheck-protocol

A univariate polynomial represented by its coefficients.
coefficients[i] is the coefficient of X^i.

Transcript of a SumCheck execution for verification.

Evaluates a univariate polynomial at a point.

Creates a univariate polynomial from coefficients.

Generates all points in the boolean hypercube {0,1}^n.

THE EQUALITY POLYNOMIAL eq(x, e)

For e in {0,1}^n, eq(x, e) is the unique multilinear polynomial that:
eq(b, e) = 1 if b = e
eq(b, e) = 0 if b != e (for b in {0,1}^n)

Formula:
eq(x, e) = prod_{i=1}^{n} (x_i * e_i + (1 - x_i) * (1 - e_i))

For e_i = 0: factor is (1 - x_i)
For e_i = 1: factor is x_i

This is the "selection" polynomial - it picks out exactly one vertex
of the boolean hypercube.

Computes eq(x, e) = prod_i (x_i * e_i + (1 - x_i)(1 - e_i)).

@param x - Evaluation point (field elements)
@param e - Boolean vector (0s and 1s)
@returns The value eq(x, e)

MULTILINEAR EXTENSION (MLE)

Given a function f: {0,1}^n -> F specified by its values on the hypercube,
the multilinear extension f~: F^n -> F is:

f~(x) = sum_{e in {0,1}^n} f(e) * eq(x, e)

This is the unique multilinear polynomial that agrees with f on {0,1}^n.

Properties:

• f~(b) = f(b) for all b in {0,1}^n
• f~ is multilinear (degree 1 in each variable)
• f~ is unique with these properties

Represents a function on the boolean hypercube by its evaluations.

Evaluates the multilinear extension at a point.

f~(x) = sum_{e in {0,1}^n} f(e) * eq(x, e)

SUMCHECK PROVER ALGORITHM

For each round i (from 1 to n):

1. Fix variables x_1 = r_1, ..., x_{i-1} = r_{i-1} (from previous challenges)
2. Compute g_i(X) = sum_{(x_{i+1}, ..., x_n) in {0,1}^{n-i}} f(r_1, ..., r_{i-1}, X, x_{i+1}, ..., x_n)
3. Send g_i to verifier
4. Receive challenge r_i

Computing g_i efficiently:

• For each degree d from 0 to deg_i(f):
  • Sum f over partial hypercube with X = d-th basis evaluation

For multilinear f: g_i has degree 1, so we only need g_i(0) and g_i(1).

Computes the i-th round polynomial for the SumCheck prover.

g_i(X) = sum_{remaining vars in {0,1}} f(r_1, ..., r_{i-1}, X, x_{i+1}, ..., x_n)

@param f - The function on the hypercube
@param challenges - Previous challenges [r_1, ..., r_{i-1}]
@param round - Current round (0-indexed)
@returns Univariate polynomial g_i

The SumCheck prover: generates the full transcript.

@param f - Function on the boolean hypercube
@param claimedSum - The claimed sum to prove
@param getChallenge - Function to get random challenges (simulates verifier)
@returns The complete SumCheck transcript

SUMCHECK VERIFIER ALGORITHM

Input: Claimed sum H, transcript from prover, oracle access to f

For each round i:

1. Check g_i(0) + g_i(1) = (previous claim or H for i=1)
2. Compute new claim = g_i(r_i)

Final check:

• Verify g_n(r_n) = f(r_1, ..., r_n) using oracle

Accept iff all checks pass.

Verifies a SumCheck transcript.

@param transcript - The prover's transcript
@param oracleEval - Function to evaluate f at any point (or commitment opening)
@returns true if verification passes

Let's demonstrate what happens if the prover tries to cheat
by claiming a wrong sum.

Production SumCheck prover with optimizations.

The naive implementation above has O(2^n) cost per round.
An optimized implementation can achieve O(2^n) TOTAL using:

• Incremental updates
• Partial sum tables
• Bookkeeping optimization

@throws NotImplementedError - Full optimization not yet implemented

Batch SumCheck for multiple instances.

Proves: sum_i alpha_i * (sum_{b in B_n} f_i(b)) = H

where alpha_i are random combination coefficients.

@throws NotImplementedError - Batch optimization not yet implemented

ZeroCheck is a key building block in HyperPlonk that allows the prover
to demonstrate that a polynomial evaluates to zero at ALL points on
the boolean hypercube {0,1}^n.

The Problem:
Given a polynomial f: F^n -> F, prove that:
f(b) = 0 for all b in {0,1}^n

This is crucial for verifying circuit satisfaction:
• Gate constraints: C(x) = 0 for all wire assignments
• Lookup constraints: L(x) = 0 for all table entries

The Solution: Reduce to SumCheck:
ZeroCheck reduces to SumCheck using a clever randomization technique.
Instead of checking 2^n zeros directly, we check a random combination.

@module tutorial/part7-hyperplonk/20-zerocheck/zerocheck-intro

Generates all points in {0,1}^n.

ZEROCHECK PROBLEM STATEMENT

Given: Multilinear polynomial f: F^n -> F
Claim: f(b) = 0 for all b in {0,1}^n

DIRECT APPROACH (NAIVE):
Check f(b) for all 2^n points b in {0,1}^n.
Cost: O(2^n) evaluations - infeasible!

POLYNOMIAL IDENTITY:
If f(b) = 0 for all b in B_n, then f must be divisible by
the vanishing polynomial of B_n.

However, working with the vanishing polynomial directly
is expensive (it has 2^n roots).

THE INSIGHT:
Use randomization to compress the check into a single SumCheck.

ZEROCHECK TO SUMCHECK REDUCTION

Key observation: If f(b) = 0 for all b in B_n, then:

sum_{b in B_n} alpha^{|b|} * f(b) = 0

for ANY alpha, where |b| = b_1 + b_2 + ... + b_n (Hamming weight).

But this is just testing that the sum is zero.
We need something stronger that the verifier can check.

THE ACTUAL REDUCTION:

Let r = (r_1, ..., r_n) be verifier's random challenge.
Define:

g(x) = f(x) * eq(x, r)

where eq(x, r) = prod_i (x_i * r_i + (1 - x_i)(1 - r_i))

Claim: f(b) = 0 for all b in B_n
<=> sum_{b in B_n} g(b) = f(r) * [sum_{b in B_n} eq(b, r)]

Wait, that's not quite right either. Let's be more precise.

CORRECT REDUCTION (HyperPlonk style):

1. Verifier sends random point r = (r_1, ..., r_n)

2. Define h(x) = eq(x, r) * f(x)

3. If f(b) = 0 for all b in B_n, then h(b) = 0 for all b in B_n

4. Therefore: sum_{b in B_n} h(b) = 0

5. Run SumCheck to verify sum_{b in B_n} h(b) = 0

6. SumCheck reduces to evaluating h(s) = eq(s, r) * f(s)
   at a random point s.

7. Verifier computes eq(s, r) and needs f(s) from an oracle.

THE EQUALITY POLYNOMIAL

eq(x, r) = prod_{i=1}^{n} (x_i * r_i + (1 - x_i)(1 - r_i))

Key properties:

1. For b in {0,1}^n and any r:
   eq(b, r) = prod_i [b_i * r_i + (1-b_i)(1-r_i)]

   When b_i = 0: factor = (1 - r_i)
   When b_i = 1: factor = r_i

   So: eq(b, r) = prod_{i: b_i=1} r_i * prod_{i: b_i=0} (1-r_i)

2. sum_{b in B_n} eq(b, r) = 1 for any r
   (This is because {eq(b, r)}_b forms a partition of unity)

3. eq(b, b') = delta_{b,b'} for b, b' in {0,1}^n
   (Selection property on boolean points)

WHY eq MATTERS FOR ZEROCHECK:

When we multiply f(x) by eq(x, r), we're creating a "random combination"
of the values f(b). If all f(b) = 0, the sum is 0.
If any f(b) != 0, the random combination is nonzero with high probability.

Computes eq(x, r) = prod_i (x_i * r_i + (1 - x_i)(1 - r_i)).

SOUNDNESS ARGUMENT

Claim: If f(b*) != 0 for some b* in B_n, the verifier rejects with
high probability.

Proof sketch:

1. The verifier's random r is chosen AFTER the prover commits to f.

2. If f(b*) != 0 for some b*, then:
   sum_{b in B_n} eq(b, r) * f(b) = sum_{b in B_n} eq(b, r) * f(b)

   This is a random linear combination of the f(b) values,
   with coefficients eq(b, r) depending on r.

3. If f(b*) != 0, then the coefficient eq(b*, r) is a polynomial in r
   that is not identically zero (it equals 1 when r = b*).

4. By Schwartz-Zippel, the sum is nonzero with probability >= 1 - n/|F|.

5. If the sum is nonzero, SumCheck will catch the cheating prover.

TOTAL SOUNDNESS ERROR:
ZeroCheck soundness error <= n/|F| (from Schwartz-Zippel)

• SumCheck soundness error <= d*n/|F| (for degree d)

For multilinear f with 256-bit field: error < 2n/2^256 ~ negligible

EXAMPLE: Verify that f(x,y) = (x - x^2)(y - y^2) is zero on {0,1}^2

Note: x - x^2 = x(1-x), which is 0 when x in {0,1}
Similarly for y.
So f(b) = 0 for all b in {0,1}^2.

Let's trace through the ZeroCheck protocol.

What happens if f is NOT zero everywhere?
Let's try g(x,y) = xy + 1, which is:
g(0,0) = 1 != 0
g(0,1) = 1
g(1,0) = 1
g(1,1) = 2

DEGREE OF h(x) = eq(x, r) * f(x)

eq(x, r) is multilinear (degree 1 in each variable).

If f is multilinear, then h has degree 2 in each variable.

For SumCheck:

• Round polynomial g_i has degree 2
• Prover sends 3 field elements per round (g_i(0), g_i(1), g_i(2))

If f has degree d in each variable:

• h has degree d+1 in each variable
• Prover sends d+2 elements per round

COMPLETE ZEROCHECK PROTOCOL

Public: Polynomial f (commitment), number of variables n
Claim: f(b) = 0 for all b in {0,1}^n

PROTOCOL:

1. V -> P: Random challenge r = (r_1, ..., r_n)

2. P -> V: Run SumCheck on h(x) = eq(x, r) * f(x)
   with claimed sum = 0
   This produces:

   • n round polynomials g_1, ..., g_n
   • Verifier challenges s_1, ..., s_n
   • Claimed final value h(s)

3. V: Verify SumCheck transcript

   • Check each g_i(0) + g_i(1) = previous claim
   • Final claim should equal h(s)

4. V: Check final evaluation

   • Compute eq(s, r) (can do locally)
   • Query oracle for f(s)
   • Verify h(s) = eq(s, r) * f(s)

ACCEPT iff all checks pass.

This file implements the complete ZeroCheck protocol, building on
the SumCheck implementation from the previous tutorial.

Protocol Overview:
ZeroCheck proves that f(b) = 0 for all b in {0,1}^n by:

1. Verifier sends random r
2. Define h(x) = eq(x, r) * f(x)
3. Run SumCheck to prove sum_{b in B_n} h(b) = 0
4. Verify final evaluation h(s) = eq(s, r) * f(s)

@module tutorial/part7-hyperplonk/20-zerocheck/zerocheck-protocol

A function on the boolean hypercube.

Univariate polynomial in evaluation form.

Transcript of a ZeroCheck execution.

Generates all points in {0,1}^n in lexicographic order.

Computes eq(x, r) = prod_i (x_i * r_i + (1 - x_i)(1 - r_i)).

Evaluates multilinear extension at a point.

Lagrange interpolation from evaluations at 0, 1, ..., d.

COMPUTING h(x) = eq(x, r) * f(x)

For ZeroCheck, we need to run SumCheck on h(x) = eq(x, r) * f(x).

Properties of h:

• If f is multilinear, h has degree 2 in each variable
• h(b) = eq(b, r) * f(b) for boolean b
• If f(b) = 0 for all b, then h(b) = 0 for all b

The prover computes h values on the hypercube:
h(b) = eq(b, r) * f(b) for each b in B_n

Creates the h function h(x) = eq(x, r) * f(x).
Returns values on the boolean hypercube.

Evaluates h(x) = eq(x, r) * f(x) at any point x (not just boolean).

ROUND POLYNOMIAL FOR ZEROCHECK

In round i, we compute:
g_i(X) = sum_{remaining vars in {0,1}} h(r_1, ..., r_{i-1}, X, ...)

Since h = eq * f and both are multilinear, h has degree 2.
So g_i has degree 2, and we need g_i(0), g_i(1), g_i(2).

Computes the round polynomial for ZeroCheck.
Returns evaluations at 0, 1, 2 (since h has degree 2).

ZeroCheck prover algorithm.

@param f - Function on the boolean hypercube (should be zero everywhere)
@param r - Initial verifier challenge
@param getChallenge - Function to get random challenges
@returns Complete ZeroCheck transcript

ZeroCheck verifier algorithm.

@param transcript - The prover's transcript
@param oracleF - Oracle access to f(x)
@returns true if verification passes

Optimized ZeroCheck prover with O(n * 2^n) total work.

Uses bookkeeping to avoid recomputing sums from scratch each round.
The key insight is that h(x) = eq(x, r) * f(x) can be incrementally
updated as we fix variables.

@throws NotImplementedError - Optimization not yet implemented

Batch ZeroCheck for multiple polynomials.

Proves: f_1 = 0 AND f_2 = 0 AND ... AND f_k = 0 on B_n.

Uses random combination: g = alpha_1 * f_1 + ... + alpha_k * f_k
and proves g = 0 with a single ZeroCheck.

@throws NotImplementedError - Batch optimization not yet implemented

ZeroCheck with polynomial commitment opening.

Instead of oracle access to f, the prover provides a commitment
and opening proof for f(s).

@throws NotImplementedError - Commitment integration not yet implemented

ProductCheck is a protocol that allows the prover to demonstrate that
the product of polynomial evaluations over the boolean hypercube equals
a claimed value (typically 1).

The Problem:
Given polynomials f and g, prove that:
prod_{b in {0,1}^n} f(b) = prod_{b in {0,1}^n} g(b)

Or equivalently (when g(b) != 0):
prod_{b in {0,1}^n} f(b)/g(b) = 1