Cryptographic Lattice Geometry Note 1

Posted on In Disqus:

All info comes from this note and this course.

This note will be mainly focusing on lattice parallelepiped and Minkowski’s Theorem.

Parallelepiped

Let $\mathcal{L} = \mathcal{L}(\pmb{B}) \subseteq \mathbb{R}^n$ for some basis matrix $\pmb{B} \in \mathbb{R}^{n \times k}$. Define fundamental parallelepiped of $\mathcal{L}$ with respect to $\pmb{B}$ as $\mathcal{P}(\pmb{B}) = \pmb{B}\lbrack 0, 1)^k$.

Fundamental Parallelepiped

A fundamental question is: given linear individual vectors $\pmb{b}_1,\dots,\pmb{b}_n \in \mathcal{L}$, how can we tell if they form a basis of $\mathcal{L}$?

Observing that basic parallelepiped generated by vectors should not contain any lattice point, except the origin.

Then, let $\mathcal{L}$ be a lattice of rank $n$, let $\pmb{b}_1,\dots,\pmb{b}_n\in \mathcal{L}$ be $n$ linearly independent lattice vectors. Then $\pmb{b}_1,\dots,\pmb{b}_n$ form a basis of $\mathcal{L}$ if and only if $\mathcal{P}(\pmb{b}_1,\dots,\pmb{b}_n) \cap \mathcal{L} = \lbrace \pmb{0}\rbrace$.

Assuming that $\pmb{b}_1,\dots,\pmb{b}_n$ form a basis for $\mathcal{L}$, then $\mathcal{L}$ is the linear span of $\pmb{b}_1,\dots,\pmb{b}_n$. Since $\mathcal{P}(\pmb{b}_1,\dots,\pmb{b}_n) = \sum\limits_{i = 1}^n \pmb{b}_i\lbrack 0, 1)$, then the only intersection is $\pmb{0}$.

Suppose $\mathcal{P}(\pmb{b}_1,\dots,\pmb{b}_n) \cap \mathcal{L} = \lbrace \pmb{0}\rbrace$, by $\mathcal{L}$ being rank $n$ and $\pmb{b}_1,\dots,\pmb{b}_n$ being linearly independent, we can represent $\pmb{x} \in \mathcal{L}$ by $\pmb{x} = \sum\limits^n_{i=1}k_i\pmb{b}_i$ with $k_i \in \mathbb{R}$.

By closed additional operation, we have $\delta = \pmb{x} - \sum\limits^n_{i = 1} \lfloor k_i \rfloor \pmb{b}_i = \sum\limits^n_{i = 1} (k_i - \lfloor k_i \rfloor) \pmb{b}_i\in \mathcal{L}$. By definition, $\delta = \pmb{0}$. Thus $k_i \in \mathbb{Z}$ and $\pmb{b}_1,\dots,\pmb{b}_n$ forms a basis for $\mathcal{L}$.

Determinant

Let $\mathcal{L} = \mathcal{\pmb{B}} \subseteq \mathbb{R}^n$ for some $\pmb{B}\in \mathbb{R}^{n \times k}$. Define the determinant of $\mathcal{L}$ be $\det(\mathcal{L}) = \sqrt{\det(\pmb{B}^\top\pmb{B})}$.

Such definition will have: $\det(\mathcal{L}(\pmb{B})) = \det(\mathcal{L}(\pmb{BU}))$ for some $\pmb{U}\in \mathbb{R}^{k \times k}$ unimodular matrix. By
$$
\begin{aligned}
\det((\pmb{BU})^\top \pmb{BU}) &= \det(\pmb{U}^\top \pmb{B}^\top \pmb{BU})\newline
&= \det(U)^2 \det(\pmb{B}^\top\pmb{B})\newline
&= \det(\pmb{B}^\top\pmb{B})
\end{aligned}
$$
the feature is satisfied. In the case when $k = n$, $\pmb{B}$ is a square matrix, $\det(\mathcal{L}) = |\det(\pmb{B})|$.

Also let $\pmb{B} = (\pmb{b}_1,\dots,\pmb{b}_n)$ denotes a basis for a lattice $\mathcal{L}$. For $\mathcal{P}(\pmb{B})$:

  1. $\text{vol}_k(\mathcal{P}(\pmb{B})) = \det(\mathcal{L})$. (see this link)
  2. $\forall \pmb{x} \in \text{span}(\mathcal{L})$, $\exists \pmb{y}$ unique that $\pmb{y}\in\mathcal{L}$ such that $\pmb{x} \in \pmb{y} + \mathcal{P}(\pmb{B})$. In particular, $\text{span}(\mathcal{L}) = \mathcal{L} + \mathcal{P}(\pmb{B})$, meaning $\mathcal{P}(\pmb{B})$ tiles space with respect to $\mathcal{L}$.

