setup.py

"""
Given parameter sets well designed for SIGNITC computes all the
global variables needed for various sub-algorithms.

TODO: making so many things global is ugly, we should be initialising 
      classes and passing things around. Will take a bit of refactoring
      so could be done when we try and include the optimisations for
      E/Fp2 and its twist
"""

# Sage imports
from sage.all import (
    proof,
    GF,
    EllipticCurve,
    QuaternionAlgebra,
    log,
    floor,
    ceil,
    var,
    gcd,
    Zmod,
    sqrt
)

# Local imports
from parameters import params

# Speedy and still (mostly) correct
proof.all(False)


def construct_fields_and_curves(p):
    """
    Given the prime, compute the finite
    fields and elliptic curves we need. Additionally
    we make `sqrt_minus_one` ∈ Fp4 to allow us to
    compute the twisting endomorphism.
    """
    # Construct finite fields
    x = var("x")
    Fp2 = GF(p**2, name="z2", modulus=x**2 + 1)
    Fp4 = Fp2.extension(2, name="z4")

    # √-1 in Fp4 is needed for automorphisms
    sqrt_minus_one = min(Fp4(-1).sqrt(all=True))  # Deterministic sqrt

    # Supersingular curve with End(E0) known
    E0 = EllipticCurve(Fp4, [1, 0])
    E0.set_order((p**2 - 1) ** 2, num_checks=0)

    return Fp2, Fp4, E0, sqrt_minus_one


def construct_quaternion_alg_and_order(p, q):
    """
    Compute the quaternion algebra and maximal
    order O0. We (currently) will always have 
    p ≡ 3 mod 4 and q = 1.
    """
    # Quaternion algebra things
    B = QuaternionAlgebra(-q, -p)
    i, j, k = B.gens()

    # TODO: derive ω from function depending on p
    # R[ω] is the distinguished quadratic subring 
    # of the algebra B_{p, ∞}.
    # When p ≡ 3 mod 4, we have ω = i
    assert p % 4 == 3, "Currently only p ≡ 3 mod 4 is supported"
    ω = i

    # Maximal order O, and a corresponding left ideal I
    O0 = B.quaternion_order([1, i, (i + j) / 2, (1 + k) / 2])

    return B, i, j, k, ω, O0
    

def construct_heuristics(p, l):
    """
    Various KLPT sub-functions require elements
    to be larger or smaller than bounds. Derive
    them here and pass them through as globals.
    """
    logp = log(p, l)
    represent_heuristic = ceil(logp / 4) - 4

    return represent_heuristic

"""
Given security parameters generate everything we need
"""
# Extract values from dictionary
#p, q, l, available_torsion, T, e, Δ, T_prime, Dc, f_step_max = params.values()
kappa, p, d_s, d_T, N_M = params.values()
q, l = 1, 2

# Construct fields and curves
Fp2, Fp4, E0, sqrt_minus_one = construct_fields_and_curves(p)

# Construct Quaternion algebra and maximal order
B, i, j, k, ω, O0 = construct_quaternion_alg_and_order(p, q)

# Construct some fixed constants for heuristics
# (Mainly for KLPT)
represent_heuristic = construct_heuristics(p, l)

#Construct message group
M = Zmod(N_M);


# Check algebra invariants
assert q == 1, "Only q = 1 is supported"
assert p % 4 == 3, "p % 4 ≡ 1 is not currently supported"

# Check soundness of torsion subgroups
assert (p**2 - 1) % d_s == 0, "d_s does not divide the available torsion in Fp4"
assert (p**2 - 1) % d_T == 0, "d_T does not divide the available torsion in Fp4"
assert gcd(d_s, d_T) == 1, "d_s and d_T are not coprime"
assert d_s**2 * d_T > represent_heuristic * p, "degree of endomorphism is probably too small for representation" #(or 2 * p or p)

# Check field and curves
assert E0.a_invariants() == (0, 0, 0, 1, 0), "Only E : y^2 = x^3 + x is supported"
assert E0.is_supersingular(), "E0 is not supersingular"
assert sqrt_minus_one**2 == -1, "sqrt_minus_one is not the square root of minus one!"

# Check Quaternion Algebra and Order
assert O0.discriminant() == B.discriminant(), "O0 is not a maximal order"

# Check security parameters
assert p >= l**kappa - 1, "p is too small"
assert d_s >= l**kappa, "d_s is too small"
assert log(N_M) <= l**(kappa / 2) / 12, "N_M is too large"