%------------------------------------------------------------------------------------
%--------------------- Author: Essam Ghadafi for the CyBOK Project ------------------
%------------------------------------------------------------------------------------
\input{header}
\usepackage{mathtools}
\DeclarePairedDelimiter\bra{\langle}{\rvert}
\DeclarePairedDelimiter\ket{\lvert}{\rangle}
\DeclarePairedDelimiterX\braket[2]{\langle}{\rangle}{#1 \delimsize\vert #2}
%\usepackage[default]{lato}
%\usepackage{smartdiagram}
\title[]{{\bf{\LARGE Introduction to Lattices in Cryptography }}}
\usepackage{tikz}
\usetikzlibrary{arrows.meta}
\usepackage{caption}
\begin{document}

%-----------------------------------------------------------------------------
% Title Slide
%-----------------------------------------------------------------------------
\begin{frame}
 \titlepage
     \vfill
     \begin{center}
        \tiny{CyBOK \copyright \, Crown Copyright, The National Cyber Security Centre 2025, licensed under the Open Government Licence \url{http://www.nationalarchives.gov.uk/doc/open-government-licence/}}
     \end{center}
\end{frame}

%-----------------------------------------------------------------------------
% Setting the footer
%-----------------------------------------------------------------------------

\setbeamertemplate{footline}
{
  \hbox{%
  \begin{beamercolorbox}[wd=.8\paperwidth,ht=1.00ex,dp=1ex,left]{title in head/foot}%
    \usebeamerfont{title in head/foot}
 
    ~~~~~{{\tiny  CyBOK  ~~~~~~~~~~~~~~~~~~~~~~~Essam Ghadafi}}
  \end{beamercolorbox}%
  \begin{beamercolorbox}[wd=.2\paperwidth,ht=1.00ex,dp=1ex,right]  {date in head/foot}%
    \usebeamerfont{date in head/foot}
   {\tiny \insertframenumber{}\hspace*{1ex} }
  \end{beamercolorbox}}%
  \vskip0pt%
}
\setbeamertemplate{enumerate item}[circle]
\setbeamertemplate{itemize item}[square]  
\setbeamertemplate{itemize subitem}[ball]
\setbeamertemplate{itemize subsubitem}[-]    
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------
\begin{frame}{CyBOK Mapping}
\centering
\vspace{0.1cm}
The lecture maps to the following CyBOK Knowledge Areas:
\vspace{0.4cm}
%==================
\begin{itemize}
    \item 
\headdwo{\href{https://www.cybok.org/media/downloads/Cryptography_v1.0.1.pdf}{Systems Security  $\rightarrow$  Cryptography}}
    
    
    \item \headdwo{\href{https://www.cybok.org/media/downloads/Applied_Cryptography_v1.0.0.pdf}
    {Infrastructure Security $\rightarrow$ Applied Cryptography}}
   
\end{itemize}

\end{frame}

%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame}{Outline}
\begin{itemize}
    \item \headdwo{A brief Overview of Vectors and Matrices:}  Basic concepts of vectors and matrices, essential for understanding lattices
    \item \headdwo{Definition of Lattices:}  What is a lattice? Examples and intuition
    \item \headdwo{Lattice Basis:}  How lattices are generated from basis vectors
    \item \headdwo{Determinant/Volume of a Lattice:} Fundamental parallelepiped and its significance
    \item \headdwo{Geometry of Lattices:} Orthogonality and geometric properties
    \item \headdwo{Successive Minima of a Lattice:} Understanding lattice structure
\end{itemize}
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\section{Vector \& Matrices }
\begin{frame}
\frametitle{Vectors}

A vector is an ordered list of numbers that represents a point or a direction in space

\begin{itemize}
    \item A 2D vector is written as \( \mathbf{v} = (v_1, v_2) \)
    \item A nD vector is written as \( \mathbf{v} = (v_1, v_2, \ldots, v_n) \)
\end{itemize}
~\\

     Vectors can be thought of as arrows pointing from one position to another
\pause
\vspace{1em}

\examw
\begin{center}
\begin{tikzpicture}[scale=0.6]
    % Draw axes
    \draw[->] (-1,0) -- (5,0) node[right] {\(x\)};
    \draw[->] (0,-1) -- (0,4) node[above] {\(y\)};
    
    % Draw vector
    \draw[thick,->] (0,0) -- (3,2) node[above] {\(\mathbf{v} = (3,2)\)};
    
    % Draw grid (optional)
    \draw[help lines, dashed] (3,0) -- (3,2) -- (0,2);
    
    % Mark the point
    \filldraw (3,2) circle (2pt);
\end{tikzpicture}

\end{center}

\end{frame}

%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Vector Length (p-Norm)}

The length (or norm) of a vector is a way to measure its size. The general formula is:

\[ \|\mathbf{v}\|_p = \left( |v_1|^p + |v_2|^p + \ldots + |v_n|^p \right)^{\frac{1}{p}} \]

\pause
Special cases of the p-norm:

\begin{itemize}
    \item \textbf{Euclidean Norm ($L_2$, $p=2$)}: \( \|\vec{v}\|_2 = \sqrt{v_1^2 + v_2^2 + \ldots  + v_{n}^{2}} \)
\pause
    \item \textbf{Manhattan Norm ($L_1$, $p=1$)}: \( \|\vec{v}\|_1 = |v_1| + |v_2| + \ldots +  |v_n| \)
    \item \textbf{Maximum Norm ($L\infty$,  $p \rightarrow \infty$)}: \( \|\vec{v}\|_\infty = \max(|v_1|, |v_2|, , \ldots, |v_n|) \)
\end{itemize}
\pause
The Euclidean norm is the default, and we will denote it by just \( \|\cdot\| \)
\vspace{1em}

\examw~\\
\( \vec{v} = (3, 4) \), \( \|\vec{v}\| = \sqrt{3^2 + 4^2} = \sqrt{9 + 16} = 5 \)

\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Matrix}

A matrix is a rectangular array of numbers, arranged in rows and columns

\[ \mat{M} = \begin{bmatrix} a_{11} & a_{12} & \dots & a_{1n} \\ a_{21} & a_{22} & \dots & a_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \dots & a_{mn} \end{bmatrix} \]

\begin{itemize}
    \item A matrix with \( m \) rows and \( n \) columns is called an \( m \times n \) matrix
    \vspace{1em}
    \item \subheadwo{Special cases:}
    \begin{itemize}
        \item A square matrix has the same number of rows and columns
        \item A diagonal matrix has nonzero elements only on its diagonal
        \item The identity matrix \( \mat{I} \) has ones on the diagonal and zeros elsewhere
    \end{itemize}

\end{itemize}

\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame} {Matrix Multiplication}
You can only multiply compatible matrices~\\~\\
\textcolor{red}{\bf Rule:} The number of columns in the LHS matrix must equal the number of rows in the RHS matrix
~\\~\\

\examw Matrix multiplication of a \(2 \times 2\) matrix with a \(2 \times 1\) matrix (column vector):

\[
\begin{bmatrix}
    a_{11} & a_{12} \\
    a_{21} & a_{22}
\end{bmatrix}
\times
\begin{bmatrix}
    b_{1} \\
    b_{2}
\end{bmatrix}
=
\begin{bmatrix}
    a_{11}b_{1} + a_{12}b_{2} \\
    a_{21}b_{1} + a_{22}b_{2}
\end{bmatrix}
\]

\pause 
~\\~\\
\subheadwo{Remember:}
Multiplying a matrix by its inverse results in the identity matrix:
\[
\mat{A} \times \mat{A}^{-1} = \mat{A}^{-1} \times \mat{A} = \mat{I}
\]
\end{frame}

\section{Lattices}
\begin{frame}{Lattice Definition -- Intuition}
\headw{Lattice:}
 A a set of points in  n-dimensional space that exhibits a periodic structure, i.e.~\subheadwo{A lattice is just a grid of points}
\vspace{1em}

\intuitionhead
The lattice is an infinite grid of points arranged in a regular, repeating pattern that extends in multiple dimensions
\begin{itemize}
    \item The position of each point is determined by the lattice basis
    \item The basis vectors define the directions and distances to reach the lattice points
\end{itemize}

  
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{figure}
\centering
\begin{tikzpicture}[scale=0.33]
    % Define grid size
    \def\n{6}  

    % Draw lattice points and connections
    \foreach \x in {0,...,\n} {
        \foreach \y in {0,...,\n} {
            \foreach \z in {0,...,\n} {
                % Lattice point
                \filldraw[black] (\x,\y,\z) circle (0.5pt);
                
               
                \ifnum\x<\n
                    \draw[black] (\x,\y,\z) -- (\x+1,\y,\z);
                \fi
                \ifnum\y<\n
                    \draw[blue] (\x,\y,\z) -- (\x,\y+1,\z);
                \fi
                \ifnum\z<\n
                    \draw[red] (\x,\y,\z) -- (\x,\y,\z+1);
                \fi
            }
        }
    }

\end{tikzpicture}
\caption{An example of 3D Lattice}
\end{figure}

\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}{Why Lattice-Based Cryptography?}
\begin{itemize}
\item Provable security from worst-case assumptions
  \begin{itemize}
    \item Stronger security guarantees
  \end{itemize}
\item Lattice-based assumptions (e.g., LWE, SIS) are \textquotedblleft{believed}\textquotedblright~to be quantum-resistant 
\item Widely used, e.g.~NIST PQC candidates are mostly lattice-based
\item Efficiency
\begin{itemize}
\item Works over matrices and rings, it mostly involves addition and multiplication so no modular exponentiations or pairings
\end{itemize}  

  \item Relatively more mature than some other PQC approaches 
\end{itemize}
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Lattice Definition}
\vspace{-2.5mm}
Working over \( \R^n \), an \( n \)-dimensional lattice \( L \) is an (additive) discrete subgroup of \( \mathbb{R}^n \), consisting of $n$-dimensional vectors from  \( \R \)