Let $\pmb{x} \in \text{span}(\mathcal{L})$, where $\pmb{x} = \sum\limits^{k}_{i = 1}a_i\pmb{b}_i$. We define $\pmb{x} \pmod{\mathcal{P}(\pmb{B})}$ to the vector $\sum\limits^k_{i = 1} (a_i - \lfloor a_i \rfloor)\pmb{b}_i \in \mathcal{P}(\pmb{B})$.

Packing, Covering and Tilting

Let $\mathcal{L}\subseteq \mathbb{R}^n$ be a lattice and let $F \subseteq \text{span}(\mathcal{L})$ be a measurable set (with respect to Lesbegue measure on $\text{span}(\mathcal{L})$). We define $F$ to be

  1. $\mathcal{L}$-packing if $\forall \pmb{x},\pmb{y} \in \mathcal{L}, \pmb{x}\neq\pmb{y}, (\pmb{x} + F) \cap (\pmb{y} + F) = \varnothing$.
  2. $\mathcal{L}$-covering if $\mathcal{L} + F = \text{span}(\mathcal{L})$.
  3. $\mathcal{L}$-tilting (or a fundamental domain of $\mathcal{L}$) if $F$ is both $\mathcal{L}$-packing and $\mathcal{L}$-covering.

$F \subseteq \text{span}(\mathcal{L})$ is $\mathcal{L}$-packing/covering/tilting if and only if $\forall \pmb{x} \in \text{span}(\mathcal{L}), |(\mathcal{L} + \pmb{x}) \cap F |\ \ (\le,\ge,=)\ \ 1$.

Prove the $\mathcal{L}$-packing case here. Assuming $F$ is $\mathcal{L}$-packing and take $\pmb{x} \in \text{span}(\mathcal{L})$.

If $|(\mathcal{L} + \pmb{x}) \cap F| > 1$, we take $\pmb{w_0},\pmb{w_1} \in F$ such that $\pmb{w_0},\pmb{w_1} \in \mathcal{L} + \pmb{x}$.

WLOG we let $\pmb{w_0} \in F = F + \pmb{0}$ and $\pmb{w_0} = \pmb{w_1} + (\pmb{w_0} - \pmb{w_1}) \in F + (\pmb{w_0} - \pmb{w_1})$. Thus $(F + \pmb{0}) \cap (F ＋ (\pmb{w_0} - \pmb{w_1})) = \lbrace \pmb{w_0}\rbrace$. Contradiction.

Also, $F \subseteq \text{span}(\mathcal{L})$ is non-empty and $\mathcal{L}$-packing $\Leftrightarrow (F - F)\cap\mathcal{L} = \lbrace \pmb{0}\rbrace$.

Suppose $\exists \pmb{x} \in \text{span}(\mathcal{L})$ s.t. $|(\mathcal{L} + \pmb{x}) \cap F| > 1$, which means $\exists \pmb{w_0}\ne\pmb{w_1} \in F$ that $\pmb{w_0 - w_1} \in \mathcal{L}\backslash\lbrace \pmb{0}\rbrace$, i.e., $(F - F) \cap\mathcal{L} \backslash \lbrace \pmb{0}\rbrace \neq \varnothing$.

Therefore $F$ is $\mathcal{L}$-packing if and only if $(F - F)\cap\mathcal{L} = \lbrace \pmb{0}\rbrace$.

Let $\mathcal{L}\subseteq \mathbb{R}^n$ be a $k\ge 1$ dimensional lattice and let $W = \text{span}(\mathcal{L})$. Let $F \subseteq W$ be measurable set and $g:\text{span}(\mathcal{L})\to \mathbb{R}_+$ be a measurable function w.r.t $k$-dimensional Lesbegue measure on $W$.

If $F$ is $\mathcal{L}$-packing/covering/tilting we have that
$$
\int_F \sum_{\pmb{y}\in\mathcal{L}} g(\pmb{y + x})\text{dvol}_k(\pmb{x})\phantom{‘’’’’’}(\le,\ge,=)\phantom{‘’’’’’}\int_W g(\pmb{x})\text{dvol}_k(\pmb{x})
$$

