# On Lattices, Learning with Errors, Random Linear Codes, and Cryptography

arXiv: https://arxiv.org/abs/2401.03703 · HTML: https://mlsanity.com/paper/2401.03703/

## Key facts

- Cited by 7 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Jan 2024.

## Built on by (most cited first, 7 of 7)

- [PQS-BFL: A Post-Quantum Secure Blockchain-based Federated Learning Framework](https://mlsanity.com/paper/2505.01866/) (2025)
- [Quantum advantage for learning shallow neural networks with natural data distributions](https://mlsanity.com/paper/2503.20879/) (2025)
- [Approximating the Number of Relevant Variables in a Parity Implies Proper Learning](https://mlsanity.com/paper/2407.11832/) (2024)
- [Speed-up of Data Analysis with Kernel Trick in Encrypted Domain](https://mlsanity.com/paper/2406.09716/) (2024)
- [Collaborative penetration testing suite for emerging generative AI algorithms](https://mlsanity.com/paper/2510.19303/) (2025)
- [SoK: Enhancing Cryptographic Collaborative Learning with Differential Privacy](https://mlsanity.com/paper/2601.09460/) (2026)
- [Post-Quantum Secure Federated DeFi for Inclusive Banking](https://mlsanity.com/paper/2606.10658/) (2026)

## Abstract (arXiv)

Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the `learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., non-quantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size tildeO(n2) and encrypting a message increases its size by a factor of tildeO(n) (in previous cryptosystems these values are tildeO(n4) and tildeO(n2), respectively). In fact, under the assumption that all parties share a random bit string of length tildeO(n2), the size of the public key can be reduced to tildeO(n).