\begin{itemize}
\item \subheadwo{Additive:} For all \( x \in \lat \), \( -x \in \lat \), and for all \( x, y \in \lat \), \( x + y \in \lat \)
\begin{itemize}
\item Adding/subtracting points in the lattice, results in another lattice point
\end{itemize}
\item \subheadwo{Discrete:} Points are sufficiently far apart
\item \subheadwo{Subgroup:} A subset that is a group under addition
\end{itemize}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{figure}
\raisebox{0pt}{\fbox{%
    \begin{tikzpicture}[scale=0.35]
        \def\a{2}
        \def\b{1.5}

        \foreach \i in {-3,...,3} {
            \foreach \j in {-3,...,3} {
                \fill (\i*\a, \j*\b) circle (1.5pt);
            }
        }

        \draw[->, thick, blue] (0,0) -- (\a,0) node[anchor=north] {\(\mathbf{v}_1\)};
        \draw[->, thick, blue] (0,0) -- (0,\b) node[anchor=east] {\(\mathbf{v}_2\)};
    \end{tikzpicture}
}}

\caption{Example 2D lattice}
\end{figure}    
\end{frame}

%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------
\subsection{Lattice Basis}
\begin{frame}{Lattice Basis -- Intuition}
\textbf{\intuitionhead} The basis of a lattice defines the directions (or vectors) you can use to reach any point in the grid
\begin{itemize}
\item Each point in the lattice (grid) can be reached by combining the basis vectors, using some integer multiples
\end{itemize}
\end{frame}


