Latice Cryptography 🔑
Lattice Cryptography
Lattice cryptography is proposed as a post-quantum robust method for public key encryption, especially focused on digital signatures and key exchange mechanisms (KEMs). Slides
Short Vector Problem and Closest Vector Problem
Latice Grids with Python
Learning with Errors (LWE) Problem
Learning with Errors (LWE) is a method defined by Regev (2005). Problem involves the difficulty of finding the values which solve: \(B = A * s + e\) where \(A\) and \(B\) are known (public key). The value of \(s\) becomes the secret values (private key) and \(e\) are random errors.
The “ring” comes from the modulus of a prime number. Why prime?
Prime numbers can only be divided with itself and one. Real world example: A prime number greater than 1024 bits
Take LWE and a prime number, 13. In this matrix, \(Z\), expression, we have a 7x4 grid of random numbers, \(A\), a secret, \(s\), and small noise, $e$.
\[Z^{7*4}_{13} * Z^{7*1}_{13} + Z^{7*1}_{13}\]This an be solved using Guassian elimination
Ring Learning with Errors (RLWE) Problem
Learning with Errors (LWE) method with additional polynomial rings over finite fields theory.
A finite field is a set of numbers with a limit/boundry/definitive size. \(F_2 = [0,1]\)
Given an example polynomial with a degree of 4, and a prime number of 13: \(Z_{13}[x]/(x^4 + 1)\)
| Operation | Polynomial | Symbol |
|---|---|---|
| \(4 + 1x + 11x^2 + 10x^3\) | \(A\) | |
| * | \(6 + 9x + 11x^2 + 11x^3\) | \(s\) |
| + | \(0 - 1x + 1x^2 + 1x^3\) | \(e\) |
| = | \(10 + 5x + 10x^2 + 7x^3\) | \(B\) |
Ring Learning with Errors for Key Exchange (RLWE-KEX)
Purpose: Create a shared encryption key with Ring LWE
Bob and Alice agree to share:
- Set of random numbers, \(A\)
- Number of bits in polynomials, \(n\)
- Prime number, \(q\)
They independently generate:
- Error values, \(e\)
- Secret values, \(s\)
Creating public keys:
- Alice: \(b_A = A * s_A + e_A\)
- Bob: \(b_B = A * s_B + e_B\)
Creating shared keys:
- Alice: \(S_A = b_B * s_A \div (x^n + 1)\)
- Bob: \(S_B = b_A * s_B \div (x^n + 1)\)
Removing the noise (reduce into binary):
In shared_A each element \(A_i\) is converted into a binary representative \(u_i\)
if shared \(A_i < \frac{q}{4}\) then \(u_i = 0\)
else if shared \(A_i < \frac{q}{2}\) then \(u_i = 1\)
else if shared \(A_i < \frac{3q}{4}\) then \(u_i = 0\)
else if shared \(A_i < q\) then \(u_i = 1\)
Resulting in a binary representation: => [1, 0, ..., 1]