Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for lecture 1, mathematical background.
In this note, I write down proofs missing from his lecture note as well as my questions. Due to the nature of personal notes, I will not formally put references.
Definition 2.1. An dimensional lattice is a discrete additive subgroup of
Proposition. Let be a subgroup of then TFAE:
- For all there exists s.t.
- There exists s.t.
- There exists s.t. for all it holds that
Proof. We prove this by cycling around.
- 3 ⟹ 1 ⟹ 2. Trivial.
- 2 ⟹ 3. Take the guaranteed by (2) as that for (3). For all s.t. we have since is a subgroup and By the choice of and (2), it follows that
Definition 2.3. The rank of lattice is
Proposition. If there exists s.t.
Proof. This will be trivial once we show that a lattice always has a basis.
Definition 2.4. A basis of lattice is a linearly independent subset of it such that it generates (as an abelian group).
Proposition. Any (finite-dimensional) lattice has a basis.
Proof. Clearly is torsion-free, so by the fundamental theorem of finitely generated abelian groups, we only need to show that is finitely generated. Since it has a maximal linearly independent subset For all there exists real coefficients s.t. Let then and This means the set generates We’re done because this is a finite set — in particular, it contains at most points, where is the positive number guaranteed by (3) of a previous proposition.
Corollary 2.7. (Checking equivalence of lattices generated by two bases, generalized to rank-deficient case.) To check whether generate the same lattice:
- Check whether This ensures
- Find an isometry (isomorphism between Euclidean spaces) and compute Note that the can be found using Gram–Schmidt orthonormalisation (QR decomposition).
- Check whether is unimodular.
Definition 2.8. (Fundamental region, generalized to rank-deficient case.) A fundamental region of lattice is one such that it has exactly one representative for each coset in
Definition 2.9. The fundamental parallelepiped of a lattice basis is Sometimes, one might opt for an alternative definition
Example. Voronoi cell of is the set It is not a fundamental region, but its closure is the closure of a fundamental region.
Definition 2.11. The volume (determinant) of lattice is the volume of any of its fundamental region.
Claim 2.12. (Determinant from basis, generalized to rank-deficient case.) If has basis it has determinant
Question. There need to be some extra conditions posed on the fundamental region to make the volume well-defined. Consider the lattice which has a fundamental region Here, is a Vitali set containing 0. This fundamental region is not measurable, so it makes no sense to talk about its volume. Another interesting question: is there a Banach–Tarski paradox for lattice fundamental regions?
The simplest way to fix this is to consider a region that contains at most one representative of each coset and whose closure contains at least one representative of each coset. This ensures the volume is well-defined (though I don’t know how to prove this).
Definition 2.13. The minimum distance of lattice is
I haven’t carefully investigated Minkowski’s results — I will update if I find a question or comment.