\begin{frame}{Lattice Basis -- Intuition}
\examw Consider the 2D lattice generated by the basis \( \vec{b}_1 = (2, 1) \) and \( \vec{b}_2 = (1, 3) \)~\\

\begin{itemize}
\item Point \( (3, 4) \) (in red) is obtained as \( \vec{b}_1 +  \vec{b}_2 \)
\item Point \( (5, 5) \) (in blue) is obtained by \( 2 \vec{b}_1 + \vec{b}_2 \)
\item $\ldots$
\end{itemize}

\begin{figure}
\centering
\begin{tikzpicture}[scale=0.54, transform shape]
\draw[very thin, gray] (-1,-1) grid (7,7);

% Draw the axes
\draw[->] (-1,0) -- (7,0) node[right] {$x$};
\draw[->] (0,-1) -- (0,7) node[above] {$y$};

\draw[->, thick, black] (0,0) -- (2,1) node[right] {$(2,1)$};
\draw[->, thick, black] (0,0) -- (1,3) node[above right] {$(1,3)$};

\fill[black] (-1,2) circle (2pt);  % (-1,2)
\fill[black] (-1,7) circle (2pt);  % (-1,7)
\fill[black] (0,0) circle (2pt);  % (0,0)
\fill[black] (0,5) circle (2pt);  % (0,5)
\fill[black] (2,1) circle (2pt);  % (2,1)
\fill[black] (2,6) circle (2pt);  % (2,6)
\fill[black] (1,3) circle (2pt);  % (1,3)
\fill[black] (3,4) circle (2pt);  % (3,4)
\fill[black] (4,2) circle (2pt);  % (4,2)
\fill[black] (4,7) circle (2pt);  % (4,7)
\fill[black] (5,0) circle (2pt);  % (5,0)
\fill[black] (6,3) circle (2pt);  % (6,3)
\fill[black] (5,5) circle (2pt);  % (5,5)
\fill[black] (7,1) circle (2pt);  % (7,1)
\fill[black] (7,6) circle (2pt);  % (7,6)

