Coverage for local/lib/python2.7/site-packages/sage/crypto/lwe.py : 92%
Hot-keys on this page
r m x p toggle line displays
j k next/prev highlighted chunk
0 (zero) top of page
1 (one) first highlighted chunk
|
# -*- coding: utf-8 -*- (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: samples(30, 20, 'Regev') [((360, 264, 123, 368, 398, 392, 41, 84, 25, 389, 311, 68, 322, 41, 161, 372, 222, 153, 243, 381), 122), ... ((155, 22, 357, 312, 87, 298, 182, 163, 296, 181, 219, 135, 164, 308, 248, 320, 64, 166, 214, 104), 152)]
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) [((1275, 168, 1529, 2024, 1874, 1309, 16, 1869, 1114, 1696, 1645, 618, 1372, 1273, 683, 237, 1526, 879, 1305, 1355), 950), ... ((1787, 2033, 1677, 331, 1562, 49, 796, 1002, 627, 98, 91, 711, 1712, 418, 2024, 163, 1773, 184, 1548, 3), 1815)]
Finally, :func:`samples` also accepts instances of classes::
sage: from sage.crypto.lwe import LindnerPeikert sage: lwe = LindnerPeikert(20) sage: samples(30, 20, lwe) [((465, 180, 440, 706, 1367, 106, 1380, 614, 1162, 1354, 1098, 2036, 1974, 1417, 1502, 1431, 863, 1894, 1368, 1771), 618), ... ((1050, 1017, 1314, 1310, 1941, 2041, 484, 104, 1199, 1744, 161, 1905, 679, 1663, 531, 1630, 168, 1559, 1040, 1719), 1006)]
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: samples(30, euler_phi(16), ringlwe) [((41, 78, 232, 79, 223, 85, 26, 68), (195, 99, 106, 57, 93, 113, 23, 68)), ... ((185, 89, 244, 122, 249, 140, 173, 142), (98, 196, 70, 49, 55, 8, 158, 57))]
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: samples(30, 20, 'Regev', balanced=True) [((-105, 43, -25, -16, 57, 141, -108, 92, -173, 4, 179, -191, 164, 101, -16, -175, 172, 10, 147, 1), 114), ... ((-166, -147, 120, -56, 130, 163, 83, 17, -125, -159, -124, 19, 198, -181, -124, -155, 84, -15, -113, 113), 39)]
AUTHORS:
- Martin Albrecht - Robert Fitzpatrick - Daniel Cabracas - Florian Göpfert - Michael Schneider
REFERENCES:
- [Reg09]_
- [LP2011]_
- [LPR2010]_
- [CGW2013]_ """
""" 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() -2
.. automethod:: __init__ .. automethod:: __call__ """ """ 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) """ raise TypeError("lower bound must be <= upper bound.")
""" Return a new sample.
EXAMPLES::
sage: from sage.crypto.lwe import UniformSampler sage: sampler = UniformSampler(-12, 12) sage: sampler() -10 """
""" EXAMPLES::
sage: from sage.crypto.lwe import UniformSampler sage: UniformSampler(-2, 2) UniformSampler(-2, 2) """
""" Uniform sampler for polynomials.
EXAMPLES::
sage: from sage.crypto.lwe import UniformPolynomialSampler sage: UniformPolynomialSampler(ZZ['x'], 8, -2, 2)() -2*x^7 + x^6 - 2*x^5 - x^3 - 2*x^2 - 2
.. automethod:: __init__ .. automethod:: __call__ """ """ 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) """ raise TypeError("lower bound must be <= upper bound.")
""" Return a new sample.
EXAMPLES::
sage: from sage.crypto.lwe import UniformPolynomialSampler sage: sampler = UniformPolynomialSampler(ZZ['x'], 8, -12, 12) sage: sampler() -10*x^7 + 5*x^6 - 8*x^5 + x^4 - 4*x^3 - 11*x^2 - 10 """
""" EXAMPLES::
sage: from sage.crypto.lwe import UniformPolynomialSampler sage: UniformPolynomialSampler(ZZ['x'], 8, -3, 3) UniformPolynomialSampler(8, -3, 3) """
""" Learning with Errors (LWE) oracle.
.. automethod:: __init__ .. automethod:: __call__ """ """ 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 :class:`DiscreteGaussianDistributionIntegerSampler` or :class:`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 = [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. """
else: except (IndexError, TypeError): raise TypeError("Parameter secret_dist=%s not understood."%(secret_dist))
""" EXAMPLES::
sage: from sage.stats.distributions.discrete_gaussian_integer import DiscreteGaussianDistributionIntegerSampler sage: from sage.crypto.lwe import LWE sage: D = DiscreteGaussianDistributionIntegerSampler(3.0) 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)
sage: lwe = LWE(n=20, q=next_prime(400), D=D, secret_dist=(-3, 3)); lwe LWE(20, 401, Discrete Gaussian sampler over the Integers with sigma = 3.000000 and c = 0, (-3, 3), None) """ else:
""" EXAMPLES::
sage: from sage.crypto.lwe import DiscreteGaussianDistributionIntegerSampler, LWE sage: LWE(10, 401, DiscreteGaussianDistributionIntegerSampler(3))() ((309, 347, 198, 194, 336, 360, 264, 123, 368, 398), 198) """
""" LWE oracle with parameters as in [Reg09]_.
.. automethod:: __init__ """ """ 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 :class:`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) """
""" LWE oracle with parameters as in [LP2011]_.
.. automethod:: __init__ """ """ 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) """ # Find c>=1 such that c*exp((1-c**2)/2))**(2*n) == 2**-40 # (c*exp((1-c**2)/2))**(2*n) == 2**-40 # log((c*exp((1-c**2)/2))**(2*n)) == -40*log(2) # (2*n)*log(c*exp((1-c**2)/2)) == -40*log(2) # 2*n*(log(c)+log(exp((1-c**2)/2))) == -40*log(2) # 2*n*(log(c)+(1-c**2)/2) == -40*log(2) # 2*n*log(c)+n*(1-c**2) == -40*log(2) # 2*n*log(c)+n*(1-c**2) + 40*log(2) == 0 # Upper bound on s**2/t # Interpretation of "choose q just large enough to allow for a Gaussian parameter s>=8" in [LP2011]_ # Gaussian parameter as defined in [LP2011]_ # Transform s into stddev
""" LWE oracle with uniform secret with parameters as in [CGW2013]_.
.. automethod:: __init__ """ """ 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, 154262477, UniformSampler(0, 351), 'noise', 131)
sage: UniformNoiseLWE(89, instance='encrypt') LWE(131, 154262477, UniformSampler(0, 497), 'noise', 181) """
raise TypeError("Parameter too small")
raise TypeError("Parameter too small")
else: raise TypeError("Parameter instance=%s not understood."%(instance))
""" Ring Learning with Errors oracle.
.. automethod:: __init__ .. automethod:: __call__ """ """ 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 :class:`DiscreteGaussianDistributionPolynomialSampler` or :class:`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 :class:`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) """
raise ValueError("Noise distribution has dimensions %d != %d"%(D.n, self.n))
self.poly = poly else:
else: raise TypeError("Parameter secret_dist=%s not understood."%(secret_dist))
""" EXAMPLES::
sage: from sage.crypto.lwe import DiscreteGaussianDistributionPolynomialSampler, RingLWE sage: D = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], n=8, sigma=3.0) sage: RingLWE(N=16, q=next_prime(400), D=D); RingLWE(16, 401, Discrete Gaussian sampler for polynomials of degree < 8 with σ=3.000000 in each component, x^8 + 1, 'uniform', None) """ else: return "RingLWE(%d, %d, %s, %s, %s, %s)"%(self.N, self.K.order(), self.D, self.poly, self.secret_dist, self.m)
""" 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() ((228, 149, 226, 198, 38, 222, 222, 127), (178, 132, 72, 147, 77, 159, 187, 250)) """ if self.__i >= self.m: raise IndexError("Number of available samples exhausted.")
""" Ring-LWE oracle with parameters as in [LP2011]_.
.. automethod:: __init__ """ """ 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) """ # Find c>=1 such that c*exp((1-c**2)/2))**(2*n) == 2**-40 # i.e c>=1 such that 2*n*log(c)+n*(1-c**2) + 40*log(2) == 0 # Upper bound on s**2/t # Interpretation of "choose q just large enough to allow for a Gaussian parameter s>=8" in [LP2011]_ # Gaussian parameter as defined in [LP2011]_ # Transform s into stddev
""" Wrapper callable to convert Ring-LWE oracles into LWE oracles by disregarding the additional structure.
.. automethod:: __init__ .. automethod:: __call__ """ """ INPUT:
- ``ringlwe`` - an instance of a :class:`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() ((130, 32, 216, 3, 125, 58, 197, 171), 189) """
""" 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() ((130, 32, 216, 3, 125, 58, 197, 171), 189) """
""" EXAMPLES::
sage: from sage.crypto.lwe import DiscreteGaussianDistributionPolynomialSampler, RingLWE, RingLWEConverter sage: D = DiscreteGaussianDistributionPolynomialSampler(ZZ['x'], euler_phi(20), 5) sage: rlwe = RingLWE(20, 257, D) sage: lwe = RingLWEConverter(rlwe) sage: lwe RingLWEConverter(RingLWE(20, 257, Discrete Gaussian sampler for polynomials of degree < 8 with σ=5.000000 in each component, x^8 - x^6 + x^4 - x^2 + 1, 'uniform', None))
"""
""" Return ``m`` LWE samples.
INPUT:
- ``m`` - the number of samples (integer > 0) - ``n`` - the security parameter (integer > 0) - ``lwe`` - either
- a subclass of :class:`LWE` such as :class:`Regev` or :class:`LindnerPeikert` - an instance of :class:`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 :func:`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)]
"""
else: raise ValueError("Passed LWE instance has n=%d, but n=%d was passed to this function."%(lwe.n, n))
else:
r""" 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: list(map(balance_sample, samples(10, 5, Regev))) [((-9, -4, -4, 4, -4), 4), ((-8, 11, 12, -11, -11), -7), ... ((-11, 12, 0, -6, -3), 7), ((-7, 14, 8, 11, -8), -12)]
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: list(map(balance_sample, samples(10, 8, rlwe))) [((-7, -37, -64, 107, -91, -24, 120, 54), (74, 83, 18, 55, -53, 43, 4, 10)), ... ((-63, 34, 82, -112, 49, 89, -72, -41), (117, 43, 13, -37, 102, 55, -97, 56))]
.. 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. """
else: K = IntegerModRing(q) a = a.change_ring(K).change_ring(ZZ) c = c.change_ring(K).change_ring(ZZ)
else: |