In lattice-based cryptography, given the basis of the lattice we compute the orthogonal vectors using Gram-Schmidt Orthogonalization process. What is the use of orthogonal vectors in lattices?
$\begingroup$
$\endgroup$
1
-
$\begingroup$ From my math background : if a basis is composed of two vectors that are almost parallel, say (1,0) and (1,epsilon) then the vector (0,1) has coordinates (-1/epsilon, 1/epsilon) which can be arbitrarily big. Clearly, this is inefficient. $\endgroup$– Jean-François GagnonApr 5, 2016 at 1:45
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
Let $\left\{\vec{b}_1,\ldots,\vec{b}_n\right\}$ ba a lattice basis and $\left\{\hat{\vec{b}}_1,\ldots,\hat{\vec{b}}_n\right\}$ be its Gram-Schmidt orthogonolization. Here are some reasons:
- It helps computing a reduced basis (an equivalent basis with shorter vectors) using LLL or BKZ algorithm,
- The span of $\{\vec{b}_1,\ldots,\vec{b}_i\}$ is equal to the span of $\{\hat{\vec{b}}_1,\ldots,\hat{\vec{b}}_i\}$ for $1\leq i\leq n$,
- It helps you finding the volume of the lattice by multiplying the norms of $\hat{\vec{b}}_i$'s rather than computing a determinant.
- It provides you upper and lower bounds on successive minimas and smoothing parameter of the lattice.