latticegen [-randseed [int | time]] options
latticegen(1) is a utility for generating matrices (rows form input lattice basis vectors).
Note that by default, the random bits always use the same seed, to ensure reproducibility. The seed may be changed with the option -randseed integer or by using the current time (in seconds) -randseed time. If you use this option, it must be the first one on the command line.
- r d b
generates a knapsack like matrix of dimension d × (d+1) and b bits (see, e.g. D. Stehle. Floating-Point LLL: Theoretical and Practical Aspects. The LLL Algorithm 2009: 179–213): the i-th vector starts with a random integer of bit-length <=b and the rest is the i-th canonical unit vector.
- s d b b2
generates a d × d matrix of a form similar to that is involved when trying to find rational approximations to reals with the same small denominator (see, e.g., A. K. Lenstra, H. W. Lenstra, Jr. and L. Lovasz. Factoring polynomials with rational coefficients. Math. Ann., 261: 515–534 (1982)): the first vector starts with a random integer of bit-length <=b2 and continues with d-1 independent integers of bit-lengths <=b; the i-th vector for i>1 is the i-th canonical unit vector scaled by a factor 2^b.
- u d b
generates a d × d matrix whose entries are independent integers of bit-lengths <=b.
- n d b c
generates an ntru-like matrix. If char is ‘b’, then it first samples an integer q of bit-length <=b, whereas if char is ‘q’, then it sets q to the provided value. Then it samples a uniform h in the ring Z_q[x]/(x^n-1). It finally returns the 2 × 2 block matrix [[I, Rot(h)], [0, q*I]], where each block is d × d, the first row of Rot(h) is the coefficient vector of h, and the i-th row of Rot(h) is the shift of the (i-1)-th (with last entry put back in first position), for all i>1. Warning: this does not produce a genuine ntru lattice with h a genuine public key (see J. Hoffstein, J. Pipher, J. H. Silverman. NTRU: A Ring-Based Public Key Cryptosystem. ANTS 1998: 267–288).
- N d b c
as the previous option, except that the constructed matrix is [[q*I, 0], [Rot(h), I]].
- q d k b c
generates a q-ary matrix. If char is ‘b’, then it first samples an integer q of bit-length <=b; if char is ‘p’, it does the same and updates q to the smallest (probabilistic) prime that is greater; if char is ‘q’, then it sets q to the provided value. It returns a 2 × 2 block matrix [[I, H], [0, q*I]], where H is (d-k) k and uniformly random modulo q. These bases correspond to the SIS/LWE q-ary lattices (see D. Micciancio and O. Regev. Post-Quantum Cryptography. Chapter of Lattice-based Cryptography, 147–191 (2009)). Goldstein-Mayer lattices correspond to k=1 and q prime (see D. Goldstein and A. Mayer. On the equidistribution of Hecke points. Forum Mathematicum, 15:165–189 (2003)).
- t d f
generates a d × d lower-triangular matrix B with B_ii = 2^(d-i+1)^f for all i, and B_ij is uniform between -B_jj/2 and B_jj/2 for all j<i.
- T d
also takes as input a d-dimensional vector vec read from a file. It generates a d × d lower-triangular matrix B with B_ii = vec[i] for all i and B_ij is uniform between -B_jj/2 and B_jj/2 for all j<i.
The generated matrix is printed in stdout.