By choosing an orthonormal basis for $W$ and applying a change of coordinates, we might assume that $W = \mathbb{R}^n$ and $k=n$.

Since $g \ge 0$ and measurable, we have that $m(A) = \int_Ag(\pmb{x})d\pmb{x}$ for $A \subseteq \mathbb{R}^n$ measurable, defines a measure on $\mathbb{R}^n$.

Let $1_{\pmb{y}+F},\pmb{y}\in\mathcal{L}$ denote the indicator function of $\pmb{y}+F$ measurable.

Since $\mathcal{L}$ is countable, we have
$$
\begin{aligned}
\sum_{y\in\mathcal{L}}m(\pmb{y}+F) &= \sum_{y\in\mathcal{L}} \int_{\mathbb{R}^n} 1_{\pmb{y}+F}(\pmb{x}) g(\pmb{x})\text{d}\pmb{x}\newline
&=\sum_{y\in\mathcal{L}} \int_{\pmb{x} \in \pmb{y}+F \subseteq \mathbb{R}^n} g(\pmb{x})\text{d}\pmb{x}\newline
&= \sum_{y\in\mathcal{L}} \int_{\pmb{x} \in F} g(\pmb{x}+\pmb{y})\text{d}\pmb{x}\newline
&= \int_{\pmb{x} \in F} \sum_{y\in\mathcal{L}} g(\pmb{x}+\pmb{y})\text{d}\pmb{x}
\end{aligned}
$$
If $F$ is $\mathcal{L}$-packing then collections of sets $\pmb{y} + F \subseteq \mathbb{R}^n$ for $\pmb{y}\in\mathcal{L}$ are all disjoint. Thus we have
$$
\int_{\mathcal{R}^n}g(\pmb{x})\text{d}\pmb{x}=m(\mathbb{R}^n) \ge m(\mathcal{L}+F) = \sum_{\pmb{y}\in\mathcal{L}}m(\pmb{y}+F) = \int_{\pmb{x} \in F} \sum_{y\in\mathcal{L}} g(\pmb{x}+\pmb{y})\text{d}\pmb{x}
$$
If $F$ is $\mathcal{L}$-covering then the order of operators are reversed since $\mathbb{R}^n \subseteq \mathcal{L}+F$.

Also by previous, we have
$$
\text{vol}_n(F) = \int_{\mathcal{R}^n} 1_F(\pmb{x})\text{d}\pmb{x} =\sum_{\pmb{y}\in\mathcal{L}} \int_{B\lbrack 0,1)^n}1_F(\pmb{x} + \pmb{y})\text{d}\pmb{x} = \int_{B\lbrack 0,1)^n}|(\mathcal{L}+\pmb{x}) \cap F|\text{d}\pmb{x}
$$
If $\mathcal{L}$-packing/covering/tilting, then by $\forall \pmb{x} \in \text{span}(\mathcal{L}), |(\mathcal{L} + \pmb{x}) \cap F |\ \ (\le,\ge,=)\ \ 1$, we have
$$
\text{vol}_n(F) = \int_{B\lbrack 0,1)^n}|(\mathcal{L}+\pmb{x}) \cap F|\text{d}\pmb{x}\phantom{‘’’’’’}(\le,\ge,=)\phantom{‘’’’’’}\int_{B\lbrack 0,1)^n}1\text{d}\pmb{x} = \text{vol}_n(\pmb{B}\lbrack0,1)^n) = \det(\mathcal{L})
$$

Sublattice and Quotient Group

For lattice $\mathcal{L}\subseteq\mathbb{R}^n$ of rank $k$, we define quotient group $\text{span}(\mathcal{L})/\mathcal{L} = \lbrace \pmb{x} + \mathcal{L} : \pmb{x} \in \text{span}(\mathcal{L})\rbrace$.

Noticing that $\pmb{x} + \mathcal{L} = \pmb{y} + \mathcal{L} \Leftrightarrow \pmb{x-y}\in\mathcal{L}$. For convenience we denote $\pmb{x} \equiv \pmb{y} \pmod{\mathcal{L}}$ if $\pmb{x}-\pmb{y}\in\mathcal{L}$.

Then $\text{span}(\mathcal{L})/\mathcal{L} = \lbrace \pmb{x} + \mathcal{L} : \pmb{x} \in \text{span}(\mathcal{L})\rbrace$ forms a group under addition, where $(\pmb{x} + \mathcal{L}) + (\pmb{y}+\mathcal{L}) = \pmb{x} + \pmb{y}+ \mathcal{L}$.

