6
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ In one article Hermit Normal Form (HNF) basis of a lattice is used as a bad basis! $\endgroup$
    – Mina
    Jan 26, 2017 at 19:02
  • 1
    $\begingroup$ can you provide a link of the paper? $\endgroup$
    – 111
    Jan 27, 2017 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$ Mar 5, 2017 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$ Sep 16, 2019 at 13:00

3 Answers 3

3
$\begingroup$

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$.

$\endgroup$
3
  • 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, 2019 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$ Sep 17, 2019 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, 2019 at 11:19
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.