7
$\begingroup$

When it comes to lattice based cryptographic systems, all the literature talks about, good bases and bad bases.

How does one define what a good basis is and what a bad basis is?

$\endgroup$
5
$\begingroup$

A good basis are the set of "almost" orthogonal set of vectors which have small norms. They allow us to solve certain variants of closest vector problem $\mathsf{CVP}$ very efficiently (for example, use LLL). Usually, the private keys are "good" basis.

A bad basis are those basis which are in certain sense hardest instance to solve: if you solve any problem in the worst basis setting, you can solve the problem in almost all basis defining the same lattice. For very obvious reasons, bad basis are used as the public key.

If you want more concrete understanding, I refer you to read Miccianio's work Improving lattice based cryptosystems using the hermite normal form which first proposed HNF variant of basis to be used as the public key.

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