\coordinate (A) at (3,4);
\coordinate (B) at (5,5);
\fill[red] (A) circle (4pt);
\fill[blue] (B) circle (4pt);

\node at (A) [below right] {$(3,4)$};
\node at (B) [above right] {$(5,5)$};

\end{tikzpicture}
\caption{2D-Lattice generated by the basis \( \vec{b}_1 = (2, 1) \) and \( \vec{b}_2 = (1, 3) \)}
\end{figure}

\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Lattice Basis}

A \headdwo{basis} of a lattice is a set of  $k$ linearly independent vectors $\vec{b}_1, \vec{b}_2, \ldots, \vec{b}_k \in \R^n$ (points in the lattice) s.t.~any vector $\vec{v}$ in the lattice can be written as an integer linear combination of the basis vectors:

\[
\vec{v} = \sum_{i=1}^k c_i \vec{b}_i, \quad c_i \in \Z
\]


\pause
\vspace{1em} 

We can think of the basis as a matrix \( \mat{B}  \in \R^{n \times k}\) with $k$-linearly independent vectors \( \vec{b}_1, \ldots, \vec{b}_k \in \mathbb{R}^n \) as columns:

\[
\mat{B} = \begin{bmatrix}
    \vec{b}_1 & \vec{b}_2 & \ldots & \vec{b}_k
\end{bmatrix}
\]
\pause
\vspace{1em} 

We denote the lattice generated by the basis matrix \( \mat{B} \in \mathbb{R}^{n \times k} \) by \( \lat(\mat{B}) \)

\end{frame}

%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Mathematical Lattice}
\begin{itemize}
    \item \( \lat(\mat{B}) \) is a discrete set of points in \( \mathbb{R}^n \) that can be described as: 
\end{itemize}

\[
\lat(\mat{B}) = \left\{ \sum_{i=1}^{k} \alpha_i \vec{b}_i \mid \alpha_i \in \Z \right\}
\]
where \( \alpha_i \in \Z \) are integers.
\vspace{1em} 

Alternatively, we can define the lattice as:

\[
\lat(\mat{B}) = \left\{ \vec{v} \in \mathbb{R}^n \mid \vec{v} = \mat{B} \vec{\boldsymbol{\alpha}} \text{ for some } \vec{\boldsymbol{\alpha}} \in \Z^k \right\}
\]


\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}[c]
\frametitle{Lattice Quiz }
\headdw{Quiz:} Can you think of a matrix \( \mat{B} \) (of any size) with entries from $\R$ that cannot serve as a lattice basis?
\begin{itemize}
    \item \subheadwo{Hint:} The basis span does not form  an additive discrete subgroup $\ldots$
\end{itemize}
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Lattice Rank}

\headdwo{Lattice Rank} is the number of vectors in its basis (i.e., $k$)
\vspace{1em} 

\intuitionhead The rank is the number of independent directions needed to span the lattice space, i.e.~to navigate the entire point grid 
\vspace{1em}

A lattice has \headdwo{full rank} iff $k = n$, meaning it has a square basis matrix 
$\mat{B} \in \R^{n \times n}$ with \textbf{full rank} $n$, i.e., $\det(\mat{B}) \neq 0$.

\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\section{Fundamental Parallelepiped}

\begin{frame}{Fundamental Parallelepiped -- Intuition}
\intuitionhead The fundamental parallelepiped is the smallest region (box) formed by the lattice basis vectors, containing one lattice point and repeating throughout the lattice
\vspace{0.6em}
\begin{itemize}
    \item The smallest building block/tile of the point grid 
    \item The lattice is created by shifting this tile in different directions, forming the entire point grid
\end{itemize}
\vspace{0.1em}
\begin{figure}
    \centering
    \begin{tikzpicture}[scale=0.8, >=stealth]
        \draw[gray!50, thin, step=1] (-1,-1) grid (4,4);
        
        \draw[thick,<->] (-1,0) -- (4,0);
        \draw[thick,<->] (0,-1) -- (0,4);
        
        \draw[thick,->,blue] (0,0) -- (1,2) node[above right, blue] {\scriptsize $\vec{b}_1 = (1, 2)$};
        \draw[thick,->,blue] (0,0) -- (2,1) node[above left, blue, xshift=1.5cm,yshift=-0.5cm] {\scriptsize $\vec{b}_2 = (2, 1)$};
      
        \draw[thick, dashed, red] (1,2) -- (3,3);
        \draw[thick, dashed, red] (2,1) -- (3,3);
        \draw[thick, dashed, red] (0,0) -- (1,2);
        \draw[thick, dashed, red] (0,0) -- (2,1);
        
        \fill[red, opacity=0.3] (0,0) -- (1,2) -- (3,3) -- (2,1) -- cycle;
    \end{tikzpicture}
    \caption{\tiny Fundamental parallelepiped of a 2D lattice with basis vectors $\vec{b}_1 = (1,2)$ and $\vec{b}_2 = (2,1)$}
