(Ring-)LWE oracle generators

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 [LPR2010] 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: S = samples(30, 20, 'Regev')
sage: len(S)
30
sage: S[0][0].parent(), S[0][1].parent()
(Vector space of dimension 20 over Ring of integers modulo 401,
 Ring of integers modulo 401)

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: S = samples(30, 20, LindnerPeikert)
sage: len(S)
30
sage: S[0][0].parent(), S[0][1].parent()
(Vector space of dimension 20 over Ring of integers modulo 2053,
 Ring of integers modulo 2053)

Finally, samples() also accepts instances of classes:

sage: from sage.crypto.lwe import LindnerPeikert
sage: lwe = LindnerPeikert(20)
sage: S = samples(30, 20, lwe)
sage: len(S)
30
sage: S[0][0].parent(), S[0][1].parent()
(Vector space of dimension 20 over Ring of integers modulo 2053,
 Ring of integers modulo 2053)

Note that Ring-LWE samples are returned as vectors:

sage: from sage.crypto.lwe import RingLWE
sage: from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
sage: D = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], euler_phi(16), 5)
sage: ringlwe = RingLWE(16, 257, D, secret_dist='uniform')
sage: p = samples(30, euler_phi(16), ringlwe)[0][0].parent(); p
Vector space of dimension 8 over Ring of integers modulo 257
sage: assert all(c.parent() is p for b in samples(30, euler_phi(16), ringlwe) for c in b)

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: from sage.crypto.lwe import samples
sage: for s in samples(30, 20, 'Regev', balanced=True):
....:     s1 = list(s[0]) + [s[1]]
....:     assert all(-401//2 <= b <= 401//2 for b in s1)

AUTHORS:

  • Martin Albrecht

  • Robert Fitzpatrick

  • Daniel Cabracas

  • Florian Göpfert

  • Michael Schneider

REFERENCES:

class sage.crypto.lwe.LWE(n, q, D, secret_dist='uniform', m=None)

Bases: sage.structure.sage_object.SageObject

Learning with Errors (LWE) oracle.

__init__(n, q, D, secret_dist='uniform', m=None)

Construct an LWE oracle in dimension n over a ring of order q with noise distribution D.

INPUT:

  • n - dimension (integer > 0)

  • q - modulus typically > n (integer > 0)

  • D - an error distribution such as an instance of DiscreteGaussianDistributionIntegerSampler or UniformSampler

  • secret_dist - distribution of the secret (default: ‘uniform’); one of

    • “uniform” - secret follows the uniform distribution in \(\Zmod{q}\)

    • “noise” - secret follows the noise distribution

    • (lb,ub) - the secret is chosen uniformly from [lb,...,ub] including both endpoints

  • m - number of allowed samples or None if no such limit exists (default: None)

EXAMPLES:

First, we construct a noise distribution with standard deviation 3.0:

sage: from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler
sage: D = DiscreteGaussianDistributionIntegerSampler(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, Discrete Gaussian sampler over the Integers with sigma = 3.000000 and c = 0, 'uniform', None)

and sample 1000 samples:

sage: L = []
sage: def add_samples():
....:     global L
....:     L += [lwe() for _ in range(1000)]
sage: add_samples()

To test the oracle, we use the internal secret to evaluate the samples in the secret:

sage: S = lambda : [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: while abs(sqrt(variance([e if e <= 200 else e-401 for e in S()]).n()) - 3.0) > 0.01:
....:     add_samples()

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.
__call__()

EXAMPLES:

sage: from sage.crypto.lwe import DiscreteGaussianDistributionIntegerSampler, LWE
sage: LWE(10, 401, DiscreteGaussianDistributionIntegerSampler(3))()[0].parent()
Vector space of dimension 10 over Ring of integers modulo 401
sage: LWE(10, 401, DiscreteGaussianDistributionIntegerSampler(3))()[1].parent()
Ring of integers modulo 401
class sage.crypto.lwe.LindnerPeikert(n, delta=0.01, m=None)

Bases: sage.crypto.lwe.LWE

LWE oracle with parameters as in [LP2011].

__init__(n, delta=0.01, m=None)

Construct LWE instance parameterised by security parameter n where the modulus q and the stddev of the noise is chosen as in [LP2011].

INPUT:

  • n - security parameter (integer > 0)

  • delta - error probability per symbol (default: 0.01)

  • m - number of allowed samples or None in which case m=2*n + 128 as in [LP2011] (default: None)

EXAMPLES:

sage: from sage.crypto.lwe import LindnerPeikert
sage: LindnerPeikert(n=20)
LWE(20, 2053, Discrete Gaussian sampler over the Integers with sigma = 3.600954 and c = 0, 'noise', 168)
class sage.crypto.lwe.Regev(n, secret_dist='uniform', m=None)

Bases: sage.crypto.lwe.LWE

LWE oracle with parameters as in [Reg09].

__init__(n, secret_dist='uniform', m=None)

Construct LWE instance parameterised by security parameter n where the modulus q and the stddev of the noise are chosen as in [Reg09].

INPUT:

  • n - security parameter (integer > 0)

  • secret_dist - distribution of the secret. See documentation of LWE for details (default=’uniform’)

  • m - number of allowed samples or None if no such limit exists (default: None)

EXAMPLES:

sage: from sage.crypto.lwe import Regev
sage: Regev(n=20)
LWE(20, 401, Discrete Gaussian sampler over the Integers with sigma = 1.915069 and c = 401, 'uniform', None)
class sage.crypto.lwe.RingLWE(N, q, D, poly=None, secret_dist='uniform', m=None)

Bases: sage.structure.sage_object.SageObject

Ring Learning with Errors oracle.

__init__(N, q, D, poly=None, secret_dist='uniform', m=None)

Construct a Ring-LWE oracle in dimension n=phi(N) over a ring of order q with noise distribution D.

INPUT:

  • N - index of cyclotomic polynomial (integer > 0, must be power of 2)

  • q - modulus typically > N (integer > 0)

  • D - an error distribution such as an instance of DiscreteGaussianDistributionPolynomialSampler or UniformSampler

  • poly - a polynomial of degree phi(N). If None the cyclotomic polynomial used (default: None).

  • secret_dist - distribution of the secret. See documentation of LWE for details (default=’uniform’)

  • m - number of allowed samples or None if no such limit exists (default: None)

EXAMPLES:

sage: from sage.crypto.lwe import RingLWE
sage: from sage.stats.distributions.discrete_gaussian_polynomial import DiscreteGaussianDistributionPolynomialSampler
sage: D = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], n=euler_phi(20), sigma=3.0)
sage: RingLWE(N=20, q=next_prime(800), D=D)
RingLWE(20, 809, Discrete Gaussian sampler for polynomials of degree < 8 with σ=3.000000 in each component, x^8 - x^6 + x^4 - x^2 + 1, 'uniform', None)
__call__()

