Hard Lattice Generator

This module contains lattice related functions relevant in cryptography.

Feel free to add more functionality.

AUTHORS:

sage.crypto.lattice.gen_lattice(type='modular', n=4, m=8, q=11, seed=None, quotient=None, dual=False, ntl=False, lattice=False)

This function generates different types of integral lattice bases of row vectors relevant in cryptography.

Randomness can be set either with seed, or by using sage.misc.randstate.set_random_seed().

INPUT:

  • type – one of the following strings

    • 'modular' (default) – A class of lattices for which asymptotic worst-case to average-case connections hold. For more refer to [Aj1996].

    • 'random' – Special case of modular (n=1). A dense class of lattice used for testing basis reduction algorithms proposed by Goldstein and Mayer [GM2002].

    • 'ideal' – Special case of modular. Allows for a more compact representation proposed by [LM2006].

    • 'cyclotomic' – Special case of ideal. Allows for efficient processing proposed by [LM2006].

  • n – Determinant size, primal:\(det(L) = q^n\), dual:\(det(L) = q^{m-n}\). For ideal lattices this is also the degree of the quotient polynomial.

  • m – Lattice dimension, \(L \subseteq Z^m\).

  • q – Coefficient size, \(q-Z^m \subseteq L\).

  • seed – Randomness seed.

  • quotient – For the type ideal, this determines the quotient polynomial. Ignored for all other types.

  • dual – Set this flag if you want a basis for \(q-dual(L)\), for example for Regev’s LWE bases [Reg2005].

  • ntl – Set this flag if you want the lattice basis in NTL readable format.

  • lattice – Set this flag if you want a FreeModule_submodule_with_basis_integer object instead of an integer matrix representing the basis.

OUTPUT: B a unique size-reduced triangular (primal: lower_left,

dual: lower_right) basis of row vectors for the lattice in question.

EXAMPLES:

Modular basis:

sage: sage.crypto.gen_lattice(m=10, seed=42)
[11  0  0  0  0  0  0  0  0  0]
[ 0 11  0  0  0  0  0  0  0  0]
[ 0  0 11  0  0  0  0  0  0  0]
[ 0  0  0 11  0  0  0  0  0  0]
[ 2  4  3  5  1  0  0  0  0  0]
[ 1 -5 -4  2  0  1  0  0  0  0]
[-4  3 -1  1  0  0  1  0  0  0]
[-2 -3 -4 -1  0  0  0  1  0  0]
[-5 -5  3  3  0  0  0  0  1  0]
[-4 -3  2 -5  0  0  0  0  0  1]

Random basis:

sage: sage.crypto.gen_lattice(type='random', n=1, m=10, q=11^4, seed=42)
[14641     0     0     0     0     0     0     0     0     0]
[  431     1     0     0     0     0     0     0     0     0]
[-4792     0     1     0     0     0     0     0     0     0]
[ 1015     0     0     1     0     0     0     0     0     0]
[-3086     0     0     0     1     0     0     0     0     0]
[-5378     0     0     0     0     1     0     0     0     0]
[ 4769     0     0     0     0     0     1     0     0     0]
[-1159     0     0     0     0     0     0     1     0     0]
[ 3082     0     0     0     0     0     0     0     1     0]
[-4580     0     0     0     0     0     0     0     0     1]

Ideal bases with quotient x^n-1, m=2*n are NTRU bases:

sage: sage.crypto.gen_lattice(type='ideal', seed=42, quotient=x^4-1)
[11  0  0  0  0  0  0  0]
[ 0 11  0  0  0  0  0  0]
[ 0  0 11  0  0  0  0  0]
[ 0  0  0 11  0  0  0  0]
[-2 -3 -3  4  1  0  0  0]
[ 4 -2 -3 -3  0  1  0  0]
[-3  4 -2 -3  0  0  1  0]
[-3 -3  4 -2  0  0  0  1]

Ideal bases also work with polynomials:

sage: R.<t> = PolynomialRing(ZZ)
sage: sage.crypto.gen_lattice(type='ideal', seed=1234, quotient=t^4-1)
[11  0  0  0  0  0  0  0]
[ 0 11  0  0  0  0  0  0]
[ 0  0 11  0  0  0  0  0]
[ 0  0  0 11  0  0  0  0]
[ 1  4 -3  3  1  0  0  0]
[ 3  1  4 -3  0  1  0  0]
[-3  3  1  4  0  0  1  0]
[ 4 -3  3  1  0  0  0  1]

Cyclotomic bases with n=2^k are SWIFFT bases:

sage: sage.crypto.gen_lattice(type='cyclotomic', seed=42)
[11  0  0  0  0  0  0  0]
[ 0 11  0  0  0  0  0  0]
[ 0  0 11  0  0  0  0  0]
[ 0  0  0 11  0  0  0  0]
[-2 -3 -3  4  1  0  0  0]
[-4 -2 -3 -3  0  1  0  0]
[ 3 -4 -2 -3  0  0  1  0]
[ 3  3 -4 -2  0  0  0  1]

Dual modular bases are related to Regev’s famous public-key encryption [Reg2005]:

sage: sage.crypto.gen_lattice(type='modular', m=10, seed=42, dual=True)
[ 0  0  0  0  0  0  0  0  0 11]
[ 0  0  0  0  0  0  0  0 11  0]
[ 0  0  0  0  0  0  0 11  0  0]
[ 0  0  0  0  0  0 11  0  0  0]
[ 0  0  0  0  0 11  0  0  0  0]
[ 0  0  0  0 11  0  0  0  0  0]
[ 0  0  0  1 -5 -2 -1  1 -3  5]
[ 0  0  1  0 -3  4  1  4 -3 -2]
[ 0  1  0  0 -4  5 -3  3  5  3]
[ 1  0  0  0 -2 -1  4  2  5  4]

Relation of primal and dual bases:

sage: B_primal=sage.crypto.gen_lattice(m=10, q=11, seed=42)
sage: B_dual=sage.crypto.gen_lattice(m=10, q=11, seed=42, dual=True)
sage: B_dual_alt=transpose(11*B_primal.inverse()).change_ring(ZZ)
sage: B_dual_alt.hermite_form() == B_dual.hermite_form()
True