Hard Lattice Generator¶
This module contains lattice related functions relevant in cryptography.
Feel free to add more functionality.
AUTHORS:
Richard Lindner <rlindner@cdc.informatik.tu-darmstadt.de>
Michael Schneider <mischnei@cdc.informatik.tu-darmstadt.de>
- 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 usingsage.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 seedquotient– for the type'ideal', this determines the quotient polynomial. Ignored for all other typesdual– 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 formatlattice– set this flag if you want aFreeModule_submodule_with_basis_integerobject instead of an integer matrix representing the basis
OUTPUT:
Ba unique size-reduced triangular (primal: lower_left, dual: lower_right) basis of row vectors for the lattice in questionEXAMPLES:
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]
sage.crypto.gen_lattice(m=10, seed=42)
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]
sage.crypto.gen_lattice(type='random', n=1, m=10, q=11^4, seed=42)
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]
sage.crypto.gen_lattice(type='ideal', seed=42, quotient=x^4 - 1) # needs sage.symbolic
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]
R.<t> = PolynomialRing(ZZ) sage.crypto.gen_lattice(type='ideal', seed=1234, quotient=t^4 - 1) # needs sage.libs.pari
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]
sage.crypto.gen_lattice(type='cyclotomic', seed=42) # needs sage.libs.pari
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]
sage.crypto.gen_lattice(type='modular', m=10, seed=42, dual=True)
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
B_primal = sage.crypto.gen_lattice(m=10, q=11, seed=42) B_dual = sage.crypto.gen_lattice(m=10, q=11, seed=42, dual=True) B_dual_alt = transpose(11*B_primal.inverse()).change_ring(ZZ) B_dual_alt.hermite_form() == B_dual.hermite_form()