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$ 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 Gagnon Apr 5 '16 at 1:45

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:

  1. It helps computing a reduced basis (an equivalent basis with shorter vectors) using LLL or BKZ algorithm,
  2. 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$,
  3. It helps you finding the volume of the lattice by multiplying the norms of $\hat{\vec{b}}_i$'s rather than computing a determinant.
  4. It provides you upper and lower bounds on successive minimas and smoothing parameter of the lattice.
| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.