simple lwe demo

test_lwe.sage

from sage.stats.distributions.discrete_gaussian_lattice import DiscreteGaussianDistributionLatticeSampler

def test_lwe(n, p, sigma, size=100):
    F = GF(p)
    a = random_vector(F, n)
    HALF_P = int(p/2)
    s = random_vector(F,n)
    p41 = int(p/4)
    p43 = int(p*3/4)
    D = DiscreteGaussianDistributionLatticeSampler(F^1, sigma)
    def decode(m):
        if p41 < m < p43:
            return 1
        return 0
    o = []
    for i in range(size):
        b = a*s + int(D()[0]) + HALF_P
        m = (b- s*a) % p
        o.append(decode(m))
    print("n: ", n, "p: ", p, "sigma: ", sigma, sum(o))

if __name__ == "__main__":
    p = [100 * i for i in range(1,10)]
    for i in p:
        test_lwe(256, next_prime(i), 3.3)

    n  = [2** i for i in range(3,10)]
    for i in n:
        test_lwe(i, next_prime(1000), 3.3)

    sigma =[ i * 3.3 for i in range(1, 10)]
    for i in sigma:
        test_lwe(512, next_prime(8000), i)