Navigation
- index
- modules |
- next |
- previous |
- Cryptography »
This module contains lattice related functions relevant in cryptography.
Feel free to add more functionality.
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() TrueTESTS:
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. |