\end{figure}
\end{frame}

%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}{Fundamental Parallelepiped}
Tiling of the lattice with its basis's fundamental parallelepiped
\begin{figure}
\centering
    
\begin{tikzpicture}[scale=0.5, >=stealth]
    \def\a{1}  % x-component of b1
    \def\b{2}  % y-component of b1
    \def\c{2}  % x-component of b2
    \def\d{1}  % y-component of b2

  
    \draw[gray!50, thin, step=1] (-3,-3) grid (5,5); 
    
    
    \draw[thick,<->] (-3,0) -- (5,0) node[below] {$x$};  
    \draw[thick,<->] (0,-3) -- (0,5) node[left] {$y$};  

    
    \foreach \i in {-2, -1, 0, 1, 2} {  % Lattice points range
        \foreach \j in {-2, -1, 0, 1, 2} { 
            \coordinate (P) at ({\i*\a + \j*\c}, {\i*\b + \j*\d});
            \fill[black] (P) circle (2pt); % Lattice points
        }
    }

    \coordinate (A) at (0,0);
    \coordinate (B) at (\a,\b);
    \coordinate (C) at ({\a+\c},{\b+\d});
    \coordinate (D) at (\c,\d);

    \fill[blue!20] (A) -- (B) -- (C) -- (D) -- cycle;  
    \draw[red, thick] (A) -- (B) -- (C) -- (D) -- cycle;
     \foreach \i in {-2,-1,0,1} {  
        \foreach \j in {-2,-1,0,1} {  
            \begin{scope}[shift={({\i*\a + \j*\c}, {\i*\b + \j*\d})}]
                \draw[orange, thin] (0,0) -- (\a,\b) -- ({\a+\c},{\b+\d}) -- (\c,\d) -- cycle;  
            \end{scope}
        }
    }

    \draw[blue,->,thick] (0,0) -- (\a,\b) node[above left,xshift=0.2cm] {$\vec{b}_1$};
    \draw[blue,->,thick] (0,0) -- (\c,\d) node[above right] {$\vec{b}_2$};

\end{tikzpicture}
     \caption{\tiny Tiling of the 2D lattice with basis vectors $\vec{b}_1 = (1,2)$ and $\vec{b}_2 = (2,1)$}

\end{figure}
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}{Fundamental Parallelepiped}
The \headdwo{fundamental parallelepiped}  of a basis matrix $\mat{B}\in \R^{n \times k}$ denoted by $\paral(\mat{B})$ is the region of space spanned by $\mat{B}$ where each point within the parallelepiped is a \subheadwo{convex combination} of the basis vectors with the coefficients \( \lambda_i \) satisfying \( 0 \leq \lambda_i < 1 \)

     \[\paral(\mat{B}) = \left\{\sum_{i=1}^k \lambda_i \vec{b}_i \quad \text{with} \quad 0 \leq \lambda_i < 1 \right\}
    \]
    \pause
    \vspace{1em}

The \subheadwo{volume} (or n-dimensional measure) of the fundamental parallelepiped is given by the absolute value of the determinant of the basis matrix:
    \[
    \text{Volume} = \left| \det(\mat{B}) \right|
    \]


\end{frame}

%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Fundamental Parallelepiped }
\subheadwo{Some useful properties:}
\begin{itemize}
\item $\mat{B}$ can only be a basis for the lattice $\lat(\mat{B})$ if $\paral(\mat{B})$ does not contain any points in $\lat(\mat{B})$  other than the origin, i.e.~$\lat(\mat{B}) \cap \paral(\mat{B}) = \{\vec{0}\}$ 
%\item $\lat(\mat{B})$ can be fully tiled by placing $\paral(\mat{B})$ at each point in $\lat(\mat{B})$ 
\vspace{1em}

\item $\lat(\mat{B})$ can be fully tiled by placing $\paral(\mat{B})$ at each point in $\lat(\mat{B})$  (as we have seen earlier)
\end{itemize}
\end{frame}