EXAMPLES:

sage: from sage.crypto.lwe import DiscreteGaussianDistributionPolynomialSampler, RingLWE
sage: N = 16
sage: n = euler_phi(N)
sage: D = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], n, 5)
sage: ringlwe = RingLWE(N, 257, D, secret_dist='uniform')
sage: ringlwe()[0].parent()
Vector space of dimension 8 over Ring of integers modulo 257
sage: ringlwe()[1].parent()
Vector space of dimension 8 over Ring of integers modulo 257
class sage.crypto.lwe.RingLWEConverter(ringlwe)

Bases: sage.structure.sage_object.SageObject

Wrapper callable to convert Ring-LWE oracles into LWE oracles by disregarding the additional structure.

__init__(ringlwe)

INPUT:

  • ringlwe - an instance of a RingLWE

EXAMPLES:

sage: from sage.crypto.lwe import DiscreteGaussianDistributionPolynomialSampler, RingLWE, RingLWEConverter
sage: D = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], euler_phi(16), 5)
sage: lwe = RingLWEConverter(RingLWE(16, 257, D, secret_dist='uniform'))
sage: set_random_seed(1337)
sage: lwe()
((32, 216, 3, 125, 58, 197, 171, 43), ...)
__call__()

EXAMPLES:

sage: from sage.crypto.lwe import DiscreteGaussianDistributionPolynomialSampler, RingLWE, RingLWEConverter
sage: D = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], euler_phi(16), 5)
sage: lwe = RingLWEConverter(RingLWE(16, 257, D, secret_dist='uniform'))
sage: set_random_seed(1337)
sage: lwe()
((32, 216, 3, 125, 58, 197, 171, 43), ...)
class sage.crypto.lwe.RingLindnerPeikert(N, delta=0.01, m=None)

Bases: sage.crypto.lwe.RingLWE

Ring-LWE oracle with parameters as in [LP2011].

__init__(N, delta=0.01, m=None)

Construct a Ring-LWE oracle in dimension n=phi(N) where the modulus q and the stddev of the noise is chosen as in [LP2011].

INPUT:

  • N - index of cyclotomic polynomial (integer > 0, must be power of 2)

  • delta - error probability per symbol (default: 0.01)

  • m - number of allowed samples or None in which case 3*n is used (default: None)

EXAMPLES:

sage: from sage.crypto.lwe import RingLindnerPeikert
sage: RingLindnerPeikert(N=16)
RingLWE(16, 1031, Discrete Gaussian sampler for polynomials of degree < 8 with σ=2.803372 in each component, x^8 + 1, 'noise', 24)
class sage.crypto.lwe.UniformNoiseLWE(n, instance='key', m=None)

Bases: sage.crypto.lwe.LWE

LWE oracle with uniform secret with parameters as in [CGW2013].

__init__(n, instance='key', m=None)

Construct LWE instance parameterised by security parameter n where all other parameters are chosen as in [CGW2013].

INPUT:

  • n - security parameter (integer >= 89)

  • instance - one of

    • “key” - the LWE-instance that hides the secret key is generated

    • “encrypt” - the LWE-instance that hides the message is generated (default: key)

  • m - number of allowed samples or None in which case m is chosen as in [CGW2013]. (default: None)

EXAMPLES:

