lwe-generator / Home

The Learning with Errors problem (LWE) is solving linear systems of equations where the right hand side has been disturbed 'slightly' where 'slightly' is made precise by a noise distribution - typically a discrete Gaussian distribution. See [Reg09] for details.

The Ring Learning with Errors problem (LWE) is solving a set of univariate polynomial equations - typically in a cyclotomic field - where the right hand side was disturbed 'slightly'. See [LPR10] for details.

This module implements generators of LWE samples where parameters are chosen following proposals in the cryptographic literature.

Examples

We get 30 samples from an LWE oracle parameterised by security parameter `n=20` and where the modulus and the standard deviation of the noise are chosen as in [Reg09]:

```sage: samples(30, 20, 'Regev')
[((360, 264, 123, 368, 398, 392, 41, 84, 25, 389, 311, 68, 322, 41, 161, 372, 222, 153, 243, 381), 126),
...
((138, 198, 204, 235, 339, 168, 269, 276, 392, 243, 86, 18, 378, 20, 369, 141, 108, 151, 336, 141), 102)]
```

We may also pass classes to the samples function, which is useful for users implementing their own oracles:

```sage: samples(30, 20, LindnerPeikert)
[((350, 835, 2023, 1785, 1958, 1818, 1130, 1285, 1331, 284, 2048, 441, 1581, 1406, 1185, 1724, 1397, 258, 994, 1056), 1902),
...
((1918, 1823, 1598, 18, 588, 1093, 744, 1934, 689, 1327, 1632, 1867, 228, 378, 798, 511, 274, 1001, 1709, 154), 184)]
```

Finally, samples also accepts instances of classes:

```sage: lwe = LindnerPeikert(20)
sage: samples(30, 20, lwe)
[((1817, 1322, 818, 1232, 354, 639, 1770, 754, 1366, 1731, 649, 162, 483, 1741, 1942, 1232, 1424, 1034, 50, 448), 1316),
...
((2021, 829, 572, 1698, 1025, 170, 598, 1193, 1268, 607, 1502, 1984, 1655, 206, 958, 334, 1213, 1413, 827, 1423), 546)]
```

Note that Ring-LWE samples are returned as vectors:

```sage: D = DiscreteGaussianPolynomialSamplerRejection(euler_phi(16), 5)
sage: ringlwe = RingLWE(16, 257, D, secret_dist='uniform')
sage: samples(30, euler_phi(16), ringlwe)
[((158, 49, 174, 179, 109, 92, 234, 41), (200, 159, 131, 197, 241, 172, 1, 107)),
...
((80, 227, 249, 205, 149, 92, 46, 68), (69, 256, 29, 219, 218, 34, 182, 178))]
```

One technical issue when working with these generators is that by default they return vectors and scalars over/in rings modulo some `q`. These are represented as elements in `(0,q-1)` by Sage. However, it usually is more natural to think of these entries as integers in `(-q//2,q//2)`. To allow for this, this module provides the option to balance the representation. In this case vectors and scalars over/in the integers are returned:

```sage: samples(30, 20, 'Regev', balanced=True)
[((-38, 59, -33, -80, 165, -55, -46, -49, -113, 135, -32, 185, -80, -184, 127, 153, 162, -31, 115, 178), 14),
...
((-165, -187, -87, 188, 160, -118, -7, 107, -77, -107, -109, 77, 63, -66, -55, -75, -12, 90, 58, -185), 6)]
```

Authors

• Martin Albrecht
• Robert Fitzpatrick
• Daniel Cabracas
• Florian Göpfert
• Michael Schneider

References

[Reg09] Oded Regev. On Lattices, Learning with Errors, Random Linear Codes, and Cryptography. in Journal of the ACM 56(6). ACM 2009, http://dx.doi.org/10.1145/1060590.1060603

[LP11] Richard Lindner and Chris Peikert. Better key sizes (and attacks) for LWE-based encryption. in Proceeding of the 11th international conference on Topics in cryptology: CT-RSA 2011. Springer 2011, http://dx.doi.org/10.1007/978-3-642-19074-2_21

[LPR10] Vadim Lyubashevsky, Chris Peikert, and Oded Regev. On Ideal Lattices and Learning with Errors over Rings. in Advances in Cryptology – EUROCRYPT 2010. Springer 2010. http://dx.doi.org/10.1007/978-3-642-13190-5_1

[CGW13] Daniel Cabarcas, Florian Göpfert, and Patrick Weiden. Provably Secure LWE-Encryption with Uniform Secret. Cryptology ePrint Archive, Report 2013/164. 2013. 2013/164. http://eprint.iacr.org/2013/164

Updated