%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Determinant (Volume) of Lattice }
The \headdwo{determinant} of a lattice classifies the lattice density (how spread out the points are):  
\begin{itemize}  
    \item A larger determinant \( \Rightarrow \) a more ``spread-out'' lattice (lower density) 
    \item A smaller determinant \( \Rightarrow \) a denser packing of lattice points (higher density) 
\end{itemize}  
\pause
~\\
\vspace{1em}

For a lattice \( \lat(\mat{B}) \subseteq \R^n \), the determinant (volume)  of  the lattice is $\det( \lat(\mat{B}) ) =  \text{Volume}(\paral(\mat{B})) = |\det(\mat{B})| \leq\prod\limits_{i=1}^{k} \| \vec{b}_i \|$
\end{frame}

%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Lattice Basis}
An \( n \)-dimensional lattice, for \( n > 1 \), will have infinitely many bases that can generate it
\pause
\vspace{1em}

Two matrices \( \mat{B} \in \R^{n \times n} \) and \( \mat{B}' \in \R^{n \times n} \) are bases for the same lattice (i.e.~generate the same lattice) if and only if
\[
\mat{B} = \mat{B}' \mat{U}
\]

for some unimodular matrix \( \mat{U}\in \R^{n \times n} \), where \( \left |\text{det}(\mat{U})\right| =  1 \)
\vspace{1em}

This means we have    \[
    \det(\mat{B}) = \pm \det(\mat{B}')
    \]
    
     
   \pause
\subheadwo{This means the volume of a parallelepiped formed by the lattice basis vectors is invariant, i.e. $\text{Volume}(\paral(\mat{B})) =  \text{Volume}(\paral(\mat{B'}))$}
 \vspace{1em}
~\\
\pause
   \notehead The same applies when the lattice is not full rank (when the basis matrix is not square)

\end{frame}

%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}{Lattice Basis}
\examw
    Consider the lattice in $\R^2$ generated by the basis:
    \[
    \mat{B}_1 =
    \begin{bmatrix}
    1 & 0 \\
    0 & 1
    \end{bmatrix}
    \]

    Another valid basis for the same lattice is 
    \[
    \mat{B}_2 =
    \begin{bmatrix}
    2 & 1 \\
    1 & 1
    \end{bmatrix}
    \]
    \vspace{1em}
We have 
    \[
    \mat{B}_2 = \mat{B}_1 \mat{U}
    \]
where 
   \[
    \mat{U} =
    \begin{bmatrix}
    2 & 1 \\
    1 & 1
    \end{bmatrix}
    \]
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}{Lattice Basis -- The Good, the Bad}
\intuitionhead
\begin{itemize}
    \item A good lattice basis has clear, direct steps, making it easy to navigate and quickly reach any point in the grid.
    \begin{itemize}
    \item Used as a secret key in lattice-based cryptosystems
    \end{itemize}
    \vspace{1em}
    
    \item A bad basis still reaches all points, but is inefficient, requiring unnecessary steps and complicating navigation.
    \begin{itemize}
    \item Used as a public key in lattice-based cryptosystems
    \end{itemize}
\end{itemize}
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Lattice Basis and Cryptography}
\begin{center}
\begin{tikzpicture}[scale=0.7,transform shape] 
        \draw[gray!50, thin, step=0.5] (-3,-3) grid (3,3);

        \foreach \x in {-3,-2,-1,0,1,2,3} {
            \foreach \y in {-3,-2,-1,0,1,2,3} {
                \fill[black] (\x,\y) circle (1.2pt);
            }
        }

        \draw[thick,<->] (-3,0) -- (3,0);
        \draw[thick,<->] (0,-3) -- (0,3);

        \draw[thick,->,blue] (0,0) -- (0.5,0.7) node[above left,blue] {\scriptsize $\mathbf{v}_1$};
        \draw[thick,->,blue] (0,0) -- (0.8,0) node[below right,blue] {\scriptsize $\mathbf{v}_2$};

        \draw[thick,->,red] (0,0) -- (3,1.1) node[above right,red] {\scriptsize $\mathbf{w}_1$};
        \draw[thick,->,red] (0,0) -- (2.5,1) node[above right,red, xshift=-0.5cm] {\scriptsize $\mathbf{w}_2$};

        \node[blue] at (-2.5, 2.5) {{Good}};
        \node[red] at (-2.5, 1.9) {{Bad}};

\end{tikzpicture}
\end{center}
\vspace{0.2em}
One can classify the basis as \textcolor{blue}{Good} or \textcolor{red}{Bad}:
\begin{itemize}
\item \textcolor{blue}{Good:} Consists of short, nearly orthogonal vectors, making computations more efficient and problem-solving easier
\vspace{0.8em}
\item \textcolor{red}{Bad:} Consists of long and highly skewed vectors (almost parallel), making the lattice computationally difficult to work with 
\end{itemize}
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}{Lattice Basis Reduction Methods}
How to go from \textcolor{red}{bad} to \textcolor{blue}{good}? 
\pause
\vspace{1em}

 
Transforming a \textcolor{red}{bad} basis to a better one involves shortening vectors and improving orthogonality among them
\vspace{1em}


\begin{itemize}
    \item \headdwo{Gram-Schmidt:} Orthogonal but unstable and order-dependent
    \begin{itemize}
        \item Does not always return a valid lattice basis ~\\
    \end{itemize}
    \item \headdwo{LLL (Lenstra-Lenstra-Lovász):} Efficient (poly-time), produces shorter, nearly orthogonal vectors. Utilises Gram-Schmidt Orthogonalisation
~\\

    \item \headdwo{BKZ (Block Korkine-Zolotarev):} Improves LLL with block reduction, better results but higher cost
\end{itemize}
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\section{Successive Minima}
\begin{frame} {Successive Minima}

\intuitionhead 
The successive minima of a lattice measure how spread out the lattice is by identifying the smallest radii that enclose at least $k$ independent vectors (points)
\begin{center}
\begin{tikzpicture}[scale=0.6,transform shape] 
    \draw[thin,gray!50] (-5,-4) grid (5,4);  
    
    % Draw axes
    \draw[thick,<->] (-5,0) -- (5,0);  
    \draw[thick,<->] (0,-4) -- (0,4); 

    \def\a{1.5}  
    \def\b{0.75} 

    \foreach \x in {-2,-1,0,1,2}  
        \foreach \y in {-2,-1,0,1,2}  
            \node[fill=black, circle, inner sep=1.3pt] at (\a*\x+\b*\y, \a*\y) {}; 

    \draw[thick,->,darkred] (0,0) -- (\a,0); 
    \draw[thick,->,darkblue] (0,0) -- (\b,\a); 

    % First minimum (lambda_1) next to b1
    \draw[darkred,thick] (0,0) circle [radius=\a];
    \node[fill=darkred, circle, inner sep=2pt] at (\a,0) {}; 
    \node[darkblue] at (0.28*\a, 0.9*\a) {\footnotesize $\lambda_2$}; 

    \draw[darkblue,thick] (0,0) circle [radius=sqrt(\a^2+\b^2)];
    \node[fill=darkred, circle, inner sep=2pt] at (\a,0) {}; 
    \node[fill=darkblue, circle, inner sep=2pt] at (\b,\a) {}; 
    \node[darkred] at (0.6*\a, 0.15*\a) {\footnotesize $\lambda_1$};

\end{tikzpicture}
\end{center}
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}{Successive Minima}
    The \headdwo{\( i \)-th successive minimum} \( \lambda_i(\lat (\mat{B})) \) of a lattice $\lat(\mat{B}) \subseteq \mathbb{R}^n$ is the smallest radius $r$ s.t.~$i$ linearly independent vectors $\{\vec{v_1}, \ldots, \vec{v_i}\}$ of length $\leq r$ exist \pause, i.e. 
    $\|v_j\| \leq r$ for all $j = 1, \dots, i$.
    \[
    \lambda_i(\lat(\mat{B})) = \inf \{ r > 0 \mid \dim (\text{span} ( \lat(\mat{B}) \cap B(0, r) )) \geq i \}
    \]
    
   \textbf{Where:}
   \begin{itemize}
   
   \item \( B(0, r) \) denotes the closed ball centdarkred at the origin with radius \( r \)
    \item \(\lat(\mat{B}) \cap B(0, r) \) is the set of lattice points contained within this ball
    
   \end{itemize}
   
   \vspace{1em}
   
   \notehead \( \inf \) denotes the infimum: the largest number that is \( \leq \) every element of the set.
  
  \end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}{Successive Minima}
    \begin{itemize}
        \item \( \lambda_1(\lat(\mat{B})) \) is the length of the shortest nonzero vector in \( \lat(\mat{B})\)
        \begin{itemize}
        \item The shortest vector is not unique, e.g. $\|\vec{v}\|=\|-\vec{v}\|$
                \end{itemize}
                \pause
        \item \( \lambda_2(\lat(\mat{B})) \) is the \headdwo{radius} of the smallest ball containing two linearly independent vectors 
