LeakLWE2/framework/instance_gen.sage

from random import shuffle, randint

load("../framework/proba_utils.sage")
load("../framework/DBDD_predict_diag.sage")
load("../framework/DBDD_predict.sage")
load("../framework/DBDD.sage")


def initialize_from_LWE_instance(dbdd_class, n, q, m, D_e,
                                 D_s, diag=False, verbosity=1):
    """
    constructor that builds a DBDD instance from a LWE instance
    :n: (integer) size of the secret s
    :q: (integer) modulus
    :m: (integer) size of the error e
    :D_e: distribution of the error e (dictionnary form)
    :D_s: distribution of the secret s (dictionnary form)
    """
    if verbosity:
        logging("     Build DBDD from LWE     ", style="HEADER")
        logging("n=%3d \t m=%3d \t q=%d" % (n, m, q), style="VALUE")
    # define the mean and sigma of the instance
    mu_e, s_e = average_variance(D_e)
    mu_s, s_s = average_variance(D_s)
    mu = vec(m * [mu_e] + n * [mu_s] + [1])
    S = diagonal_matrix(m * [s_e] + n * [s_s] + [0])
    # draw matrix A and define the lattice
    A = matrix([[randint(0, q) for _ in range(n)] for _ in range(m)])
    B = build_LWE_lattice(-A, q)
    D = build_LWE_lattice(A/q, 1/q)
    # draw the secrets
    s = vec([draw_from_distribution(D_s) for _ in range(n)])
    e = vec([draw_from_distribution(D_e) for _ in range(m)])
    # compute the public value t and build a target
    b = (s * A.T + e) % q
    tar = concatenate([b, [0] * n])
    B = kannan_embedding(B, tar)
    D = kannan_embedding(D, concatenate([-b/q, [0] * n])).T
    u = concatenate([e, s, [1]])
    return A, b, dbdd_class(B, S, mu, u, verbosity=verbosity, D=D, Bvol=m*log(q))


def initialize_from_LWR_instance(dbdd_class, n, q, p, m, D_s, verbosity=1):
    if verbosity:
        logging("     Build DBDD from LWR     ", style="HEADER")
        logging("n=%3d \t m=%3d \t q=%d \t p=%d" % (n, m, q, p), style="VALUE")
    D_e = build_mod_switching_error_law(q, p)
    # draw matrix A and define the lattice
    A = matrix([[randint(0, q) for _ in range(n)] for _ in range(m)])
    s = vec([draw_from_distribution(D_s) for _ in range(n)])
    B = build_LWE_lattice(-A, q)
    b = q / p * ((p / q) * s * A.T).apply_map(lambda x: x.round(mode='down'))
    e = b - s * A.T
    tar = concatenate([b, [0] * n])
    B = kannan_embedding(B, tar)
    u = concatenate([e, s, [1]])
    # define the mean and sigma of the instance
    mu_e, s_e = average_variance(D_e)
    mu_s, s_s = average_variance(D_s)
    mu = vec(m * [mu_e] + n * [mu_s] + [1])
    S = diagonal_matrix(m * [s_e] + n * [s_s] + [0])
    return A, b, dbdd_class(B, S, mu, u, verbosity=verbosity)


def initialize_round5_instance(dbdd_class, n, q, p, h, m, D_e,
                               D_s, verbosity=1):
    if verbosity:
        logging("     Build DBDD from round5     ", style="HEADER")
        logging("n=%3d \t m=%3d \t q=%d \t p=%d" % (n, m, q, p), style="VALUE")
    # draw matrix A and define the lattice
    assert (h % 2 == 0), "Round5 requires 2 to divide h"
    A = matrix([[randint(0, q) for _ in range(n)] for _ in range(m)])
    s = h / 2 * [1] + h / 2 * [-1] + (n - h) * [0]
    shuffle(s)
    s = vec(s)
    B = build_LWE_lattice(-A, q)
    b = vec([q / p * (round((p / q) * ((s * A.T)[0][i] % q)) % p)
             for i in range(n)])
    e = vec([((- s * A.T)[0][i] + b[0][i]) % q
             if ((- s * A.T)[0][i] + b[0][i]) % q < q / 2
             else ((- s * A.T)[0][i] + b[0][i]) % q - q
             for i in range(n)])
    tar = concatenate([b, [0] * n])
    B = kannan_embedding(B, tar)
    u = concatenate([e, s, [1]])
    # define the mean and sigma of the instance
    mu_e, s_e = average_variance(D_e)
    mu_s, s_s = average_variance(D_s)
    mu = vec(m * [mu_e] + n * [mu_s] + [1])
    S = diagonal_matrix(m * [s_e] + n * [s_s] + [0])
    return A, b, dbdd_class(B, S, mu, u, verbosity=verbosity)


