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.
Before beginning this section you should have completed at least the "Lattices" section in the Mathematics category.
Throughout CryptoHack and especially in the Mathematics and RSA chapters, 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.
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, <A, S> + 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.
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 mod 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, <A,S> + 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.
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 < p
)
- scaling factor Δ = round(q / p)
Key-gen:
- The secret key S
is a random element of the vector space Zq^n
.
Ciphertext format:
- Ciphertexts consist of a pair A, b
, where A
is an element of the vector space Zq^n
, and b
is an element of Zq
.
Encryption given message m
:
1. Sample A
, a random element of the vector space Zq^n
2. Sample the error-term e
, an integer in the range [-Δ / 2, Δ / 2]
. (Note: often the error is sampled from a discrete Gaussian distribution, but uniform sampling is fine)
3. Compute b = <A,S> + Δ * m + e
4. Return the pair (A, b)
Decryption given ciphertext (A, b)
:
1. Compute x = b - <A,S> mod q
and then interpret x as an integer (not mod q)
2. Compute m = round(x / Δ)
, where the division and rounding happens over the integers
3. return m
In this system, decryption works because after the mask <A,S>
has been removed, the remaining equation for the noisy message Δ * 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 Δ * 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.
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 < p
)
- must have q
, p
be coprime
Key-gen:
- The secret key S
is a random element of the vector space Zq^n
.
Ciphertext format:
- Ciphertexts consist of a pair A, b
, where A
is an element of the vector space Zq^n
, and b
is an element of Zq
.
Encryption given message m
:
1. Sample A
, a random element of the vector space Zq^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 = <A,S> + m + p * e
4. Return the pair (A, b)
Decryption given ciphertext (A, b)
:
1. Compute x = b - <A,S> centered mod q
and then interpret x as an integer (not mod 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 <A,S>
has been removed, the remaining equation for the noisy message m + p * 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 mod p
. This requires the parameters to be chosen so that m + p * 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.
This can be turned into a public key cryptosystem by using the "additively homomorphic" property of LWE. That is, given an encryption <A, b>
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 <A, b + m_2>
for low-bit messages (high-bit noise) and <A, b + Δ · m_2>
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.
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.
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.
You are now level Current level