~\\        \pause
        \item In general, \( \lambda_i(\lat(\mat{B})) \) is the \headdwo{radius} of the smallest ball  containing \( i \) linearly independent lattice vectors
    \end{itemize}
    
  The \(\lambda_n\)-ball contains a basis for an \(n\)-dimensional lattice
 \begin{center}
\begin{tikzpicture}[scale=0.4,transform shape]
  
    \draw[thin,gray!50] (-5,-4) grid (5,4);  
    
    % Draw axes
    \draw[thick,<->] (-5,0) -- (5,0);  
    \draw[thick,<->] (0,-4) -- (0,4);  

    \def\a{1.5} 
    \def\b{0.75}
    \foreach \x in {-2,-1,0,1,2}  
        \foreach \y in {-2,-1,0,1,2}  
            \node[fill=black, circle, inner sep=1.3pt] at (\a*\x+\b*\y, \a*\y) {}; 

    \draw[thick,->,darkred] (0,0) -- (\a,0); 
    \draw[thick,->,darkblue] (0,0) -- (\b,\a);

    % First minimum (lambda_1) next to b1
    \draw[darkred,thick] (0,0) circle [radius=\a];
    \node[fill=darkred, circle, inner sep=2pt] at (\a,0) {}; 
    \node[darkblue] at (0.36*\a, 1.2*\a) {\footnotesize $\lambda_2$}; 

    \draw[darkblue,thick] (0,0) circle [radius=sqrt(\a^2+\b^2)];
    \node[fill=darkred, circle, inner sep=2pt] at (\a,0) {}; 
    \node[fill=darkblue, circle, inner sep=2pt] at (\b,\a) {}; 
    \node[darkred] at (0.8*\a, 0.15*\a) {\footnotesize $\lambda_1$};
