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: from sage.crypto.lwe import samples
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: from sage.crypto.lwe import samples, LindnerPeikert
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: from sage.crypto.lwe import LindnerPeikert
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: from sage.crypto.lwe import DiscreteGaussianPolynomialSamplerRejection, RingLWE
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 . These are represented
as elements in
by Sage. However, it usually is more natural to think
of these entries as integers in
. 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: from sage.crypto.lwe import samples
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:
REFERENCES:
[Reg09] | (1, 2, 3, 4) 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] | (1, 2, 3, 4, 5) 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] | (1, 2) 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 |
Bases: sage.structure.sage_object.SageObject
Discrete Gaussian sampler for polynomials.
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianPolynomialSamplerRejection
sage: DiscreteGaussianPolynomialSamplerRejection(8, 3.0)()
x^7 - x^6 - 2*x^4 + 2*x^3 - x^2 + x - 1
sage: gs = DiscreteGaussianPolynomialSamplerRejection(8, 3.0, precision=100, tailcut=1.0)
sage: [gs() for _ in xrange(3)]
[-x^7 + x^6 + 2*x^5 + 2*x^4 - x^3 - x^2 - 1,
x^7 - 2*x^6 + 2*x^5 + x^4 - x^3 + 2*x^2 - x + 2,
x^5 + 2*x^3 + 2*x + 1]
Construct a sampler for univariate polynomials of degree n-1 where coefficients are drawn independently with standard deviation stddev using D.
INPUT:
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianPolynomialSamplerRejection
sage: DiscreteGaussianPolynomialSamplerRejection(8, 3.0)()
x^7 - x^6 - 2*x^4 + 2*x^3 - x^2 + x - 1
sage: gs = DiscreteGaussianPolynomialSamplerRejection(8, 3.0, precision=100, tailcut=1.0)
sage: [gs() for _ in xrange(3)]
[-x^7 + x^6 + 2*x^5 + 2*x^4 - x^3 - x^2 - 1,
x^7 - 2*x^6 + 2*x^5 + x^4 - x^3 + 2*x^2 - x + 2,
x^5 + 2*x^3 + 2*x + 1]
Return a new sample.
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianPolynomialSamplerRejection
sage: sampler = DiscreteGaussianPolynomialSamplerRejection(8, 12.0)
sage: sampler()
x^7 - 9*x^5 + 2*x^4 + 8*x^3 - 5*x^2 + 7*x - 5
alias of DiscreteGaussianSamplerRejection
Bases: sage.structure.sage_object.SageObject
Discrete Gaussian sampler using rejection sampling.
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianSamplerRejection
sage: DiscreteGaussianSamplerRejection(3.0)()
-1
sage: gs = DiscreteGaussianSamplerRejection(3.0, precision=100, tailcut=1.0)
sage: all(gs() <= 3.0 for _ in xrange(1000))
True
Construct a new discrete Gaussian sampler.
INPUT:
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianSamplerRejection
sage: gs = DiscreteGaussianSamplerRejection(3.0)
sage: sqrt(variance([gs() for _ in xrange(1000)])).n()
2.965...
Return a new sample.
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianSamplerRejection
sage: sampler = DiscreteGaussianSamplerRejection(12.0)
sage: sampler()
-5
Bases: sage.structure.sage_object.SageObject
Learning with Errors (LWE) oracle.
Construct an LWE oracle in dimension n over a ring of order q with noise distribution D.
INPUT:
EXAMPLE:
First, we construct a noise distribution with standard deviation 3.0:
sage: from sage.crypto.lwe import DiscreteGaussianSampler
sage: D = DiscreteGaussianSampler(3.0)
Next, we construct our oracle:
sage: from sage.crypto.lwe import LWE
sage: lwe = LWE(n=20, q=next_prime(400), D=D); lwe
LWE(20, 401, DiscreteGaussianSamplerRejection(3.000000, 53, 4), 'uniform', None)
and sample 1000 samples:
sage: L = [lwe() for _ in range(1000)]
To test the oracle, we use the internal secret to evaluate the samples in the secret:
sage: S = [ZZ(a.dot_product(lwe._LWE__s) - c) for (a,c) in L]
However, while Sage represents finite field elements between 0 and q-1 we rely on a balanced representation of those elements here. Hence, we fix the representation and recover the correct standard deviation of the noise:
sage: sqrt(variance([e if e <= 200 else e-401 for e in S]).n())
3.0...
If m is not None the number of available samples is restricted:
sage: from sage.crypto.lwe import LWE
sage: lwe = LWE(n=20, q=next_prime(400), D=D, m=30)
sage: _ = [lwe() for _ in range(30)]
sage: lwe() # 31
Traceback (most recent call last):
...
IndexError: Number of available samples exhausted.
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianSampler, LWE
sage: LWE(10, 401, DiscreteGaussianSampler(3))()
((309, 347, 198, 194, 336, 360, 264, 123, 368, 398), 198)
Bases: sage.crypto.lwe.LWE
LWE oracle with parameters as in [LP11].
Construct LWE instance parameterised by security parameter n where the modulus q and the stddev of the noise is chosen as in [LP11].
INPUT:
EXAMPLES:
sage: from sage.crypto.lwe import LindnerPeikert
sage: LindnerPeikert(n=20)
LWE(20, 2053, DiscreteGaussianSamplerRejection(3.600954, 53, 4), 'noise', 168)
Bases: sage.crypto.lwe.LWE
LWE oracle with parameters as in [Reg09].
Construct LWE instance parameterised by security parameter n where the modulus q and the stddev of the noise are chosen as in [Reg09].
INPUT:
EXAMPLES:
sage: from sage.crypto.lwe import Regev
sage: Regev(n=20)
LWE(20, 401, DiscreteGaussianSamplerRejection(1.915069, 401, 4), 'uniform', None)
Bases: sage.structure.sage_object.SageObject
Ring Learning with Errors oracle.
Construct a Ring-LWE oracle in dimension n=phi(N) over a ring of order q with noise distribution D.
INPUT:
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianPolynomialSampler, RingLWE
sage: D = DiscreteGaussianPolynomialSampler(n=euler_phi(20), stddev=3.0)
sage: RingLWE(N=20, q=next_prime(800), D=D);
RingLWE(20, 809, DiscreteGaussianPolynomialSamplerRejection(8, 3.000000, 53, 4), x^8 - x^6 + x^4 - x^2 + 1, 'uniform', None)
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianPolynomialSampler, RingLWE
sage: N = 16
sage: n = euler_phi(N)
sage: D = DiscreteGaussianPolynomialSampler(n, 5)
sage: ringlwe = RingLWE(N, 257, D, secret_dist='uniform')
sage: ringlwe()
((228, 149, 226, 198, 38, 222, 222, 127), (177, 138, 68, 134, 74, 162, 203, 243))
Bases: sage.structure.sage_object.SageObject
Wrapper callable to convert Ring-LWE oracles into LWE oracles by disregarding the additional structure.
INPUT:
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianPolynomialSampler, RingLWE, RingLWEConverter
sage: D = DiscreteGaussianPolynomialSampler(euler_phi(16), 5)
sage: lwe = RingLWEConverter(RingLWE(16, 257, D, secret_dist='uniform'))
sage: set_random_seed(1337)
sage: lwe()
((130, 32, 216, 3, 125, 58, 197, 171), 182)
EXAMPLE:
sage: from sage.crypto.lwe import DiscreteGaussianPolynomialSampler, RingLWE, RingLWEConverter
sage: D = DiscreteGaussianPolynomialSampler(euler_phi(16), 5)
sage: lwe = RingLWEConverter(RingLWE(16, 257, D, secret_dist='uniform'))
sage: set_random_seed(1337)
sage: lwe()
((130, 32, 216, 3, 125, 58, 197, 171), 182)
Bases: sage.crypto.lwe.RingLWE
Ring-LWE oracle with parameters as in [LP11].
Construct a Ring-LWE oracle in dimension n=phi(N) where the modulus q and the stddev of the noise is chosen as in [LP11].
INPUT:
EXAMPLES:
sage: from sage.crypto.lwe import RingLindnerPeikert
sage: RingLindnerPeikert(N=16)
RingLWE(16, 1031, DiscreteGaussianPolynomialSamplerRejection(8, 2.803372, 53, 4), x^8 + 1, 'noise', 24)
Bases: sage.crypto.lwe.LWE
LWE oracle with uniform secret with parameters as in [CGW13].
Construct LWE instance parameterised by security parameter n where all other parameters are chosen as in [CGW13].
INPUT:
EXAMPLES:
sage: from sage.crypto.lwe import UniformNoiseLWE
sage: UniformNoiseLWE(89)
LWE(89, 154262477, UniformSampler(0, 351), 'noise', 131)
sage: UniformNoiseLWE(89, instance='encrypt')
LWE(131, 154262477, UniformSampler(0, 497), 'noise', 181)
Bases: sage.structure.sage_object.SageObject
Uniform sampler for polynomials.
EXAMPLE:
sage: from sage.crypto.lwe import UniformPolynomialSampler
sage: UniformPolynomialSampler(8, -2, 2)()
-2*x^7 + x^6 - 2*x^5 - x^3 - 2*x^2 - 2
Construct a sampler for univariate polynomials of degree n-1 where coefficients are drawn uniformly at random between lower_bound and upper_bound (both endpoints inclusive).
INPUT:
EXAMPLE:
sage: from sage.crypto.lwe import UniformPolynomialSampler
sage: UniformPolynomialSampler(10, -10, 10)
UniformPolynomialSampler(10, -10, 10)
Return a new sample.
EXAMPLE:
sage: from sage.crypto.lwe import UniformPolynomialSampler
sage: sampler = UniformPolynomialSampler(8, -12, 12)
sage: sampler()
-10*x^7 + 5*x^6 - 8*x^5 + x^4 - 4*x^3 - 11*x^2 - 10
Bases: sage.structure.sage_object.SageObject
Uniform sampling in a range of integers.
EXAMPLE:
sage: from sage.crypto.lwe import UniformSampler
sage: sampler = UniformSampler(-2, 2); sampler
UniformSampler(-2, 2)
sage: sampler()
-2
Construct a uniform sampler with bounds lower_bound and upper_bound (both endpoints inclusive).
INPUT:
EXAMPLE:
sage: from sage.crypto.lwe import UniformSampler
sage: UniformSampler(-2, 2)
UniformSampler(-2, 2)
Return a new sample.
EXAMPLE:
sage: from sage.crypto.lwe import UniformSampler
sage: sampler = UniformSampler(-12, 12)
sage: sampler()
-10
Given (a,c) = s return a tuple (a',c') where a' is an integer vector with entries between -q//2 and q//2 and c is also within these bounds.
If q is given (a,c) = s may live in the integers. If q is not
given, then (a,c) are assumed to live in .
INPUT:
EXAMPLE:
sage: from sage.crypto.lwe import balance_sample, samples, Regev
sage: map(balance_sample, samples(10, 5, Regev))
[((-9, -4, -4, 4, -4), 6), ((-3, -10, 8, -3, -1), -10), ((-6, -12, -3, -2, -6), -6),
...
((-1, -8, -11, 13, 4), -6), ((10, 11, -3, -13, 0), 6), ((6, -1, 2, -11, 14), 2)]
sage: from sage.crypto.lwe import balance_sample, DiscreteGaussianPolynomialSampler, RingLWE, samples
sage: D = DiscreteGaussianPolynomialSampler(8, 5)
sage: rlwe = RingLWE(20, 257, D)
sage: map(balance_sample, samples(10, 8, rlwe))
[((5, -55, -31, -90, 6, 100, -46, -107), (6, -64, -40, 117, 27, 54, -98, -56)),
((109, -106, 28, 77, -14, -109, 115, 34), (82, 17, -89, 62, 1, -77, 128, 64)),
...
((-32, 51, -110, -106, 35, -82, 14, -113), (126, -120, 126, 119, 101, 3, -122, -75))]
Note
This function is useful to convert between Sage’s standard
representation of elements in as integers between 0 and q-1
and the usual representation of such elements in lattice cryptography as
integers between -q//2 and q//2.
Return m LWE samples.
INPUT:
EXAMPLE:
sage: from sage.crypto.lwe import samples, Regev
sage: samples(2, 20, Regev, seed=1337)
[((199, 388, 337, 53, 200, 284, 336, 215, 75, 14, 274, 234, 97, 255, 246, 153, 268, 218, 396, 351), 18),
((286, 42, 175, 155, 190, 275, 114, 280, 45, 218, 304, 386, 98, 235, 77, 0, 65, 20, 163, 14), 334)]
sage: from sage.crypto.lwe import samples, Regev
sage: samples(2, 20, Regev, balanced=True, seed=1337)
[((199, -13, -64, 53, 200, -117, -65, -186, 75, 14, -127, -167, 97, -146, -155, 153, -133, -183, -5, -50), 18),
((-115, 42, 175, 155, 190, -126, 114, -121, 45, -183, -97, -15, 98, -166, 77, 0, 65, 20, 163, 14), -67)]
sage: from sage.crypto.lwe import samples
sage: samples(2, 20, 'LindnerPeikert')
[((1302, 718, 1397, 147, 278, 979, 1185, 133, 902, 1180, 1264, 734, 2029, 314, 428, 18, 707, 2021, 1153, 173), 1127),
((2015, 1278, 455, 429, 1391, 186, 149, 1199, 220, 1629, 843, 719, 1744, 1568, 674, 1462, 1549, 972, 248, 1066), 1422)]