Rating:
### crypto/learning-without-errors
This challenge is based on a [passive attack which broke the CKKS cryptosystem last year](https://eprint.iacr.org/2020/1533). The gist of it is that CKKS Ring Learning With Errors cryptosystem encrypts the message as a pair `(c_0, c_1) = (a, a * s + m + e)` where `s` is the secret, `m` is the message, `a` is a random ring element, and `e` is a "small" secret error. If `e` and `s` are unknown, then recovering `m` from this requires solving a hard lattice problem. However, when decrypting, CKKS returns `m + e`, which just ... tells you ... what the secret error is.
Basic algebra then gives `s = (c_1 - (m + e)) * c_0^{-1}`. Therefore, seeing a pair of encrypted and decrypted values is enough for a passive adversary to completely recover the secret key!
However, this does seemingly require `c_0` to be invertible in the ring, which for our parameters is `Zmod(2^100)[x] / [x^1024]`. The power-of-two modulus sometimes raises an issue.
```python
q = 1 << 100
N = 10
Rbase.<x> = PolynomialRing(Zmod(q))
R.<x> = Rbase.quotient(x^N + 1)
```
But you can solve it in `ZMod(2)` instead of `Zmod(q)`, where it has a much higher change of being invertible. Or you can solve it over the p-adics (this was the intended solution, which is way more complicated that the other approach).
The challenge had a low number of solves, probably because RLWE is not common in CTFs.