def initialize_LAC_instance(dbdd_class, n, q, m, D_e, D_s, verbosity=1):
    if verbosity:
        logging("     Build DBDD for LAC     ", style="HEADER")
        logging("n=%3d \t m=%3d \t q=%d" % (n, m, q), style="VALUE")
    # draw matrix A and define the lattice
    A = matrix([[randint(0, q) for _ in range(n)] for _ in range(m)])
    B = build_LWE_lattice(-A, q)
    assert (n % 4 == 0) and (m % 4 == 0), "LAC requires 4 to divide n and m"
    s = (n / 4) * [0, 1, 0, -1]
    shuffle(s)
    s = vec(s)
    e = (m / 4) * [0, 1, 0, -1]
    shuffle(e)
    e = vec(e)
    b = (s * A.T + e) % q
    tar = concatenate([b, [0] * n])
    B = kannan_embedding(B, tar)
    u = concatenate([e, s, [1]])
    # define the mean and sigma of the instance
    mu_e, s_e = average_variance(D_e)
    mu_s, s_s = average_variance(D_s)
    mu = vec(m * [mu_e] + n * [mu_s] + [1])
    S = diagonal_matrix(m * [s_e] + n * [s_s] + [0])
    return A, b, dbdd_class(B, S, mu, u, verbosity=verbosity)


def initialize_NTRU_instance(dbdd_class, n, q, m, D_e, D_s, verbosity=1):
    if verbosity:
        logging("     Build DBDD for NTRU HPS VERSION     ", style="HEADER")
        logging("n=%3d \t m=%3d \t q=%d" % (n, m, q), style="VALUE")

    assert (q % 16 == 0), "NTRU-HPS requires 16 to divide q"
    A = matrix([[randint(0, q) for _ in range(n)] for _ in range(m)])
    B = build_LWE_lattice(-A, q)
    if q / 8 - 2 <= 2 * n / 3:
        hamming_weight = (q / 16 - 1)
    else:
        hamming_weight = floor(n / 3)
    s = hamming_weight * [1] + hamming_weight * \
        [-1] + (n - 2 * hamming_weight) * [0]
    shuffle(s)
    s = vec(s)
    e = vec([draw_from_distribution(D_e) for _ in range(m)])
    b = (s * A.T + e) % q
    tar = concatenate([b, [0] * n])
    B = kannan_embedding(B, tar)
    u = concatenate([e, s, [1]])
    # define the mean and sigma of the instance
    mu_e, s_e = average_variance(D_e)
    mu_s, s_s = average_variance(D_s)
    mu = vec(m * [mu_e] + n * [mu_s] + [1])
    S = diagonal_matrix(m * [s_e] + n * [s_s] + [0])
    return A, b, dbdd_class(B, S, mu, u, verbosity=verbosity)


# def initialize_NTRU_prime_instance(dbdd_class, n, q, m, h, D_f,
#                                    D_g, verbosity=1):
#     if verbosity:
#         logging("     Build DBDD for NTRU PRIME VERSION     ", style="HEADER")
#         logging("n=%3d \t m=%3d \t q=%d \t h=%d" % (n, m, q, h), style="VALUE")

#     A = matrix([[randint(0, q) for _ in range(n)] for _ in range(m)])
#     B = build_LWE_lattice(-A, q)
#     e = h * [1] + (n - h) * [0]
#     shuffle(e)
#     e = [(-1) ** randint(0, 1) * e[i] for i in range(len(e))]
#     e = vec(e)
#     s = vec([draw_from_distribution(D_g) for _ in range(m)])
#     b = (s * A.T + e) % q
#     tar = concatenate([b, [0] * n])
#     B = kannan_embedding(B, tar)
#     u = concatenate([e, s, [1]])
#     # define the mean and sigma of the instance
#     mu_e, s_e = average_variance(D_g)
#     mu_s, s_s = average_variance(D_f)
#     mu = vec(m * [mu_e] + n * [mu_s] + [1])
#     S = diagonal_matrix(m * [s_e] + n * [s_s] + [0])
#     return A, b, dbdd_class(B, S, mu, u, verbosity=verbosity)