For a lattice $\mathcal{L}\subseteq\mathbb{R}^n$, a lattice $\mathcal{L}’ \subseteq \mathcal{L}$ is called a sublattice $\mathcal{L}’$.

An example of $\mathcal{L}’ = \lbrace (x, y) \in \mathbb{Z}^2: x + y \equiv 0 \pmod 2\rbrace \subseteq \mathbb{Z}^2$.

Quotient group $\mathcal{L}/\mathcal{L}’ = \lbrace \pmb{x} + \mathcal{L}’ : \pmb{x} \in \mathcal{L}\rbrace$ is defined. $|\mathcal{L}/\mathcal{L}’|$ is generally finite, so long as $\text{span}(\mathcal{L}) = \text{span}(\mathcal{L}’)$.

Let $\mathcal{L}\subseteq\mathbb{R}^n$ be a $k \ge 1$ dimensional lattice. The following holds:

  1. $\text{span}(\mathcal{L})/\mathcal{L} \cong \mathbb{R}^k/\mathbb{Z}^k$.
  2. $m \in \mathbb{N}, \mathcal{L}/m\mathcal{L}\cong \mathbb{Z}^k_m$ and $|\mathcal{L}/m\mathcal{L}|=m^k$. Furthermore, $\det(m\mathcal{L}) = m^k\det(\mathcal{L})$.

Let $(\pmb{b}_1,\dots,\pmb{b}_k)$ denote any basis for $\mathcal{L}$. $\pmb{x} \in \mathcal{L}$ can be represented in $\sum\limits^k_{i=1}a_i\pmb{b}_i$ and form $T:\text{span}(\mathcal{L}) \to \mathbb{R}^k$ by taking $\pmb{x}$ and outputting $(a_1,\dots,a_k)$.

Given that $T$ is bijective and linear, $T(\text{span}(\mathcal{L})) = \mathbb{R}^k$ and $T(\mathcal{L})= \mathbb{Z}^k$, we have that $\text{span}(\mathcal{L}) / \mathcal{L} \cong \mathbb{R}^k / \mathbb{Z}^k$.

Also, we have $\mathcal{L}(m\pmb{b}_1,\dots,m\pmb{b}_k) = m\mathcal{L}(\pmb{b}_1,\dots,\pmb{b}_k) = m\mathcal{L}$, and hence $(m\pmb{b}_1,\dots,m\pmb{b}_k)$ is a basis for $m\mathcal{L}$.

By definition, we have $\det(m\mathcal{L}) = m^k\det(\mathcal{L})$.

Let $\tau : \mathcal{L}\to \mathbb{Z}^k_m$ denote the map which sends $\pmb{x} = \sum\limits^k_{i = 1}a_i\pmb{b}_i \in \mathcal{L}$ to $(a_1,\dots,a_k) \pmod m$.

The property of $\tau$ addition is on modular $m$, making $\forall\pmb{x},\pmb{y}\in\mathcal{L}, \tau(\pmb{x}+\pmb{y}) = \tau(\pmb{x}) +\tau(\pmb{y})$. Thus $\tau$ forms a homomorphism from $\mathcal{L}$ to $\mathbb{Z}^k_m$.

$\tau$ is surjective onto $\mathbb{Z}^k_m$ since $\tau(\pmb{B}\lbrace 0,\dots,m-1\rbrace^k) = \mathbb{Z}^k_m$.

Also, $\tau(\pmb{x}) \equiv 0^k \Leftrightarrow a_i \equiv 0\ \forall a_i \in \mathbb{Z}$. Thus $m\mathcal{L} = \ker(\tau)$. Thus $\mathcal{L}/m\mathcal{L}\cong \mathbb{Z}^k_m$ by first isomorphism theorem for groups.

Let $\mathcal{L}\subseteq \mathbb{R}^n$ be a $k\ge 1$ dimensional lattice, and $\mathcal{L}’\subseteq L$ being a sublattice. The following holds:

  1. $|\mathcal{L}/\mathcal{L}’| < \infty \Leftrightarrow \text{span}(\mathcal{L}) = \text{span}(\mathcal{L}’)$.
  2. Assuming $|\mathcal{L}/\mathcal{L}’| < \infty$, then $|\mathcal{L}/\mathcal{L}’| = |\mathcal{L}\cap\mathcal{P}(\pmb{B}’)| = \det(\mathcal{L’}) /\det(\mathcal{L})$, for any basis $\pmb{B}’$ for $\mathcal{L}’$.

