7 minute read

Post Quantum Cryptography Logo

Post Quantum Cryptography

Overview

Lattice cryptography is a branch of cryptography that bases its security on the computational hardness of problems involving lattices—geometric structures formed by the set of all integer linear combinations of basis vectors in an $ n $-dimensional space. Here’s an in-depth look at what it is and why it’s important:

What Is a Lattice?

A lattice $ \Lambda $ in $ \mathbb{R}^n $ is defined as: $ \Lambda = { b_1 z_1 + b_2 z_2 + \cdots + b_n z_n : z_i \in \mathbb{Z} } $ where $ b_1, b_2, \ldots, b_n $ are linearly independent vectors in $ \mathbb{R}^n $. The set $ {b_1, \ldots, b_n} $ is called a basis for the lattice. Lattices can be visualized as a periodic array of points in space, much like a grid that extends infinitely in all directions.

Hard Problems in Lattices

The security of lattice-based cryptographic schemes comes from the assumed hardness of certain computational problems on lattices. Two of the most prominent problems are:

  • Shortest Vector Problem (SVP): Given a lattice, the task is to find the shortest non-zero vector in the lattice. This problem is known to be NP-hard under certain conditions and is believed to be hard even for quantum computers.

  • Closest Vector Problem (CVP): Given a lattice and a target point in space, find the lattice point closest to the target. Like SVP, CVP is computationally challenging, especially in high-dimensional lattices.

Another key problem is the Learning With Errors (LWE) problem, which, informally, involves solving systems of linear equations that have been perturbed by small random errors. The hardness of LWE is widely believed to hold even against quantum adversaries, and many cryptographic schemes have been built on this assumption.

Why Lattice Cryptography?

  1. Quantum Resistance:
    One of the major motivations behind lattice cryptography is its resistance to quantum attacks. Unlike classical cryptosystems based on factoring or discrete logarithms—which can be efficiently solved by quantum algorithms such as Shor’s algorithm—lattice problems like LWE, SVP, and CVP have no known efficient quantum algorithms.

  2. Versatility:
    Lattice-based techniques are not only used for encryption but also for constructing digital signatures, identity-based encryption, and even advanced primitives like fully homomorphic encryption (FHE), which allows computation on encrypted data without decrypting it.

  3. Worst-Case to Average-Case Reductions:
    Many lattice-based cryptographic schemes come with reductions from worst-case hardness (solving the hardest instances of a problem) to average-case hardness (solving a random instance), which provides a strong theoretical guarantee of security.
    Worst-case to average-case reductions show that if you can solve a typical (average-case) instance of a lattice problem, you can also solve its hardest (worst-case) instance. This means that the security of a lattice-based cryptographic scheme—built on average-case problems—is as strong as the assumed intractability of the worst-case instances, providing a robust theoretical guarantee.

Applications

  • Encryption:
    Schemes based on LWE and its variants provide public-key encryption methods that are both efficient and secure under standard assumptions about lattice problems.

  • Digital Signatures:
    Lattice-based digital signature schemes offer a promising alternative to classical signature algorithms, with the added benefit of quantum resistance.

  • Homomorphic Encryption:
    Lattice-based FHE allows computations to be performed directly on encrypted data, which is a powerful tool for privacy-preserving computations in cloud computing and secure multiparty computation.

  • Post-Quantum Cryptography:
    Because of their quantum-resistant properties, lattice-based cryptographic schemes are among the leading candidates for standardization in the post-quantum era. Organizations like the National Institute of Standards and Technology (NIST) are actively evaluating lattice-based proposals for future cryptographic standards.

Summary

Lattice cryptography represents a robust and versatile approach to designing cryptographic systems. By relying on the hardness of lattice-related problems such as SVP, CVP, and LWE, these schemes offer strong security guarantees and are considered promising candidates in the era of quantum computing. Their flexibility in supporting various cryptographic functionalities—from encryption to fully homomorphic encryption—further underscores their significance in modern and future cryptography.

Example

Overview

Below is a simple Python example that implements a toy version of an LWE‐based encryption scheme. Note: This is a very simplified version meant for educational purposes and should not be used in any production system. Real-world implementations require carefully chosen parameters, robust error distributions (often discrete Gaussians), and extensive security analysis.

In this example, we work modulo a small integer $ q $ (the modulus), use small dimensions, and choose the error from a tiny set (e.g. ${-1, 0, 1}$). The scheme works for encrypting a single bit. The idea is as follows:

  1. Key Generation:
    • Choose a secret vector $ \mathbf{s} \in \mathbb{Z}_q^n $ uniformly at random.
    • Generate a random matrix $ \mathbf{A} \in \mathbb{Z}_q^{m \times n} $.
    • Sample a small error vector $ \mathbf{e} \in \mathbb{Z}_q^m $.
    • Compute $ \mathbf{b} = \mathbf{A}\mathbf{s} + \mathbf{e} $ (mod $ q $).
    • Public key: $(\mathbf{A}, \mathbf{b})$
      Private key: $ \mathbf{s} $
  2. Encryption (of bit $ \mu \in {0,1} $):
    • Choose a random binary vector $ \mathbf{r} \in {0,1}^m $ (or one with small Hamming weight).
    • Compute
      $ \mathbf{u} = \mathbf{r}^T \mathbf{A} \quad (\text{in } \mathbb{Z}_q^n) $
      $ v = \mathbf{r}^T \mathbf{b} + \left\lfloor \frac{q}{2} \right\rfloor \mu \quad (\text{in } \mathbb{Z}_q) $
    • The ciphertext is $(\mathbf{u}, v)$.
  3. Decryption:
    • Compute $ v’ = v - \mathbf{u} \cdot \mathbf{s} $ (mod $ q $).
    • If $ v’ $ is closer to $0$ than to $\lfloor q/2 \rfloor$ (in modulo $ q $ arithmetic), then the decrypted bit is $0$; otherwise, it is $1$.

