Distribution of "good" and "bad" basis in lattice families?

One of the fundamental ideas behind lattice based cryptosystems is that there can be many equivalent basis for a single lattice.

Formally, let's define $$Lattice(B)$$ as the lattice generated by a basis B, and a function $$Family(\Lambda) = \{ B \ |\ B \in \mathbb{R}^{m \times n}, Lattice(B) =\Lambda \}$$.

Equivalent bases (i.e., bases that generate the same lattice) can be algebraically characterized as follows. Two bases $${\bf B}, {\bf B}' \in \Bbb R^{m \times n}$$ are equivalent if and only if there exists a unimodular matrix $${\bf U} \in \Bbb Z^{n \times n}$$ (i.e., an integral matrix with determinant $$\det({\bf U}) = \pm 1$$) such that $${\bf B}' = {\bf B} {\bf U}$$.

This seems to imply that given a fixed basis S, we can determine (with * implying unimodularity) $$Family(Lattice(S)) = \{ SU | U \in {Z^{n \times n}}^* \}$$.

Is there any literature or interesting structure characterizing these lattice families? I am interested in learning more because for many cryptographic applications, we pick basis from these families in which to solve the "closest lattice point" problem, and depending on which basis is chosen can have dramatic implications on the complexity of the solution.

Given a family, do we have any idea of the distribution "good" and "bad" basis over these families? Secondarily, are there any good resources for learning more about this general structure (the equivalence classes of basis matrices partitioned by lattice).

While this is an exceedingly broad question, I'll mention a few relevant things.

I am interested in learning more because for many cryptographic applications, we pick basis from these families in which to solve the "closest lattice point" problem, and depending on which basis is chosen can have dramatic implications on the complexity of the solution.

In standard lattice-based cryptography this isn't really true. Essentially every lattice-based hardness assumption I am aware of admits what are known as randomized self-reductions. At a high level, these say that worst-case complexity of a problem and the average-case complexity of the problem are roughly the same. Not all hardness assumptions admit such reductions --- the worst-case complexity of factoring is vastly different than the average-case complexity, which is why RSA has to be defined relative to semi-primes rather than arbitrary integers.

Moreover, most lattice-based hardness assumptions are not actually that straightforward to write down in this "good basis bad basis" paradigm. For example, (one form of) the most popular lattice-based hardness assumption is

Learning with Errors Problem: Let $$n,q, B\in\mathbb{N}$$. Let $$A\gets \mathsf{Unif}(\mathbb{Z}_q^{n\times n})$$, $$\vec s\gets \mathsf{Unif}(\mathbb{Z}_q^n)$$, and $$e\gets [-B, B]^n\cap\mathbb{Z}^n$$. The task is then to distinguish between samples of the form $$(A, A\vec s + \vec e)$$ and $$(A, \vec u)$$ where $$\vec u\gets \mathsf{Unif}(\mathbb{Z}_q^n)$$ is uniformly random.

To phrase this in terms of lattices, define the lattice $$\Lambda_q(A) := \{y\in\mathbb{Z}^n\mid \exists x\in\mathbb{Z}^n\text{ s.t. }y \equiv Ax\bmod q\}$$. Note that this is a quite natural object --- you get it by applying the "Construction A" to a uniformly random $$q$$-ary code. In terms of this lattice, the (decision) LWE problem asks you to distinguish between

1. uniformly random elements of space, and
2. points that are unnaturally close to this lattice.

The search version of the LWE problem is to recover $$\vec s$$ from $$(A, A\vec s + \vec e)$$. This is equivalent to solving a variant of the closest vector problem on this lattice (it is a "promise" variant of the problem).

This all being said, there is not an obvious good basis/bad basis perspective LWE-based encryption. One can phrase things in terms of knowledge of a specific short dual vector related to $$\vec s$$ (which often can be used as a terms of "good basis"), but this isn't the most natural presentation of things in my opinion, and is not the most common perspective taken in the literature.

• encryption based on the NTRU assumption,
• how lattice-based signatures are constructed, as well as
• the recently-introduced lattice isomorphism problem (LIP).

Of the three, the last matches your idea of being "stuck within a family, necessitating picking a good family" the best (the others just "pick a family randomly" essentially). There are a few papers about cryptography from LIP, but it's really quite a new assumption (I think two years old at the oldest --- the problem itself has existed for longer, but cryptographic constructions are recent). Relevant pointers are Bennett et al '21, Ducas and van Woerden, and papers that cite these papers. Of the two Ducas and van Woerden matches your perspective the most closely, so is perhaps the best to look into.

This answer doesn't really address the applicability of "good/bad" basis concepts to actual cryptographic problems; Mark's answer is much better for that. I just wanted to introduce some common definitions that would be helpful to see for for anyone exploring this subject for the first time.

One fundamental notion of "good basis" that arose very early on in the study of lattice basis reduction is being LLL-reduced. Intuitively, a basis $$(b_1,\ldots,b_n)$$ is LLL-reduced if (a) no $$b_j$$ can be made shorter by subtracting $$b_i$$ for any $$i, and (b) if consecutive basis vectors $$b_{k-1},b_k$$ are orthogonally projected away from $$\text{span}(b_1,\ldots,b_{k-2})$$, then the projections are in the classical fundamental domain for bases of $$\mathbb{R}^2$$. See Wikipedia for a rigorous definition.

There are a few reasons that this is a very nice notion of "good basis." First, given any lattice basis, an LLL-reduced basis for the same lattice can be computed in polynomial time. (Technical note: one actually must replace condition (b) with the requirement that the projections are "close" to the classical fundamental domain, as measured by a parameter $$\delta\leq 1$$. If $$\delta=1$$ then the projections are actually in the fundamental domain, but we only get polynomial time if $$\delta<1$$.) Second, the conditions (a) and (b) both mean that the basis vectors are "close to orthogonal." This makes LLL-reduced bases helpful in many applications. For instance, an LLL-reduced basis isn't enough to solve SVP, but it always returns a vector with length at most $$2^{n-1}$$ times the length of a shortest vector (in particular, an LLL-reduced basis gives you a lower bound on the length of the shortest vector - it's not obvious a priori that this can be done in polynomial time!). Third, every lattice has only finitely many LLL-reduced bases. So from the infinite family of all possible bases for a lattice, we can very quickly reduce to a finite subfamily of relatively nice bases. This makes it meaningful to ask questions about distributions/statistics of bases (e.g. what proportion of LLL-reduced bases satisfy some stronger property?), which seems to at least somewhat address the original poster's line of questions.

On the other hand, LLL-reduction is actually a fairly weak notion of "good;" in particular, it's often exponentially far away from solving any cryptographically hard lattice problems (for instance it can only get within an exponential factor of the shortest vector, as described above). Despite the number of LLL-reduced bases being finite, this number is typically enormous: we expect the number of LLL-reduced bases for a single lattice to be on the order of $$c^{n^3}$$ for some constant $$c>1$$ (see this Mathoverflow answer). A slight improvement over LLL reduction is HKZ reduction, but even HKZ-reduced bases are exponentially far from being able to solve the hard lattice problems. There are much stronger notions of "good" that are often sufficient to solve these problems (modulo the disclaimers mentioned in Mark's answer), but these magical bases are also much harder to find within the haystack of LLL- or HKZ-reduced bases.

One interesting paper discussing various quantitative measures of "goodness" of a basis, and exploring how bases are distributed with respect to these measures, is LLL on the Average by Nguyen and Stehlé.