Skip to content

Latest commit

 

History

History
240 lines (178 loc) · 6.75 KB

tutorial.rst

File metadata and controls

240 lines (178 loc) · 6.75 KB
Raw
orphan:

Tutorial

Matrix generators

>>> from fpylll import IntegerMatrix, FPLLL
>>> FPLLL.set_random_seed(1337)
>>> A = IntegerMatrix(9, 10)
>>> A.randomize("intrel", bits=10)

Matrix A is a (random) knapsack type matrix. That is of the form [ {\bf a} | I_n], where {\bf a} is a column vector of dimension n, and I_n the n-dimensional identity matrix. Giving

>>> print(A)
[  50 1 0 0 0 0 0 0 0 0 ]
[ 556 0 1 0 0 0 0 0 0 0 ]
[   5 0 0 1 0 0 0 0 0 0 ]
[ 899 0 0 0 1 0 0 0 0 0 ]
[ 383 0 0 0 0 1 0 0 0 0 ]
[ 846 0 0 0 0 0 1 0 0 0 ]
[ 771 0 0 0 0 0 0 1 0 0 ]
[ 511 0 0 0 0 0 0 0 1 0 ]
[ 734 0 0 0 0 0 0 0 0 1 ]

Also, the following types of matrices are supported,

>>> from fpylll import FPLLL
>>> from copy import copy
>>> b = 10
>>> p = 521 # prime
>>> FPLLL.set_random_seed(1337)
>>> A = IntegerMatrix(6,6)
>>> B = copy(A)
>>> C = copy(A)
>>> D = copy(A)
>>> A.randomize("uniform", bits=b)
>>> B.randomize("ntrulike", bits=b, q=p)
>>> C.randomize("ntrulike2", bits=b, q=p)
>>> D.randomize("qary", bits=b, k=3)

For instance:

>>> print(D)
[ 1 0 0 858 790 620 ]
[ 0 1 0  72 832 133 ]
[ 0 0 1 263 121 724 ]
[ 0 0 0 877   0   0 ]
[ 0 0 0   0 877   0 ]
[ 0 0 0   0   0 877 ]

For a user defined matrix we use the method from_matrix:

>>> A = IntegerMatrix.from_matrix([[1,2,3,4],[30,4,4,5],[1,-2,3,4],[0,0,1,0]])

Gram-Schmidt tools

To compute the Gram-Schimdt form of the matrix {\bf A}, we use the GSO class:

>>> from fpylll import GSO
>>> A = IntegerMatrix.from_matrix([[1,2,3,4],[30,4,4,5],[1,-2,3,4],[0,0,1,0]])
>>> M = GSO.Mat(A)

To write a vector v as a linear combination of the GS-basis of RowSp(A):

>>> A = IntegerMatrix.from_matrix([[1,2,3,4],[30,4,4,5],[1,-2,3,4],[0,0,1,0]])
>>> M = GSO.Mat(A)
>>> _ = M.update_gso()
>>> v = (1,2,5,5)
>>> v_from_canonical = M.from_canonical(v)
>>> print(v_from_canonical) # doctest: +ELLIPSIS
(1.3333333333333..., -0.01301973960520..., 0.1949374454466..., 1.2521739130434...)
>>> v_back_to_canonical = tuple([int(round(v_)) for v_ in M.to_canonical(v_from_canonical)])
>>> print(v_back_to_canonical)
(1, 2, 5, 5)
>>> # the dimension of the GS-matrix :
... print(M.d)
4

We can then compute the inner product r_{i,j} = \langle {\bf b}_i, {\bf b}^{*}_j \rangle and the coefficient \mu_{i,j} = \langle {\bf b}_i, {\bf b}^*_j \rangle / ||{\bf b}^*_j||^2 (for any i,j, here i=2, j=3)

>>> i = 3; j = 2;
>>> print(M.get_r(i,j)) # doctest: +ELLIPSIS
0.810079798...
>>> print(M.get_mu(i,j))  # doctest: +ELLIPSIS
0.0584569876...

To compute the determinant of {\bf A}, compute either its \sqrt[n]{~} or its \log

