Lattices

Research into quantum computing has posed several questions and challenges for cryptography. The most popular public-key algorithms which the world has been relying on for decades - factorization (used in RSA), and discrete logarithm problems (used in both finite field and elliptic-curve Diffie-Hellman) can theoretically be solved in polynomial time on a quantum computer using Shor's algorithm.

Shor's algorithm shows that factoring integers would be extremely fast on an ideal, large quantum computer. "Ideal, large" are important caveats here, since as of 2022, the largest number that has been publicly factored using Shor's algorithm is 21. Still, advances in quantum technology have motivated the development of post-quantum cryptography (PQC), which is based on algorithms which even quantum computers cannot break efficiently, according to current knowledge.

Post-quantum cryptography focusses on developing asymmetric/public-key algorithms. This is because symmetric algorithms and hash functions seem to do much better in a post-quantum world. The best algorithm for attacking symmetric ciphers, Grover's algorithm, halves their security level. Therefore doubling the keysize should be enough; for instance, AES-256 should retain 128 bits of security. On the other hand, RSA keys would have to be 1 terabyte large to achieve a reasonable level of security against Shor's algorithm.

The NIST Post-Quantum Cryptography Standardization process began in 2017 to find the best asymmetric algorithms to be used in protocols like TLS in future. Good algorithms must not only resist classical and quantum attacks but should also have small public and private keys and should execute quickly. Of the proposed schemes, Lattice-based cryptography has shown the most promise in terms of balancing security and performance.

Lattices are also a powerful tool in cryptanalysis. The Lenstra–Lenstra–Lovász (LLL) lattice basis reduction algorithm has been used to break knapsack cryptosystems, RSA with particular parameters, and NTRUEncrypt. This category begins with a series of challenges that build up an intuition of how lattices work and are used in cryptanalysis.