Implementation

Below is the complete Python code:

import numpy as np

def mod_q(x, q):
    """Helper function to compute modulo q correctly for both scalars and arrays."""
    return np.remainder(x, q)

def keygen(n, m, q):
    """
    Generates a public and private key for the LWE encryption scheme.
    
    Parameters:
      n : int -- dimension of the secret vector
      m : int -- number of LWE samples (rows of A)
      q : int -- modulus
      
    Returns:
      public_key: (A, b) where A is an (m x n) matrix and b is an m-dimensional vector.
      secret_key: s, the secret n-dimensional vector.
    """
    # Secret key: a random vector in Z_q^n
    s = np.random.randint(0, q, size=n)
    
    # Public key generation:
    A = np.random.randint(0, q, size=(m, n))
    
    # Error vector: choose small errors; here, we choose uniformly from {-1, 0, 1}
    e = np.random.choice([-1, 0, 1], size=m)
    
    # Compute b = A*s + e (mod q)
    b = mod_q(np.dot(A, s) + e, q)
    
    return (A, b), s

def encrypt(public_key, mu, q):
    """
    Encrypts a single bit message mu using the public key.
    
    Parameters:
      public_key: tuple (A, b) from keygen.
      mu : int -- message bit (0 or 1)
      q : int -- modulus
      
    Returns:
      ciphertext: (u, v)
    """
    A, b = public_key
    m = A.shape[0]
    
    # Choose random binary vector r in {0,1}^m
    r = np.random.randint(0, 2, size=m)
    
    # Compute u = r^T * A (note: u is a 1 x n vector)
    u = mod_q(np.dot(r, A), q)
    
    # Compute v = r^T * b + floor(q/2)*mu mod q
    v = mod_q(np.dot(r, b) + (q // 2) * mu, q)
    
    return (u, v)

def decrypt(ciphertext, s, q):
    """
    Decrypts the ciphertext using the secret key s.
    
    Parameters:
      ciphertext: tuple (u, v) from encryption.
      s: secret key vector.
      q: modulus.
      
    Returns:
      Decrypted bit (0 or 1)
    """
    u, v = ciphertext
    
    # Compute inner product u · s (note: u is 1 x n and s is n-dimensional)
    inner = np.dot(u, s) % q
    v_prime = mod_q(v - inner, q)
    
    # Decide based on whether v_prime is closer to 0 or to q/2.
    # Here we use q/4 as a threshold for a simple decision.
    # For a robust scheme, the threshold would depend on the error distribution.
    if v_prime < q/4 or v_prime > 3*q/4:
        return 0
    else:
        return 1

def main():
    # Parameters (these are toy parameters for demonstration)
    n = 10   # dimension of the secret vector
    m = 30   # number of LWE samples (rows of A)
    q = 97   # modulus (a small prime)
    
    # Key generation
    public_key, secret_key = keygen(n, m, q)
    print("Public Key (A, b):")
    print("A =", public_key[0])
    print("b =", public_key[1])
    print("Secret Key s =", secret_key)
    
    # Encrypt a bit (0 or 1)
    message = np.random.randint(0, 2)
    print("\nOriginal message:", message)
    
    ciphertext = encrypt(public_key, message, q)
    print("Ciphertext (u, v):")
    print("u =", ciphertext[0])
    print("v =", ciphertext[1])
    
    # Decrypt the ciphertext
    decrypted_message = decrypt(ciphertext, secret_key, q)
    print("Decrypted message:", decrypted_message)
    
    if decrypted_message == message:
        print("Decryption successful!")
    else:
        print("Decryption failed.")

if __name__ == "__main__":
    main()

Explanation

  • Key Generation (keygen):
    • We randomly generate the secret $ \mathbf{s} $ and matrix $ \mathbf{A} $ in $ \mathbb{Z}_q $.
    • A small error vector $ \mathbf{e} $ is sampled from ${-1, 0, 1}$.
    • The vector $ \mathbf{b} $ is computed as $ \mathbf{A}\mathbf{s} + \mathbf{e} $ modulo $ q $.
  • Encryption (encrypt):
    • A random binary vector $ \mathbf{r} $ is chosen.
    • The vector $ \mathbf{u} = \mathbf{r}^T \mathbf{A} $ and scalar $ v = \mathbf{r}^T \mathbf{b} + \lfloor q/2 \rfloor \mu $ are computed modulo $ q $.
  • Decryption (decrypt):
    • The decryption computes $ v’ = v - \mathbf{u} \cdot \mathbf{s} $ (mod $ q $).
    • By comparing $ v’ $ with the threshold (roughly $ q/4 $ and $ 3q/4 $), the original bit is recovered.

Again, this implementation is a simplified toy model. In practice, the parameters (like $ n $, $ m $, $ q $), the error distribution, and the precise decision thresholds must be carefully chosen to ensure both correctness and security.

Credits

This post has been created with the help of OpenAI ChatGPT o3-mini.