Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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