# 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 [A96].
• 'random' - Special case of modular (n=1). A dense class of lattice used for testing basis reduction algorithms proposed by Goldstein and Mayer [GM02].
• 'ideal' - Special case of modular. Allows for a more compact representation proposed by [LM06].
• 'cyclotomic' - Special case of ideal. Allows for efficient processing proposed by [LM06].
• 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 - Coefficent 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 [R05].

• 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]
[ 4 -2 -3 -3  1  0  0  0]
[-3  4 -2 -3  0  1  0  0]
[-3 -3  4 -2  0  0  1  0]
[-2 -3 -3  4  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]
[ 4 -2 -3 -3  1  0  0  0]
[ 3  4 -2 -3  0  1  0  0]
[ 3  3  4 -2  0  0  1  0]
[ 2  3  3  4  0  0  0  1]

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

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


TESTS:

We are testing output format choices:

sage: sage.crypto.gen_lattice(m=10, q=11, 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]

sage: sage.crypto.gen_lattice(m=10, q=11, seed=42, ntl=True)
[
[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]
]

sage: sage.crypto.gen_lattice(m=10, q=11, seed=42, lattice=True)
Free module of degree 10 and rank 10 over Integer Ring
User basis matrix:
[ 0  0  1  1  0 -1 -1 -1  1  0]
[-1  1  0  1  0  1  1  0  1  1]
[-1  0  0  0 -1  1  1 -2  0  0]
[-1 -1  0  1  1  0  0  1  1 -1]
[ 1  0 -1  0  0  0 -2 -2  0  0]
[ 2 -1  0  0  1  0  1  0  0 -1]
[-1  1 -1  0  1 -1  1  0 -1 -2]
[ 0  0 -1  3  0  0  0 -1 -1 -1]
[ 0 -1  0 -1  2  0 -1  0  0  2]
[ 0  1  1  0  1  1 -2  1 -1 -2]


REFERENCES:

 [A96] Miklos Ajtai. Generating hard instances of lattice problems (extended abstract). STOC, pp. 99–108, ACM, 1996.
 [GM02] Daniel Goldstein and Andrew Mayer. On the equidistribution of Hecke points. Forum Mathematicum, 15:2, pp. 165–189, De Gruyter, 2003.
 [LM06] (1, 2) Vadim Lyubashevsky and Daniele Micciancio. Generalized compact knapsacks are collision resistant. ICALP, pp. 144–155, Springer, 2006.
 [R05] (1, 2) Oded Regev. On lattices, learning with errors, random linear codes, and cryptography. STOC, pp. 84–93, ACM, 2005.

#### Previous topic

S-Boxes and Their Algebraic Representations

#### Next topic

(Ring-)LWE oracle generators