>>> start_row = 0
>>> stop_row = -1
>>> root_det_A = M.get_root_det(start_row, stop_row)
>>> log_det_A = M.get_log_det(start_row, stop_row)
>>> print(root_det_A) # root_det_A = det(A)^(1/n) doctest: +ELLIPSIS
21.44761058...
>>> print(log_det_A) # log_det_A = exp(det(A)) in base e doctest: +ELLIPSIS
12.26245297...

Lattice reduction tools

To compute the LLL reduced matrix of {\bf A}

>>> from fpylll import LLL
>>> FPLLL.set_random_seed(1337)
>>> A.randomize("qary", bits=10, k=3)
>>> A_original = copy(A)
>>> A_lll = LLL.reduction(A)
>>> print(A_lll)
[  -3 21 -15 -23 ]
[ -10 70 -50 111 ]
[ -94 95  93  30 ]
[ 238 23  64 -52 ]

To test if a matrix is LLL-reduced

>>> print(LLL.is_reduced(A_original)) # a uniform matrix is usually not LLL-reduced
False
>>> print(LLL.is_reduced(A_lll))
True

For the BKZ reduction of {\bf A} with blocksize say 3 (without pruning),

>>> from fpylll import BKZ
>>> block_size = 3
>>> FPLLL.set_random_seed(1337)
>>> A.randomize("qary", bits=10, k=3)
>>> A_bkz = BKZ.reduction(A, BKZ.Param(block_size))
>>> print(A_bkz)
[  -3 21 -15 -23 ]
[ -10 70 -50 111 ]
[ -94 95  93  30 ]
[ 238 23  64 -52 ]

If we want to use pruning we can use the default pruning of fplll [GNR10].

>>> from fpylll import BKZ
>>> param = BKZ.Param(block_size = block_size, strategies = BKZ.DEFAULT_STRATEGY)
>>> bkz_reduced = BKZ.reduction(A, param)

SVP and CVP tools

To use Babai's Nearest Plane algorithm on the target vector v with basis {\bf A}, use it from the GSO tool detailed above

::
>>> FPLLL.set_random_seed(1337)
>>> A = LLL.reduction(IntegerMatrix.random(5, "qary", bits=10, k=3))
>>> M = GSO.Mat(A)
>>> _ = M.update_gso()
>>> w = M.babai([1, 17, -3, -75, 102])
>>> A.multiply_left(w)
(-6, 12, -19, -71, 98)

To compute the norm of a shortest vector of the lattice generated by the rows of the matrix {\bf A} we use the shortest_vector method of the SVP class, and measure the first row of the resulting matrix {\bf A}

>>> from fpylll import SVP
>>> SVP.shortest_vector(A)
(-3, 0, 21, -15, -23)
>>> print(A[0])
(-3, 0, 21, -15, -23)
>>> A[0].norm()
34.698703...

For the Closest Vector Problem, fplll (and so fpylll) uses enumeration:

>>> from fpylll import CVP
>>> A = IntegerMatrix.from_matrix([[1,2,3,4],[30,4,4,5],[1,-2,3,4]])
>>> t = (1, 2, 5, 5)
>>> v0 = CVP.closest_vector(A, t)
>>> v0
(1, 2, 3, 4)

In fact the following code was executed:

>>> from fpylll.fplll.gso import MatGSO
>>> from fpylll.fplll.enumeration import Enumeration
>>> M = MatGSO(A)
>>> _ = M.update_gso()
>>> E = Enumeration(M)
>>> _, v2 = E.enumerate(0, A.nrows, 5, 40, M.from_canonical(t))[0]
>>> v3 = IntegerMatrix.from_iterable(1, A.nrows, map(lambda x: int(x), v2))
>>> v1 = v3*A
>>> print(v1)
[ 1 2 3 4 ]

Further examples

More specific examples can be found in:

References

[MV]
  1. Micciancio, P. Voulgaris, Faster exponential time algorithms for the shortest vector problem. In: SODA 2010, pp. 1468--1480 (2010).
[GNR10]Nicolas Gama, Phong Q. Nguyen, and Oded Regev. 2010. Lattice enumeration using extreme pruning. In Proceedings of the 29th Annual international conference on Theory and Applications of Cryptographic Techniques (EUROCRYPT'10), Henri Gilbert (Ed.). Springer-Verlag, Berlin, Heidelberg, 257-278. DOI=http://dx.doi.org/10.1007/978-3-642-13190-5_13