Suppose $|\mathcal{L}/\mathcal{L}’| < \infty$, then suppose $\pmb{x} \in \mathcal{L}$ that $\exists k \in \mathbb{Z}\backslash\lbrace 0\rbrace$ that $k\pmb{x} \notin \mathcal{L}’$, i.e., $k\pmb{x} \not\equiv \pmb{0} \pmod {\mathcal{L}’}$.

Then we can see that $|\mathcal{L}/\mathcal{L}’| = |\mathbb{Z}\backslash\lbrace 0\rbrace| = \infty$. Contradiction. Thus $\forall \pmb{x} \in \mathcal{L}, \pmb{x} \in \text{span}(\mathcal{L}’)$. Thus $\text{span}(\mathcal{L}) = \text{span}(\mathcal{L}’)$.

$|\mathcal{L}/\mathcal{L}’| = |\mathcal{L}\cap\mathcal{P}(\pmb{B}’)|$ follows directly from the previous proof.

By previous we have that
$$
\begin{aligned}
\det(\mathcal{L}’) &= \text{vol}_k(\mathcal{P}(\pmb{B}’)) = \int_{\text{span}(\pmb{B}’)} 1_{\mathcal{P}(\pmb{B}’)}(\pmb{x})\text{dvol}_k(\pmb{x})\newline
&= \int_{\mathcal{P}(\pmb{B})} \sum_{\pmb{y}\in\mathcal{L}} 1_{\mathcal{P}(\pmb{B}’)}(\pmb{y}+\pmb{x})\text{dvol}_k(\pmb{x})\newline
&= \int_{\mathcal{P}(\pmb{B})} |\mathcal{P}(\pmb{B}’) \cap (\mathcal{L} + \pmb{x})| \text{dvol}_k(\pmb{x})
\end{aligned}
$$
We let $A = \mathcal{P}(\pmb{B}’)\cap \mathcal{L}$, then we see that $\mathcal{L}’ + A = \mathcal{L}$ and $|A| = |\mathcal{L}/\mathcal{L}’|$.

Then we have $|\mathcal{P}(\pmb{B}’) \cap (\mathcal{L} + \pmb{x})| = |\mathcal{P}(\pmb{B}’) \cap (\mathcal{L}’ + A + \pmb{x})|$. Therefore
$$
\begin{aligned}
\det(\mathcal{L}’) &= \int_{\mathcal{P}(\pmb{B})} |\mathcal{P}(\pmb{B}’) \cap (\mathcal{L} + \pmb{x})| \text{dvol}_k(\pmb{x}) = \int_{\mathcal{P}(\pmb{B})} |\mathcal{P}(\pmb{B}’) \cap (\mathcal{L}’ + A + \pmb{x})| \text{dvol}_k(\pmb{x})\newline
&= |\mathcal{L}/\mathcal{L}’| \int_{\mathcal{P}(\pmb{B})}\text{dvol}_k(\pmb{x}) = |\mathcal{L}/\mathcal{L}’| \text{vol}_k(\mathcal{P}(\pmb{B})) = |\mathcal{L}/\mathcal{L}’| \det(\mathcal{L})
\end{aligned}
$$

Lattice Geometry

First check previous note on successive minima and $\lambda_i$.

Covering Radius

Distance function is defined as $\mu(t,\mathcal{L}) = \min\limits_{x \in \mathcal{L}} \lVert t - x \rVert$.

The covering radius is defined as $\mu(\mathcal{L}) = \max\limits_{t \in \text{span}(\mathcal{L})} \mu(t, \mathcal{L})$.

We have a very rough conclusion that if $t \in x + \mathcal{P}(\pmb{B})$, then $\lVert t - x \rVert \le \sum \lVert v_i\rVert \le n\lambda_n$. Thus $\mu(\mathcal{L}) \le n \lambda_n$.

Let $\mathcal{L}\subseteq \mathbb{R}^n$ be a $k \ge 1$ dimensional lattice. There exists linearly independent vectors $\pmb{y}_1,\dots,\pmb{y}_k\in\mathcal{L}$ such that $\lVert\pmb{y}_i\rVert = \lambda_i$.

Let $\pmb{b}_1,\dots,\pmb{b}_k$ be the basis of $\mathcal{L}$. Let $R = \max\lVert\pmb{b}_i\rVert$. Trivially, $\dim(R\mathcal{B}^n_2 \cap \mathcal{L}) = \dim(\mathcal{L}) = k$. Thus $\lambda_i \le R$.

