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.

Public Key LWE

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

Ring LWE

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]