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)¶ 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 [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:
, dual:
.
For ideal lattices this is also the degree of the quotient polynomial.m– Lattice dimension,
.q– Coefficient size,
.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
, 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 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 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]
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] [ 4 1 4 -3 1 0 0 0] [-3 4 1 4 0 1 0 0] [ 4 -3 4 1 0 0 1 0] [ 1 4 -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:
Test some bad quotient polynomials:
sage: sage.crypto.gen_lattice(type='ideal', seed=1234, quotient=cos(x)) Traceback (most recent call last): ... TypeError: unable to convert cos(x) to an integer sage: sage.crypto.gen_lattice(type='ideal', seed=1234, quotient=x^23-1) Traceback (most recent call last): ... ValueError: ideal basis requires n = quotient.degree() sage: R.<u,v> = ZZ[] sage: sage.crypto.gen_lattice(type='ideal', seed=1234, quotient=u+v) Traceback (most recent call last): ... TypeError: quotient should be a univariate polynomial
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.