Recursively choose $\pmb{y}_1,\dots,\pmb{y}_k\in\mathcal{L} \backslash \lbrace \pmb{0}\rbrace$ by $\pmb{y}_i \in \mathcal{L}\cap R \mathcal{B}^n_2 \backslash V_{i-1}$ where $V_{i} = \text{span}(\pmb{y}_1,\dots,\pmb{y}_{i})$. Note that $R\mathcal{B}^n_2$ is finite so such $\pmb{y}_1,\dots,\pmb{y}_k$ exists.

By construction, $\dim(\lVert \pmb{y}_i\rVert \mathcal{B}^n_2 \cap \mathcal{L}) \ge \dim(V_i) = i$, thus $\lVert \pmb{y}_i\rVert \ge \lambda_i$.

Take $\pmb{y}\in \mathcal{L}\cap(\lVert \pmb{y}_i\rVert -\epsilon)\mathcal{B}^n_2$ where $\epsilon \in (0, \lVert \pmb{y}_i\rVert\rbrack$. We claim that $\pmb{y}\in V_{i-1}$. If not then we have $(\lVert \pmb{y}_i \rVert - \epsilon) \ge \lVert \pmb{y}\rVert \ge \lVert \pmb{y}_i\rVert$. Contradiction.

Thus $\dim((\lVert \pmb{y}_i\rVert - \epsilon) \mathcal{B}^n_2 \cap \mathcal{L}) \le \dim(V_{i-1}) = i-1$.

Thus we have $\dim(\lVert \pmb{y}_i\rVert \mathcal{B}^n_2 \cap \mathcal{L}) = i$ exactly and $\lVert \pmb{y}_i\rVert = \lambda_i$.

By previous lemma, we can have full rank lattice $\mathcal{L}\subseteq \mathbb{R}^n, \mu(\mathcal{L}) \le \sum\limits^n_{i=1}\dfrac{1}{2}\lambda_i$.

It can be equivalent to $\forall \pmb{x} \in \mathbb{R}^n,\exists \pmb{y} \in \mathcal{L}, \lVert \pmb{x} - \pmb{y}\rVert \le \sum\limits^n_{i=1}\dfrac{1}{2}\lambda_i$. Denoting $\pmb{x} = \sum\limits^n_{i=1}a_i\pmb{y}_i$ and $\pmb{y} = \sum\limits^n_{i=1}\lfloor a_i \rceil \pmb{y}_i$. Noticing that
$$
\lVert \pmb{x} - \pmb{y}\rVert = \lVert \sum^n_{i=1} (a_i - \lfloor a_i \rceil)\pmb{y}_i \rVert \le \sum^n_{i=1} \lVert (a_i - \lfloor a_i \rceil)\pmb{y}_i \rVert \le \sum^n_{i=1}\dfrac{1}{2}\lambda_i
$$

Blichfeldt’s Theorem

Let $\mathcal{L}\subseteq \mathbb{R}^n$ be a full dimensional lattice. Then for any measurable set $A \subseteq \mathbb{R}^n$ such that $\text{vol}_n(A) > \text{vol}_n(\mathcal{L})$, there exists $\pmb{w}\ne\pmb{z}\in A$ such that $\pmb{w} - \pmb{z} \in \mathcal{L}$.

By previous we let $\pmb{B}$ be the basis of $\mathcal{L}$ and we have
$$
\text{vol}_n(A) = \int_{\mathbb{R}^n}1_A(\pmb{x})\text{d}\pmb{x} = \int_{\mathcal{P}(\pmb{B})} | (\mathcal{L}+\pmb{x})\cap A | \text{d}\pmb{x}
$$
Assume $\forall \pmb{x} \in F, |(\mathcal{L} +\pmb{x}) \cap A| \le 1$, then noticing that $\text{vol}_n(A) \le \text{vol}_n(\mathcal{P}(\pmb{B})) = \det(\mathcal{L})$. Contradiction.

Minkowski’s First and Second Theorem

Let $K\subseteq \mathbb{R}^n$ be a non-empty convex set. Then $\forall s,t\ge 0, sK+tK = (s+t)K$. Furthermore, if $K$ is symmetric, then $\forall s,t, sK +tK = (s+t)K$.

Let $(s+t)\pmb{x} \in (s+t)K$, if any $\pmb{x} \in K$. Then $(s+t)\pmb{x} = s\pmb{x} + t\pmb{x} \in sK + tK$. Thus $(s+t)K \subseteq sK+tK$.

Let $\pmb{x},\pmb{y}\in K$, then $s\pmb{x} + t\pmb{y} \in sK+tK$. By convex set, we have $\dfrac{s}{s+t}\pmb{x} + \dfrac{t}{s+t}\pmb{y}\in K$. Then $(s+t)(\dfrac{s}{s+t}\pmb{x} + \dfrac{t}{s+t}\pmb{y})\in (s+t)K$. Thus $sK + tK \subseteq (s+t)K$.

Symmetry part follows by $\forall s, sK = |s|K$.

Let $\mathcal{L} \subseteq \mathbb{R}^n$ be a full dimensional lattice. Let $K \subseteq \mathbb{R}^n$ be a symmetric convex set with $\text{vol}_n(K) > 2^n\det(\mathcal{L})$. Then $K$ contains a non-zero lattice vectors.

$\det(2\mathcal{L}) = 2^n\det(\mathcal{L})$, then $\text{vol}_n(K) > \det(2\mathcal{L})$. By Blichfeldt’s Theorem, there exists $\pmb{w},\pmb{z}\in K$ that $\pmb{w}-\pmb{z} \in \mathcal{L}’ = 2\mathcal{L}$.

Since $\pmb{w}-\pmb{z} \in 2\mathcal{L}\backslash \lbrace \pmb{0}\rbrace$, we let $\pmb{y} = \dfrac{1}{2}(\pmb{w}-\pmb{z}) \in \mathcal{L} \backslash \lbrace \pmb{0}\rbrace$. Noticing that $K$ is symmetric convex set, $-\dfrac{1}{2}\pmb{z} \in K$.

Then $\pmb{y} \in K$ and $A$ exists a non-zero lattice vector in $\mathcal{L}$.

For any full rank lattice $\mathcal{L}$ of rank $n$, we have
$$
\lambda_1 \le 2\left(\dfrac{\det(\mathcal{L})}{\text{vol}_n(\mathcal{B}^n_2)}\right)^{\frac{1}{n}} \le \sqrt{n}\det(\mathcal{L})^{\frac{1}{n}}
$$

Let $d= 2\left(\dfrac{\det(\mathcal{L})}{\text{vol}_n(\mathcal{B}^n_2)}\right)^{\frac{1}{n}}$, then we have $\forall \epsilon > 0, \text{vol}_n(d(1+\epsilon)\mathcal{B}^n_2) = d^n (1+\epsilon)^n\text{vol}_n(\mathcal{B}^n_2) = (1+\epsilon)^n2^n\det(\mathcal{L}) > 2^n\det(\mathcal{L})$.

Then $d(1+\epsilon)\mathcal{B}^n_2$ follows previous theorem that $\exists \pmb{x} \in d(1+\epsilon)\mathcal{B}^n_2 \cap \mathcal{L} \backslash \lbrace \pmb{0}\rbrace$. Such $\pmb{x} \in \mathcal{L}\backslash \lbrace \pmb{0}\rbrace$ must have $\lVert \pmb{x}\rVert \ge \lambda_1$.

Since it applies to any $\epsilon >0$, then $\lVert \pmb{x}\rVert \le d$. Thus $\lambda_1 \le d$.

Also, by $\lbrack -\dfrac{1}{\sqrt{n}}, \dfrac{1}{\sqrt{n}}\rbrack^n \subseteq \mathcal{B}^n_2$ we have $\text{vol}_n(\lbrack -\dfrac{1}{\sqrt{n}}, \dfrac{1}{\sqrt{n}}\rbrack^n) \leq \text{vol}_n(\mathcal{B}^n_2)$. Thus
$$
d = 2\left(\dfrac{\det(\mathcal{L})}{\text{vol}_n(\mathcal{B}^n_2)}\right)^{\frac{1}{n}} \le 2 \left(\dfrac{\det(\mathcal{L})}{\text{vol}_n(\lbrack -\dfrac{1}{\sqrt{n}}, \dfrac{1}{\sqrt{n}}\rbrack^n)}\right)^{\frac{1}{n}} = 2 \left(\dfrac{\det(\mathcal{L})}{2^n n^{-\frac{n}{2}}}\right)^{\frac{1}{n}} = \sqrt{n}\det(\mathcal{L})^{\frac{1}{n}}
$$

For any full rank lattice $\mathcal{L}$ of rank $n$, we have
$$
\left(\prod^n_{i=1}\lambda_i\right)^{\frac{1}{n}} \le 2\left(\dfrac{\det(\mathcal{L})}{\text{vol}_n(\mathcal{B}^n_2)}\right)^{\frac{1}{n}} \le \sqrt{n}\det(\mathcal{L})^{\frac{1}{n}}
$$

Let $\pmb{x}_1,\dots,\pmb{x}_n\in\mathcal{L}$ be independent vectors achieving the successive minima $\lambda_1,\dots,\lambda_n$.

Let $\widetilde{\pmb{x}_1},\dots,\widetilde{\pmb{x}_n}$ be the Gram-Schmidt orthogonalization.

Consider the open ellipsoid defined as follows
$$
E = \lbrace \pmb{y} \in \mathbb{R}^n : \sum^n_{i=1}\left( \dfrac{\langle \pmb{y},\widetilde{\pmb{x}_i} \rangle}{\lVert \widetilde{\pmb{x}_i} \rVert \cdot \lambda_i} \right)^2 < 1 \rbrace
$$
Let $Q = (\dfrac{\widetilde{\pmb{x}_1}}{\lVert \widetilde{\pmb{x}_1} \rVert}, \ldots, \dfrac{\widetilde{\pmb{x}_n}}{\lVert \widetilde{\pmb{x}_n} \rVert})^\top\in\mathbb{R}^{n\times n}$ with rows of normalized Gram-Schmidt vectors of $\pmb{x}_1,\dots,\pmb{x}_n$.

Let $D = (\dfrac{1}{\lambda_1}\pmb{e}_1,\ldots,\dfrac{1}{\lambda_n}\pmb{e}_n)\in\mathbb{R}^{n\times n}$ be the diagonal matrix with diagonal $\dfrac{1}{\lambda_i}$.

Thus we have
$$
\begin{aligned}
E &= \lbrace \pmb{x}\in\mathbb{R}^n : \lVert D Q \pmb{x} \rVert^2 < 1\rbrace\newline
&= (DQ)^{-1} \lbrace \pmb{x} \in \mathbb{R}^n : \lVert \pmb{x} \rVert^2 < 1\rbrace \newline
&= Q^\top (\lambda_1 \pmb{e}_1,\dots,\lambda_n \pmb{e}_n) \lbrace \pmb{x} \in \mathcal{B}^n_2\rbrace
\end{aligned}
$$
The volume of $E$ must follow
$$
\text{vol}_n(E) = |\det(Q^\top (\lambda_1\pmb{e}_1,\dots,\lambda_n \pmb{e}_n))| \text{vol}_n(\mathcal{B}^n_2) = (\prod^n_{i=1}\lambda_i)\text{vol}_n(\mathcal{B}^n_2)
$$
We want to show that $E$ does not contain any non zero lattice vector.

Assume that $\pmb{y} \in \mathcal{L}$ and $1 \le k \le n$ being the largest $k$ that $\lVert \pmb{y}\rVert \ge \lambda_k$. Then $\pmb{y} \in \text{span}(\pmb{x}_1,\ldots,\pmb{x}_k) = \text{span}(\widetilde{\pmb{x}_1},\ldots,\widetilde{\pmb{x}_k})$ by $\lambda$ definition.

Then we notice that
$$
\sum^n_{i=1}\left( \dfrac{\langle \pmb{y},\widetilde{\pmb{x}_i} \rangle}{\lVert \widetilde{\pmb{x}_i} \rVert \cdot \lambda_i} \right)^2 = \sum^k_{i=1}\left( \dfrac{\langle \pmb{y},\widetilde{\pmb{x}_i} \rangle}{\lVert \widetilde{\pmb{x}_i} \rVert \cdot \lambda_i} \right)^2 \ge \dfrac{1}{\lambda_k^2}\sum^k_{i=1}\left( \dfrac{\langle \pmb{y},\widetilde{\pmb{x}_i} \rangle}{\lVert \widetilde{\pmb{x}_i} \rVert} \right)^2 = \dfrac{1}{\lambda_k^2} \lVert \pmb{y} \rVert^2 \ge 1
$$
Then no such $\pmb{y}$ is in $E$. By previous theorem, $\text{vol}_n(E) \le 2^n\det(\mathcal{L})$.

Also $\text{vol}_n(E) = (\prod\limits^n_{i=1}\lambda_i)\text{vol}_n(\mathcal{B}^n_2) \le 2^n \det(\mathcal{L})$. Thus $\prod\limits^n_{i=1}\lambda_i \le 2^n \dfrac{\det(\mathcal{L})}{\text{vol}_n(\mathcal{B}^n_2)}$.