I am researching lattice problems and some methods for solving them. I read some books that mentioned Babai's algorithm for finding the Closest Vector Problem (CVP) cannot be successful with a "bad" basis for a lattice.

Which begs a question: what is the worst basis for a lattice?

Is the HNF basis the worst basis for finding CVP in a lattice?

  • $\begingroup$ In one article Hermit Normal Form (HNF) basis of a lattice is used as a bad basis! $\endgroup$ – Mina Jan 26 '17 at 19:02
  • 1
    $\begingroup$ can you provide a link of the paper? $\endgroup$ – 111 Jan 27 '17 at 0:10
  • $\begingroup$ for instance Gentry's first FHE scheme proposes the HNF of a lattice as the public key, and the LLL reduction of this as the secret key. The link can be found in www.google.com $\endgroup$ – Tal-Botvinnik Mar 5 '17 at 21:18
  • $\begingroup$ @Tal-Botvinnik are you referring to the scheme proposed in Gentry's PhD thesis? Could you please tell us in which section the public and secret keys are defined in this way? Thank you! $\endgroup$ – Hilder Vitor Lima Pereira Sep 16 '19 at 13:00

Whether an algorithm succeeds or not for solving e.g. CVP depends on the quality of the basis, which for instance can be measured in terms of the sum of the norms of the basis vectors. Your question could therefore be interpreted as: does the HNF give you the basis of the lattice with the worst quality?

The answer has to be no to this. Suppose w.l.o.g. that the lattice lives in $\mathbb{Z}^n$, and the sum of the norms of the basis vectors of the HNF basis is $M$. Now clearly there can only be finitely many bases of the lattice for which this quality measure is less than $M$, as we can just enumerate all possible such bases. On the other hand, there are infinitely many bases for each lattice, and so there must be a basis with even worse quality. It all depends on how you define "quality", but for most sensible definitions there is no "worst quality" - you can always get a worse basis.

More concretely, given a basis matrix $B$, you can obtain another basis $B' = U \cdot B$ by multiplying $B$ with any unimodular matrix $U$. By taking a $U$ with huge entries, $B'$ will likely be a much worse basis than $B$.

  • 1
    $\begingroup$ True in the geometric sense indeed. But to complement: HNF is 'a' (but not 'the') worse basis in a complexity sense: it teaches nothing special about the lattice because it is an efficiently computable normal form. Other efficiently computable normal forms would also be `worse bases' in that sense. $\endgroup$ – LeoDucas Sep 16 '19 at 16:03
  • $\begingroup$ @LeoDucas I doubt we have some result like this, but anyway: Could it be a "worse basis" in the sense that applying a reduction to it produces worse basis than applying a reduction to other types of basis? $\endgroup$ – Hilder Vitor Lima Pereira Sep 17 '19 at 10:17
  • $\begingroup$ We do have a result like this, and this is why we are using HNF for public keys since 2001: cseweb.ucsd.edu/~daniele/papers/HNFcrypt.pdf . In particular: ``We formally prove that the new functions are at least as secure as the original ones, and possibly even better as the adversary gets less information in a strong information theoretical sense''. $\endgroup$ – LeoDucas Sep 18 '19 at 11:19

There are two algorithms for CVP due to Babai. Nearest plane algorithm and the rounding algorithm. The former, first applies LLL. Therefore independent of the input basis, the algorithm will output the same vector. So your claim is not true (since this algorithm does not depend on the representation of the basis).

The latter algorithm, is the rounding algorithm of Babai. In this case indeed, the output depends on the input basis.
Your question is, if I feed the algorithm with an HNF-matrix, the output is worst if I use a better basis? In general no.

To see this, say that you have a full rank integer lattice and a basis which form a diagonal matrix, with positive integers in diagonal entries. This matrix is HNF and so the basis is an HNF-basis. But then, the rounding algorithm solves the CVP problem, since the basis is orthogonal (this is exercise 18.2.5). So again your claim does not seem true. Maybe, in specific lattices the HNF-basis provide bad results for CVP. But, you must be more specific.


The answer to your question depends on the context. If you are thinking in basis reductions of a lattice $L$, the answer is not really. HNF$(L)$ is of course difficult to reduce, but there is no reason to believe that HNF$(L)\times U$ where $U$ is a random unimodular matrix is easier to reduce than HNF($L$) (if that was the case, then to reduce any HNF just multiply by a random unimodular and reduce that!)

*Note that a lattice is determined uniquely by its HNF, so my notation HNF(L) is not ambiguous.


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.