Lattices

 Toggle
  • Vectors
    10 pts · 4514 Solves
    Before defining a lattice or talking about how lattices appear in cryptography, let's review some of the basics of linear algebra. The following challenges should be considered as revision, if this is totally new to you, you might need to do a bit of background reading. As usual, we recommend "An Introduction to Mathematical Cryptography" by Hoffstein, Pipher, Silverman, as well as this introduction to lattices and their applications.

    A vector space $V$ over a field $F$ is a set defined with two binary operators. For a vector $v \in V$, and a scalar $a \in F$, vector addition takes two vectors and produces another vector: $v + w = z,$ for $v, w, z \in V$ and scalar multiplication takes a vector and a scalar and produces a vector: $a \cdot v = w,$ for $v, w \in V, a \in F$.

    You will probably have first seen vectors in the context of a two dimensional vector space defined over the reals. We'll use this here too as an example!

    Let's consider a two dimensional vector space over the reals. A vector $v \in V$ can be considered as a pair of numbers: $v = (a,b)$ for $a,b \in R$. Vector addition works as $v + w = (a,b) + (c,d) = (a+c, b+d)$, and scalar multiplication by $c \cdot v = c \cdot (a,b) = (c \cdot a, c \cdot b)$.

    One can also define the inner product (also called the dot product), which takes two vectors and returns a scalar. Formally we think of this as $v \cdot w = a$ for $v,w \in V, a \in F$. In our two-dimensional example, the inner product works as $v \cdot w = (a,b) \cdot (c,d) = a \cdot c + b \cdot d$.

    Time for the flag! Given a three dimensional vector space defined over the reals, where $v = (2,6,3)$, $w = (1,0,0)$ and $u = (7,7,2)$, calculate $3 \cdot (2 \cdot v - w) \cdot 2 \cdot u$.

    You must be logged in to submit your flag.


  • Size and Basis
    15 pts · 4324 Solves · 13 Solutions
    We say a set of vectors $v_{1}, v_{2}, \ldots, v_{k} \in V$ are linearly independent if the only solution to the equation:

    $a_{1} \cdot v_{1} + a_{2} \cdot v_{2} + \ldots + a_{k} \cdot v_{k} = 0$

    is for $a_{1} = a_{2} = \ldots = a_{k} = 0$.

    To visualise this, think of a vector directed out of a point. Given a set of linearly independent vectors, the only way to return back to the original point is by moving along the original vector. No combination of any of the other vectors will get you there.

    A basis is a set of linearly independent vectors $v_{1}, v_{2}, \ldots, v_{n} \in V$ such that any vector $w \in V$ can be written as:

    $w = a_{1} \cdot v_{1} + a_{2} \cdot v_{2} + \ldots + a_{k} \cdot v_{n}$

    The number of elements in the basis is also the dimension of the vector space.

    We define the size of a vector, denoted $||v||$, using the inner product of the vector with itself: $||v||^{2} = v \cdot v$.

    A basis is orthogonal if for a vector basis $v_{1}, v_{2}, \ldots, v_{n} \in V$, the inner product between any two different vectors is zero: $v_{i} \cdot v_{j} = 0, i \neq j$.

    A basis is orthonormal if it is orthogonal and $||v_{i}|| = 1$, for all $i$.

    That's a lot of stuff, but we'll be needing it. Time for the flag. Given the vector $v = (4, 6, 2, 5)$, calculate its size.

    You must be logged in to submit your flag.


  • Gram Schmidt
    30 pts · 3156 Solves · 25 Solutions
    In the last challenge we saw that there is a special kind of basis called an orthogonal basis. Given a basis $v_{1}, v_{2}, \ldots, v_{n} \in V$ for a vector space, the Gram-Schmidt algorithm calculates an orthogonal basis $u_{1}, u_{2}, \ldots, u_{n} \in V$.

    In "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman, the Gram-Schmidt algorithm is given as:

    Algorithm for Gram-Schmidt

    $u_{1} = v_{1}$
    Loop $i = 2,3\ldots,n$
       Compute $\mu_{ij} = v_{i} \cdot u_{j} / ||u_{j}||^2, 1 \leq j < i$.
       Set $u_{i} = v_{i} - \mu_{ij} \cdot u_{j}$ (Sum over $j$ for $1 \leq j < i$)
    End Loop


    To test your code, let's grab the flag. Given the following basis vectors:

    $v_{1} = (4,1,3,-1), \;\; v_{2} = (2,1,-3,4), \;\; v_{3} = (1,0,-2,7), \;\; v_{4} = (6, 2, 9, -5)$.

    use the Gram-Schmidt algorithm to calculate an orthogonal basis. The flag is the float value of the second component of $u_{4}$ to 5 significant figures.

    Note that this algorithm doesn't create an orthonormal basis! It's a small change to implement this. Think about what you would have to change. If you're using someone else's algorithm and the flag is incorrect, this might be the issue. If everything seems good and you're still not having your answer accepted, check your rounding when you take 5.s.f. for the solution.

    You must be logged in to submit your flag.


  • What's a Lattice?
    40 pts · 3307 Solves · 12 Solutions
    We're now ready to start talking about lattices. Given a set of linearly independent vectors $v_{1}, v_{2}, \ldots, v_{n} \in R^m$, the lattice $L$ generated by $v_{1}, v_{2}, \ldots, v_{n}$ is the set of linearly independent vectors $v_{1}, v_{2}, \ldots, v_{n}$ with integer coefficients.

    $L = {a_{1} \cdot v_{1} + a_{2} \cdot v_{2} + \ldots + a_{k} \cdot v_{k} : a_{1}, a_{2}, \ldots, a_{n} \in \mathbb{Z}}$.

    The basis for the lattice $L$ is any set of independent vectors that generates $L$. The choice of basis is far from unique. In the image below, we show a two dimensional lattice with two different basis vectors given by $u_{1}, u_{2}$ and $v_{1}, v_{2}$.

    diagram of lattice



    Using a basis, we can reach any point within the lattice with integer multiples of the basis vectors. The basis vectors also define the fundamental domain:

    $F(v_{1},\ldots,v_{n}) = {t_{1} v_{1} + t_{2} v_{2} + \ldots + t_{n} v_{n} : 0 \leq t_{i} < 1}$.

    As a two dimensional example, the fundamental domain is the parallelogram with sides $u_{1}$ and $u_{2}$.

    We can calculate the volume of the fundamental domain from the basis vectors. As an example, let us take a two dimensional lattice with basis vectors $v = (2,5), u = (3,1)$. Create a matrix $A$ with rows corresponding to the basis vectors: $A = [[2,5],[3,1]]$. The volume of the fundamental domain is the magnitude of the determinant of A: $\text{vol}(F) = |\det(A)| = |2 \cdot 1 - 5 \cdot 3| = |-13| = 13$.

    For the flag, calculate the volume of the fundamental domain with the basis vectors $v_{1} = (6, 2, -3), v_{2} = (5, 1, 4), v_{3} = (2, 7, 1)$.

    You must be logged in to submit your flag.


  • Gaussian Reduction
    50 pts · 2892 Solves · 24 Solutions
    If you look closely enough, lattices start appearing everywhere in cryptography. Sometimes they appear through manipulation of a crypto system, breaking parameters which were not generated securely enough. The most famous example of this is Coppersmith's attack against RSA cryptography.

    Lattices can also be used to build cryptographic protocols, whose security is based on two fundamental "hard" problems:

    The Shortest Vector Problem (SVP): find the shortest non-zero vector in a lattice $L$. In other words, find the non-zero vector within $v \in L$ such that $||v||$ is minimised.

    The Closest Vector Problem (CVP): Given a vector $w \in R^m$ that is not in $L$, find the vector $v \in L$ that is the closest to $w$, i.e. find the vector $v \in L$ such that $||v - w||$ is minimised.

    The SVP is hard for a generic lattice, but for simple enough cases there are efficient algorithms to compute either a solution or an approximation for the SVP. When the dimension of the lattice is four or less, we can compute this exactly in polynomial time; for higher dimensions, we have to settle for an approximation.

    Gauss developed his algorithm to find an optimal basis for a two-dimensional lattice given an arbitrary basis. Moreover, the output $v_1$ of the algorithm is a shortest nonzero vector in $L$, and so solves the SVP.

    For higher dimensions, there's a basis lattice reduction algorithm called the LLL algorithm, named after Lenstra, Lenstra and Lovász. If you play CTFs regularly, you'll already know about it. The LLL algorithm runs in polynomial time. For now though, lets stay in two dimensions.

    Gauss's algorithm roughly works by subtracting multiples of one basis vector from the other until it's no longer possible to make them any smaller. As this works in two-dimensions, it's nice to visualise. Here's a description of the algorithm from "An Introduction to Mathematical Cryptography", Jeffrey Hoffstein, Jill Pipher, Joseph H. Silverman:

    Algorithm for Gaussian Lattice Reduction

    Loop
       (a) If $||v_2|| < ||v_1||$, swap $v_1, v_2$
       (b) Compute $m = \lfloor v_1 \cdot v_2 / v_1 \cdot v_1 \rceil$
       (c) If $m = 0$, return $v_1, v_2$
       (d) $v_2 = v_2 - m \cdot v_1$
    Continue Loop


    Note the similarity to Euclid's GCD algorithm with the "swap" and "reduction" steps, and that we have to round the float, as on a lattice we may only use integer coefficients for our basis vectors.

    For the flag, take the two vectors $v = (846835985, 9834798552), u = (87502093, 123094980)$ and by applying Gauss's algorithm, find the optimal basis. The flag is the inner product of the new basis vectors.

    You must be logged in to submit your flag.


  • Find the Lattice
    100 pts · 1769 Solves · 18 Solutions
    As we've seen, lattices contain hard problems which can form trapdoor functions for cryptosystems. We also find that in cryptanalysis, lattices can break cryptographic protocols which seem at first to be unrelated to lattices.

    This challenge uses modular arithmetic to encrypt the flag, but hidden within the protocol is a two-dimensional lattice. We highly recommend spending time with this challenge and finding how you can break it with a lattice. This is a famous example with plenty of resources available, but knowing how to spot the lattice within a system is often the key to breaking it.

    As a hint, you will be able to break this challenge using the Gaussian reduction from the previous challenge.

    Challenge files:
      - source.py
      - output.txt

    You must be logged in to submit your flag.


  • Backpack Cryptography
    120 pts · 1172 Solves · 9 Solutions
    I love this cryptosystem so much, I carry it everywhere in my backpack. To lighten the load, I make sure I don't pack anything with high densities.

    Challenge files:
      - source.py
      - output.txt


    Challenge contributed by VincBreaker

    You must be logged in to submit your flag.


