# 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)[source]#

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]

>>> from sage.all import *
>>> sage.crypto.gen_lattice(m=Integer(10), seed=Integer(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]

>>> from sage.all import *
>>> sage.crypto.gen_lattice(type='random', n=Integer(1), m=Integer(10), q=Integer(11)**Integer(4), seed=Integer(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)          # needs sage.symbolic
[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]
[-3 -3 -2  4  1  0  0  0]
[ 4 -3 -3 -2  0  1  0  0]
[-2  4 -3 -3  0  0  1  0]
[-3 -2  4 -3  0  0  0  1]

>>> from sage.all import *
>>> sage.crypto.gen_lattice(type='ideal', seed=Integer(42), quotient=x**Integer(4) - Integer(1))          # needs sage.symbolic
[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]
[-3 -3 -2  4  1  0  0  0]
[ 4 -3 -3 -2  0  1  0  0]
[-2  4 -3 -3  0  0  1  0]
[-3 -2  4 -3  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)        # needs sage.libs.pari
[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]
[-3  4  1  4  1  0  0  0]
[ 4 -3  4  1  0  1  0  0]
[ 1  4 -3  4  0  0  1  0]
[ 4  1  4 -3  0  0  0  1]

>>> from sage.all import *
>>> R = PolynomialRing(ZZ, names=('t',)); (t,) = R._first_ngens(1)
>>> sage.crypto.gen_lattice(type='ideal', seed=Integer(1234), quotient=t**Integer(4) - Integer(1))        # needs sage.libs.pari
[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]
[-3  4  1  4  1  0  0  0]
[ 4 -3  4  1  0  1  0  0]
[ 1  4 -3  4  0  0  1  0]
[ 4  1  4 -3  0  0  0  1]


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

sage: sage.crypto.gen_lattice(type='cyclotomic', seed=42)                       # needs sage.libs.pari
[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]
[-3 -3 -2  4  1  0  0  0]
[-4 -3 -3 -2  0  1  0  0]
[ 2 -4 -3 -3  0  0  1  0]
[ 3  2 -4 -3  0  0  0  1]

>>> from sage.all import *
>>> sage.crypto.gen_lattice(type='cyclotomic', seed=Integer(42))                       # needs sage.libs.pari
[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]
[-3 -3 -2  4  1  0  0  0]
[-4 -3 -3 -2  0  1  0  0]
[ 2 -4 -3 -3  0  0  1  0]
[ 3  2 -4 -3  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]

>>> from sage.all import *
>>> sage.crypto.gen_lattice(type='modular', m=Integer(10), seed=Integer(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

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