sage: from sage.crypto.lwe import UniformNoiseLWE
sage: UniformNoiseLWE(89)
LWE(89, 64311834871, UniformSampler(0, 6577), 'noise', 131)

sage: UniformNoiseLWE(89, instance='encrypt')
LWE(131, 64311834871, UniformSampler(0, 11109), 'noise', 181)
class sage.crypto.lwe.UniformPolynomialSampler(P, n, lower_bound, upper_bound)

Bases: sage.structure.sage_object.SageObject

Uniform sampler for polynomials.

EXAMPLES:

sage: from sage.crypto.lwe import UniformPolynomialSampler
sage: UniformPolynomialSampler(ZZ['x'], 8, -2, 2)().parent()
Univariate Polynomial Ring in x over Integer Ring
__init__(P, n, lower_bound, upper_bound)

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:

  • P - a univariate polynomial ring over the Integers

  • n - number of coefficients to be sampled

  • lower_bound - integer

  • upper_bound - integer

EXAMPLES:

sage: from sage.crypto.lwe import UniformPolynomialSampler
sage: UniformPolynomialSampler(ZZ['x'], 10, -10, 10)
UniformPolynomialSampler(10, -10, 10)
__call__()

Return a new sample.

EXAMPLES:

sage: from sage.crypto.lwe import UniformPolynomialSampler
sage: sampler = UniformPolynomialSampler(ZZ['x'], 8, -12, 12)
sage: sampler().parent()
Univariate Polynomial Ring in x over Integer Ring
class sage.crypto.lwe.UniformSampler(lower_bound, upper_bound)

Bases: sage.structure.sage_object.SageObject

Uniform sampling in a range of integers.

EXAMPLES:

sage: from sage.crypto.lwe import UniformSampler
sage: sampler = UniformSampler(-2, 2); sampler
UniformSampler(-2, 2)
sage: sampler() in range(-2, 3)
True
__init__(lower_bound, upper_bound)

Construct a uniform sampler with bounds lower_bound and upper_bound (both endpoints inclusive).

INPUT:

  • lower_bound - integer

  • upper_bound - integer

EXAMPLES:

sage: from sage.crypto.lwe import UniformSampler
sage: UniformSampler(-2, 2)
UniformSampler(-2, 2)
__call__()

Return a new sample.

EXAMPLES:

sage: from sage.crypto.lwe import UniformSampler
sage: sampler = UniformSampler(-12, 12)
sage: sampler() in range(-12, 13)
True
sage.crypto.lwe.balance_sample(s, q=None)

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 \(\Zmod{q}\).

INPUT:

  • s - sample of the form (a,c) where a is a vector and c is a scalar

  • q - modulus (default: None)

EXAMPLES:

sage: from sage.crypto.lwe import balance_sample, samples, Regev
sage: for s in samples(10, 5, Regev):
....:     b = balance_sample(s)
....:     assert all(-29//2 <= c <= 29//2 for c in b[0])
....:     assert -29//2 <= b[1] <= 29//2
....:     assert all(s[0][j] == b[0][j] % 29 for j in range(5))
....:     assert s[1] == b[1] % 29


sage: from sage.crypto.lwe import balance_sample, DiscreteGaussianDistributionPolynomialSampler, RingLWE, samples
sage: D = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], 8, 5)
sage: rlwe = RingLWE(20, 257, D)
sage: for s in samples(10, 8, rlwe):
....:     b = balance_sample(s)
....:     assert all(-257//2 <= c <= 257//2 for bi in b for c in bi)
....:     assert all(s[i][j] == b[i][j] % 257 for i in range(2) for j in range(8))

Note

This function is useful to convert between Sage’s standard representation of elements in \(\Zmod{q}\) 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.

sage.crypto.lwe.samples(m, n, lwe, seed=None, balanced=False, **kwds)

Return m LWE samples.

INPUT:

  • m - the number of samples (integer > 0)

  • n - the security parameter (integer > 0)

  • lwe - either

    • a subclass of LWE such as Regev or LindnerPeikert

    • an instance of LWE or any subclass

    • the name of any such class (e.g., “Regev”, “LindnerPeikert”)

  • seed - seed to be used for generation or None if no specific seed shall be set (default: None)

  • balanced - use function balance_sample() to return balanced representations of finite field elements (default: False)

  • **kwds - passed through to LWE constructor

EXAMPLES:

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), 15),
 ((365, 227, 333, 165, 76, 328, 288, 206, 286, 42, 175, 155, 190, 275, 114, 280, 45, 218, 304, 386), 143)]

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), 15),
 ((-36, -174, -68, 165, 76, -73, -113, -195, -115, 42, 175, 155, 190, -126, 114, -121, 45, -183, -97, -15), 143)]

sage: from sage.crypto.lwe import samples
sage: samples(2, 20, 'LindnerPeikert')
[((506, 1205, 398, 0, 337, 106, 836, 75, 1242, 642, 840, 262, 1823, 1798, 1831, 1658, 1084, 915, 1994, 163), 1447),
 ((463, 250, 1226, 1906, 330, 933, 1014, 1061, 1322, 2035, 1849, 285, 1993, 1975, 864, 1341, 41, 1955, 1818, 1357), 312)]