# Wiki

Clone wiki# 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