\end{tikzpicture}
\end{center}
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------
\begin{frame}{Minimum Distance of a Lattice}
The \textbf{minimum distance} of a lattice \( \lat \), denoted by \( \lambda(\lat) \), is the shortest distance between any two points in the lattice. It answers the question:
\begin{itemize}
    \item \textbf{Q:} How close are the closest two points in the grid?
\end{itemize}
\pause
    \vspace{0.5em}
    
  Formally,
        \[
    \lambda(\lat) = \min_{\vec{v}, \vec{w} \in \lat, \vec{v} \neq \vec{w}} \|\vec{v} - \vec{w}\|
    \]

\vspace{1em}
The lattice minimum distance is also the length of its shortest non-zero vector: \( \lambda(\lat) = \lambda_1(\lat) \)
\pause
\vspace{1em}

\notehead Since lattice points are discrete, the minimum distance must be \( > 0 \), as otherwise the set would not be discrete and would not form a lattice

\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}{Dual Lattice}
   The \headdwo{dual} (or  \headdwo{reciprocal}) \headdwo{lattice}  $\lat^*$ of a lattice  $\lat \subseteq \R^n$ is defined as:
    \[
    \lat^* = \{ \vec{y} \in \R^n \mid \vec{y}^T \vec{x} \in \Z, \quad \forall \vec{x} \in \lat \}
    \]
    That is, the dual lattice consists of all vectors in $\R^n$ that have an integer inner product with every vector $\lat$
\vspace{1em}

The basis of $\lat^*$ is is given by:
    \[
    \mat{B}^* = (\mat{B}^T)^{-1}
    \]
\end{frame}
%------------------------------------------------------------
%------------------------------------------------------------

\begin{frame}{Key Takeaways}
\begin{itemize}
    \item \headdwo{Lattices} are discrete grids of points formed by integer combinations of basis vectors
    \item \headdwo{The basis} of a lattice is not unique, but the determinant (volume of the fundamental parallelepiped) is invariant
    \begin{itemize}
    \item Good lattice bases are short and nearly orthogonal; bad ones are long or nearly parallel, leading to inefficiency
    \end{itemize}
    \item \headdwo{The determinant} of a lattice represents the ``density'' of the lattice and plays a crucial role in geometry and applications
    \item \headdwo{Successive minima} provide insights into the structure and density of the lattice 
      \end{itemize}
\end{frame}
%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------

\begin{frame}
\frametitle{Additional Resources \& Reading}
%\marcom{EG}{ADd}
\begin{itemize}
\item \url{https://web.eecs.umich.edu/~cpeikert/pubs/lattice-survey.pdf}
\item \url{https://link.springer.com/chapter/10.1007/978-3-642-23082-0_7}
\item \url{https://link.springer.com/chapter/10.1007/978-3-540-88702-7_5}
\end{itemize}
\end{frame}
%-------------------------------------------------------------------
\end{document}