Learning With Errors 1

 Toggle
  • LWE Background
    5 pts · 1116 Solves
    Before beginning this section you should have completed at least the "Lattices" section above.

    Throughout CryptoHack and especially in the RSA chapter, lattice reduction using LLL has proven to be a very powerful cryptanalysis tool. It excels at the related problems of finding short vectors in a lattice (SVP) and finding the closest vector to a point not in the lattice (CVP and BDD). LLL also finds surprising applications through Coppersmith's method.

    However, lattice reduction algorithms for the Learning With Errors problem (LWE) only work up to a certain point. By making the lattice dimension or errors large, or providing a large/obfuscated basis, basis reduction will no longer return the shortest vector in the lattice. This is the intuition that makes LWE a "hard" problem suitable for cryptography.

    What is the name of the computer scientist and mathematician who introduced the LWE problem in 2005?

    Resources:
      - The Two Faces of Lattices in Cryptology


    Challenge contributed by ireland

    You must be logged in to submit your flag.


  • LWE Intro
    10 pts · 813 Solves
    Learning With Errors (LWE) refers to the computational problem of learning a linear function $f(A)$ which takes values over a ring, given many noisy samples of the function. These samples look like the pair $(A, \langle A, S \rangle + e)$, where $S$ is the secret element which defines the linear function, $e$ is some small error term from a known distribution, and $A$ is a known element of the ring. Note that $\langle A, S \rangle$ denotes the matrix multiplication of a matrix $A$ with vector $S$.

    Cryptosystems based on LWE are quite varied, but they usually have several common features:

    • They use modular arithmetic under two different moduli: the plaintext modulus and the ciphertext modulus.
    • The secret key is an element of a vector space modulo n.
    • Messages are encrypted by adding an encoded noisy message to a large dot-product.


    The noisy message is a properly-encoded sum of the message and a small error or noise term.

    The dot-product is between the secret key and a random element of the vector space, where this random element is provided as part of the ciphertext.

    This looks like $(A, \langle A,S \rangle + \text{encoded}(m, e))$, where $A$ is an element of the vector space.

    If the secret key is known, then the dot-product can be subtracted out, leaving only the encoded message and noise. Thanks to the special way in which the message and noise are encoded, the noise can be removed from the encoding, leaving only the message behind.

    There are two common approaches to storing the message and noise in LWE systems: you can either store the message in the high-bits of the LWE sample and the noise in the low-bits, or vice-versa.

    • Some examples of LWE schemes where the message is stored in the high-bits are Regev09 and BFV.
    • An example of an LWE scheme where the message is stored in the low-bits is BGV.


    What algorithm could be used to recover the message from the linear equations in polynomial time, if there was no added error?

    Resources:
      - The Learning with Errors Problem
      - Kyber - How does it work?


    Challenge contributed by ireland

    You must be logged in to submit your flag.


  • LWE High Bits Message
    15 pts · 561 Solves · 3 Solutions
    Now we're going to jump in and decrypt a message that's hidden in the high bits of a toy LWE system.

    Parameters:

    • vector space dimension $n$
    • ciphertext modulus $q$
    • plaintext modulus $p$ (can only encrypt messages $m < p$)
    • scaling factor $\Delta = \text{round}(q / p)$


    Key-gen:

    • The secret key $S$ is a random element of the vector space $\mathbb{Z}_q^n$.


    Ciphertext format:

    • Ciphertexts consist of a pair $A, b$, where $A$ is an element of the vector space $\mathbb{Z}_q^n$, and $b$ is an element of $\mathbb{Z}_q$.


    Encryption given message $m$:

    1. Sample $A$, a random element of the vector space $\mathbb{Z}_q^n$
    2. Sample the error-term $e$, an integer in the range $[-\Delta / 2, \Delta / 2]$. (Note: often the error is sampled from a discrete Gaussian distribution, but uniform sampling is fine)
    3. Compute $b = \langle A,S \rangle + \Delta \cdot m + e$
    4. Return the pair $(A, b)$


    Decryption given ciphertext $(A, b)$:

    1. Compute $x = b - \langle A,S \rangle \mod q$ and then interpret $x$ as an integer (not modulo $q$)
    2. Compute $m = \text{round}(x / \Delta)$, where the division and rounding happens over the integers
    3. return m


    In this system, decryption works because after the mask $\langle A,S \rangle$ has been removed, the remaining equation for the noisy message $\Delta \cdot m + e$ holds over the integers, so there is no modular wraparound due to $q$. As such, removing the error term $e$ can be done by rounding integer-division. This requires the parameters to be chosen so that $\Delta \cdot m + e < q/2$ holds.

    Challenge files:
      - lwe-high-bits.sage
      - output.txt


    Challenge contributed by ireland

    You must be logged in to submit your flag.


  • LWE Low Bits Message
    20 pts · 515 Solves · 3 Solutions
    Now we're going to jump in and decrypt a message that's hidden in the low bits of a toy LWE system. The noise is stored in the high bits.

    Parameters:

    • vector space dimension $n$
    • ciphertext modulus $q$
    • plaintext modulus $p$ (can only encrypt messages $m < p$)
    • must have $q$, $p$ be coprime


    Key-gen:

    • The secret key $S$ is a random element of the vector space $\mathbb{Z}_q^n$.


    Ciphertext format:

    • Ciphertexts consist of a pair $A, b$, where $A$ is an element of the vector space $\mathbb{Z}_q^n$, and $b$ is an element of $\mathbb{Z}_q$.


    Encryption given message $m$:

    1. Sample $A$, a random element of the vector space $\mathbb{Z}_q^n$
    2. Sample the error-term $e$, an integer in the range $[-(q/p)/2, (q/p)/2]$. Note: often the error is sampled from a discrete Gaussian distribution, but uniform sampling is fine
    3. Compute $b = \langle A, S \rangle + m + p \cdot e$
    4. Return the pair $(A, b)$


    Decryption given ciphertext $(A, b)$:

    1. Compute $x = b - \langle A, S \rangle$ centered modulo $q$ and then interpret $x$ as an integer (not modulo $q$). Note: this centered modular reduction must produce a result between $(-q/2, q/2]$ as opposed to usual modular reduction producing a result between $[0, q-1]$
    2. Compute $m = x \mod p$, where the division and rounding happens over the integers
    3. return m


    In this system, decryption works because after the mask $\langle A, S \rangle$ has been removed, the remaining equation for the noisy message $m + p \cdot e$ holds over the integers, so there is no modular wraparound due to $q$. As such, removing the error term $e$ can be done by reducing modulo $p$. This requires the parameters to be chosen so that $m + p \cdot e < q/2$ holds.

    Challenge files:
      - lwe-low-bits.sage
      - output.txt


    Challenge contributed by ireland

    You must be logged in to submit your flag.


  • From Private to Public Key LWE
    25 pts · 541 Solves · 2 Solutions
    This can be turned into a public key cryptosystem by using the "additively homomorphic" property of LWE. That is, given an encryption $\langle A, b \rangle$ encrypting the number $m$, it is possible for anyone to turn this into a valid encryption of $m + m_2$ for any number $m_2$. Explicitly, this is done by computing $\langle A, b + m_2 \rangle$ for low-bit messages (high-bit noise) and $\langle A, b + \Delta \cdot m_2 \rangle$ for high-bit messages (low-bit noise).

    While this additively homomorphic property is more straightforward to see when the message is stored in low-bits, it is also present when the message is stored in high-bits.

    Similarly, adding two LWE ciphertexts produces a new valid ciphertext which encrypts the sum of the corresponding plaintexts. The owner of the private key can use this property to turn LWE into a public-key system by releasing many different "encryptions of zero" as the public key. For Alice to use this information to encrypt, she first chooses a random subset of these "encryptions of zero" and add them together. By the second additively homomorphic property, this is also a valid encryption of zero. Next, Alice creates a new encoding of her message $m$, and adds this encoded message to this new encryption of zero. By the first additively homomorphic property, this is a valid encryption of $m$. This procedure requires the distribution from which the noise samples are drawn to be carefully chosen so that the final error term is (with high probability) below the threshold needed to decrypt.

    In order for this to be secure, it must be hard for an adversary to determine which public key samples were summed to produce the LWE ciphertext. To ensure this, the number of "encryptions of zero" in the public key must be significantly larger than the LWE dimension. As such, the size of the public key scales as $O(n^2 \log(q))$ bits, making LWE cryptosystems have large public keys.

    What is the size of a Kyber1024 public key in bytes?

    Challenge contributed by ireland

    You must be logged in to submit your flag.


Learning With Errors 2

 Toggle
  • Noise Free
    40 pts · 408 Solves · 7 Solutions
    The addition of the noise term is what makes learning into learning with errors. How well can you learn if you don't have to deal with errors?

    Connect at socket.cryptohack.org 13411

    Challenge files:
      - 13411.py


    Challenge contributed by ireland

    You must be logged in to submit your flag.


  • Bounded Noise
    50 pts · 195 Solves · 4 Solutions
    I find implementing gaussian sampling to be hard and slow, so I prefer binary sampling

    Challenge files:
      - bounded_noise.sage
      - output.txt


    Challenge contributed by deuterium

    You must be logged in to submit your flag.


  • Nativity
    60 pts · 257 Solves · 7 Solutions
    LWE is easy, so I made my own implementation that works with native integers.

    Challenge files:
      - nativity.py
      - public_key.txt
      - ciphertexts.txt


    Challenge contributed by ireland and defund

    You must be logged in to submit your flag.


  • Missing Modulus
    80 pts · 227 Solves · 4 Solutions
    I just created my first LWE cryptosystem, I hope I didn't forget anything important...

    Connect at socket.cryptohack.org 13412

    Challenge files:
      - 13412.py


    Challenge contributed by ireland

    You must be logged in to submit your flag.


  • Noise Cheap
    90 pts · 187 Solves · 3 Solutions
    A core part of making LWE secure is having the noise terms be larger than what lattice reduction algorithms can handle.

    Connect at socket.cryptohack.org 13413

    Challenge files:
      - 13413.py


    Challenge contributed by ireland

    You must be logged in to submit your flag.


  • Too Many Errors
    100 pts · 414 Solves · 7 Solutions
    To protect my flag against quantum computers, I've used a quantum-safe Learning With Errors (LWE) distribution on Z_127 to encrypt it. The LWE sample generator is not quite finished though, sometimes it outputs a faulty sample...

    Connect at socket.cryptohack.org 13390

    Challenge files:
      - 13390.py


    Challenge contributed by joachim

    You must be logged in to submit your flag.


Level Up

level up icon

You are now level Current level