%------------------------------------------------------------------------------------
%--------------------- 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}

\title[]{{\bf{\LARGE {Lattice-Related Hard Problems }
 }}}

\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{Worst-case vs Average-case Problems}
      \begin{itemize}
        \item Definition and key differences
        \item Examples in cryptography
      \end{itemize}
    
    \item \headdwo{SVP and its Variants (Shortest Vector Problem)}
      \begin{itemize}
        \item Problem description, Hardness and Variants
      \end{itemize}
    
    \item \headdwo{CVP and its Variants (Closest Vector Problem)}
      \begin{itemize}
        \item Problem description, Hardness and Variants
      \end{itemize}
    
    \item \headdwo{SIS (Short Integer Solution) Problem}
      \begin{itemize}
            \item Problem description, Hardness and Variants
      \end{itemize}
    
    \item \headdwo{LWE (Learning With Errors) Problem}
      \begin{itemize}
           \item Problem description, Hardness and Variants
      \end{itemize}
  \end{itemize}

\end{frame}

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

\begin{frame}{Worst-Case vs.~Average-Case Problems}
\begin{itemize}

\item \headdwo{Average-Case Problems:} The attacker must succeed in solving some random instances of the problem
~\\~\\
\examw \textbf{Average-Case Factoring Problem:}  Given a composite integer \( N = p \times q \) from a distribution \( D_N \) over products of two large primes, find \( p \) and \( q \)
\pause
\vspace{0.5em}

\item \headdwo{Worst-Case Problems:} The attacker must succeed in solving all instances of the problem~\\~\\
\examw \textbf{Worst-Case Factoring Problem:} Given a composite integer \( N = p \times q \), where \( p \) and \( q \) are large primes, find \( p \) and \( q \)

\end{itemize}
\pause
\vspace{1em}

Some problems are hard in the worst-case but easy on average. Basing  security on worst-case hardness provides stronger guarantees
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------
\section*{Shortest \& Closest Vector Problems}

\begin{frame}{Shortest Vector Problem (SVP)}
\intuitionhead Which point in the point grid is closest to the origin point (centre of the grid)?
\pause  
  \vspace{1em}
   
\headdwo{The Shortest Vector Problem (SVP)}:
    \begin{itemize}
        \item  Given a basis $\mat{B}$ for a lattice $\lat(\mat{B})$, find the shortest non-zero vector $\vec{v}$ in the lattice
        ~\\
         \textbf{Mathematically:}
        \[ ||\vec{v}|| = \min_{\vec{w} \in \lat(\mat{B}) \setminus \{\vec{0}\}} ||\vec{w}|| \]
        equivalently 
         \[ ||\vec{v}|| = \lambda_1 (\lat(\mat{B})) \] 
         
         \subheadwo{Remember the 1st successive minimum $\lambda_1$ denotes the shortest non-zero vector in the lattice}

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

\begin{frame} {Shortest Vector Problem (SVP)}
How hard is the problem?
\begin{itemize}

        \item Hard because finding the shortest vector is NP-hard
        \vspace{1em}
        \item Easy to solve when the basis vectors $\{\vec{b}_1, \vec{b}_2, \dots, \vec{b}_n\}$ are \textit{orthogonal}, i.e.~$\vec{b}^{T}_i \vec{b}_j = 0$ for all $i,j \in \{1,\ldots,n\} \text{~where~}  i \neq j$. In this case the shortest vector is the shortest base vector $\vec{b}_i$
\[
\|\vec{v}_{\text{SVP}}\| = \min_{1 \leq i \leq n} \|\vec{b}_i\|
\]

    \end{itemize}
   % \includegraphics[width=0.7\textwidth]{svp_diagram.png} % Add SVP illustration
 
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame}{Approximate SVP ($\gamma$-SVP)}
A related variant to SVP
\vspace{1em}

The goal is to find a vector $\vec{v}$ that is at most 
$\gamma$ times the length of the shortest vector where $\gamma \geq 1$
\vspace{1em}
\pause
    \begin{itemize}
        \item  Given a basis $\mat{B}$ for a lattice $\lat(\mat{B})$, find a vector $\vec{v} \in \lat(\mat{B})\setminus \{\vec{0}\}$ where $ ||\vec{v}|| \leq \gamma \cdot \lambda_1 (\lat(\mat{B})) $

\vspace{1em}

         \subheadwo{Remember the 1st successive minimum $\lambda_1$ denotes the shortest non-zero vector in the lattice}
\vspace{1em}
\pause
        \item The larger $\gamma$, the easier the problem. $1$-SVP is SVP
    \end{itemize}
\end{frame}	
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame} { SVP variants}
\begin{itemize}
\item  \headdwo{Short Independent Vectors  Problem (SIVP)} denoted by ($\text{SIVP}_{\gamma}$):
~\\
\inputText  Basis $\mat{B} \in \Z_q^{m \times n}$ for $\lat(\mat{B})$
~\\
\outputText Find $n$ linearly independent vectors $\vec{v}_1, \ldots, \vec{v}_n \in \lat(\mat{B})$ such that $\|\vec{v}_i \| \leq \gamma \lambda
 _n(\lat(\mat{B}))$ for all $i=1,\ldots,n$
\pause
\vspace{2em}

%--------------------------------------
\item \headdwo{GAP SVP ($\text{GapSVP}_{\gamma}$)}:
  ~\\
  \inputText Basis $\mat{B} \in \Z_q^{m \times n}$ for $\lat(\mat{B})$
  ~\\
  \outputText Decide whether $\lambda_1 (\lat(\mat{B})) \leq 1$ or
   $\lambda_1 (\lat(\mat{B})) > \gamma$
\end{itemize}
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame}{Closest Vector Problem (CVP)}
\vspace{-3mm}
\intuitionhead 
From a location (which may not be a point) on the grid, find the nearest grid point
\pause
\vspace{1em}

\headdwo{Closest Vector Problem (CVP)}
    \begin{itemize}
        \item Given a basis $\mat{B}$ for a lattice $\lat(\mat{B})$ and a target point $\vec{t}$, find the closest lattice vector $\vec{v} \in \lat(\mat{B})$ 
        ~\\
        \textbf {Mathematically:}
        \( \min_{\vec{v} \in \lat(\mat{B})} || \vec{v} - \vec{t} || \)
        
\end{itemize}
   \begin{center}
        \begin{tikzpicture}[scale=0.6]
            \draw[gray!50, thin] (-2,-2) grid (3,3);
            \foreach \x in {-2,-1,0,1,2,3}
                \foreach \y in {-2,-1,0,1,2,3}
                    \filldraw[black] (\x,\y) circle (2pt);
            \filldraw[blue] (1.3,1.7) circle (2pt);
             \node[blue, right] at (1.3,1.7) {\textbf{$t$}};
            \draw[red, thick, dashed, ->] (1.3,1.7) -- (1,2)
            ;
        \end{tikzpicture}
    \end{center}
    \pause
    \vspace{0.5em}
    
    \begin{itemize}
             \item Harder than SVP and is NP-hard
         \begin{itemize}
         \item SVP is a special case where $\vec{t}=\vec{0}$. If one can solve CVP, one can solve SVP. i.e.~ SVP $\leq$ CVP
         \end{itemize}
    \end{itemize}
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame}{Approximate CVP ($\gamma$-CVP)}
 The \headdwo{Approximate CVP ($\gamma$-CVP)}  is a variant of CVP
 \vspace{1em}
 
 Instead of finding the closest vector $\vec{v} \in \lat(\mat{B})$ to $\vec{t}$, the task is instead to  find $\vec{v}\in \lat(\mat{B})$ where the distance between $\vec{v}$ and $\vec{t}$ is at most $\gamma$ times the distance between $\vec{t}$ and the closest vector in the lattice
      
                \vspace{1em}
        \textbf{Mathematically:}
        \[ \min_{\vec{v} \in \lat(\mat{B})} \left\| \vec{v} - \vec{t} \right\| \leq \gamma \cdot \min_{\vec{v}' \in \lat(\mat{B})} \left\| \vec{v}' - \vec{t} \right\| \]
\pause 
   \vspace{0.5em}
 
        \begin{itemize}
        \item    At least as hard as $\gamma\text{-SVP}$, i.e. $\gamma\text{-SVP} \leq \gamma\text{-CVP}$
        \end{itemize}
    
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame}{Bounded Distance Decoding (BDD)}
The \headdwo{Bounded Distance Decoding (BDD)} problem is a special case of CVP where the target $\vec{t}$ is close to a lattice point
   
       \begin{center}
        \begin{tikzpicture}
            \draw[gray!50, thin] (-2,-2) grid (3,3);
            \foreach \x in {-2,-1,0,1,2,3}
                \foreach \y in {-2,-1,0,1,2,3}
                    \filldraw[black] (\x,\y) circle (2pt);
            \filldraw[blue] (0.8,1.2) circle (2pt);
            \draw[red, thick, dashed, ->] (0.8,1.2) -- (1,1);
        \end{tikzpicture}
    \end{center}
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------
\section*{Short Integer Solution }

\begin{frame}{Short Integer Solution (SIS)}
The \headdwo{SIS}  problem introduced by Ajtai~\cite{Ajt1996} is parametrised by parameters $m,n,q,\gamma$ and is denoted by $\text{SIS}_{m,n,q,\gamma}$
    \begin{itemize}
        \item Given a random  matrix $\mat{A} \in \Z_q^{m \times n}$, find a short non-zero vector $\vec{x}\in \Z^n$ such that $\| \vec{x}  \| \leq \gamma$ and 
           \[ \mat{A} \vec{x} \equiv \vec{0} \bmod q \]
\end{itemize}
\begin{figure}
\centering
        \begin{tikzpicture}[scale=0.8, every node/.style={transform shape}]
        
        \fill[gray!30] (0,0) rectangle (3,2);
        \draw[thin] (0,0) rectangle (3,2);
        \node at (1.5,1) {\Large $\mat{A}$};
        
        \fill[blue!30] (3.2,0) rectangle (3.5,2);
        \draw[thin] (3.2,0) rectangle (3.5,2);
        \node at (3.35,1) {\Large $\vec{x}$};
        
       \node at (4.48,1) {\Large $= \vec{0}$};
        
       \draw [<->,gray] (-0.2,2) -- (-0.2,0) node[midway,xshift=-10pt] {\large $m$};
       \draw [<->,gray] (0,-0.2) -- (3,-0.2) node[below,midway] {\large $n$};
       \draw [<->,gray] (3.7,2) -- (3.7,0) node[right,midway,xshift=-2pt] {\large $n$};
       \draw [<->,gray] (3.1,-0.2) -- (3.6,-0.2) node[below, midway] {\large $1$};
    \end{tikzpicture}

\end{figure}
  \pause          
\begin{itemize}
\item Generally, $\gamma < q n$, as otherwise, $\vec{s}=(q,0, \ldots, 0)$ is a valid solution
\item The bigger $m$, the harder the problem
\item The problem is trivial when $n< m$ 
\end{itemize}   
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame}{  Short Integer Solution (SIS)}
SIS is used in some  hash functions and digital signatures
\pause
 \vspace{1em}

\headdwo{The Inhomogeneous Short Integer Solution (ISIS)} problem is similar to SIS, except the right-hand side is $\vec{y} \in \Z_q^n$ instead of $\vec{0}$ 
\vspace{1em}

ISIS is parametrised by $m,n,q,\gamma$ and denoted by $\text{ISIS}_{m,n,q,\gamma}$
    \begin{itemize}
        \item Given a random matrix $\mat{A} \in \Z_q^{m \times n}$ and a random vector $\vec{y} \in \Z_q^m$ find a short vector $\vec{x}\in \Z^n$ such that $\| \vec{x}  \| \leq \gamma$ and 
                \[ \mat{A} \vec{x} \equiv \vec{y} \bmod q \]
        
        \pause
  \begin{itemize}
\item ISIS is as hard as SIS
\begin{itemize}
\item SIS requires solving $\mat{A} \vec{x} = \vec{0}$ ~vs.~ solving  $\mat{A} \vec{x} - \vec{y}  = \vec{0}$ in ISIS
\end{itemize}
\end{itemize}
\end{itemize}
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame}{SIS as a Lattice Problem}
SIS is a lattice problem as well
\vspace{1em}

We use the matrix $\mat{A}\in  \Z_q^{m \times n}$ to define the lattice:

\[
\lat(\mat{A}) = \{\vec{e} \in \Z^n : \mat{A} \vec{e} = \vec{0} \bmod q\}
 \]
\vspace{1em}
SIS is then defined as finding a short vector $\vec{e}$ in this lattice 
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\section*{Learning with Errors}
\begin{frame} {LWE -- Setting the scene }
Consider a system of \( m \) linear equations of the form:  
\begin{align*}
\sum_{i=1}^{n} a_{1,i} s_i &= b_1 \bmod q\\
\vdots \\
\sum_{i=1}^{n} a_{m,i} s_i &= b_m \bmod q
\end{align*}

where \( a_{j,i} \in \mathbb{Z}_q \) are known coefficients, \( b_j \in \mathbb{Z}_q \) are known results, and \( s_i \in \mathbb{Z}_q \) are the unknowns we seek to solve for. 
\pause
\vspace{0.5em}

We can represent the system as  
\[
\mathbf{A} \vec{s} = \vec{b} \bmod q
\]
\pause
\vspace{0.5em}

This system of equations is straightforward to solve (in poly time),  e.g., using Gaussian elimination
\end{frame}

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

\begin{frame}{Learning with Errors (LWE)}
\headdwo{LWE} introduced by Regev ~\cite{{Reg2009}} adds small noise to linear equations, making them hard to solve even for quantum computers
\vspace{1em}

LWE and its variants have been used to construct various types of cryptosystems, including:
\begin{itemize}
\item Public-Key Encryption
\item Key Exchange
\item Identity-Based Encryption
\item Zero-Knowledge Proofs
\item $\ldots$
\end{itemize}
\end{frame}

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

\begin{frame} {Learning With Errors (LWE)}

\textbf{Definition:} Let $m, n, q$ be positive integers, and let $\chi$ be a probability distribution over $\Z_q$ 
\vspace{1em}

The (search) LWE problem denoted by ($\text{LWE}_{m,n,q,\chi}$)  is:
 \begin{itemize}
 
 \item Randomly choose a secret vector $\vec{s} \in \Z_q^n$
 \item Choose a uniformly random matrix $\mathbf{A} \in \Z_q^{m \times n}$ 
 \item  Choose a random error/noise vector $\vec{e}$  according to $\chi^m$
 \begin{itemize}
 \item        i.e., each coordinate $e_i$ is independently drawn from $\chi$
 \end{itemize}
 \end{itemize}

\vspace{1em}
\pause

\inputText \( (\mathbf{A}, \vec{b} )\) where \(
\mathbf{A} \vec{s} + \vec{e} \equiv \vec{b} \mod q \) where 
 $\vec{b} \in \mathbb{Z}_q^m$~\\
 
  \outputText Recover $\vec{s}$  


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

\begin{frame}{Decisional LWE}
The \headdwo{(decision) LWE} problem denoted by ($\text{D-LWE}_{m,n,q,\chi}$)  is:

 \begin{itemize}
 \item $\mat{A}$, $\vec{s}$, and $\vec{e}$ are all chosen as in the search LWE problem
\vspace{1em}

   \item \textbf{Challenge Generation:}
    \begin{itemize}
        \item \textbf{Case 0} (real): Compute $\vec{b}_0 = \mat{A} \vec{s} + \vec{e} \mod q$
        \item \textbf{Case 1} (fake): Choose $\vec{b}_1 \in \Z_q^m$ uniformly at random
    \end{itemize}
    
 \end{itemize}
\vspace{1em}
\inputText  $(\mat{A}, \vec{b}_b)$ where $b \in \{0,1\}$ is chosen uniformly at random

 \outputText Guess the case $b$
 \pause
\vspace{1em}

Interestingly, LWE can be reduced to D-LWE
\begin{itemize}
\item An algorithm solving D-LWE can also solve LWE. The reverse implication is trivial
\begin{itemize}
\item This means equivalence of the two variants of LWE
\end{itemize}
\end{itemize}

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

\begin{frame}{Hardness of LWE}
\begin{itemize}
\item If one can solve $\text{SIS}_{m,n,q,\gamma}$, one can solve $\text{LWE}_{m,n,q,\chi}$, i.e. $\text{LWE}_{m,n,q,\chi} \leq \text{SIS}_{m,n,q,\gamma}$
\vspace{1em}
\pause

\item If one can solve $\text{LWE}_{m,n,q,\chi}$, one can solve $\text{GapSVP}_{\gamma}$
\begin{itemize}
\item e.g. \cite{Reg2009,BLP+2013}: $\text{GapSVP}_{\gamma},\text{SIVP}_{\gamma} \leq \text{LWE}_{m,n,q,\chi}$
\vspace{1em}


\notehead~In~\cite{Reg2009} the reduction is \emph{quantum}, while in~\cite{BLP+2013} it is \emph{classical} but only for \emph{polynomial modulus}~$q$, with some losses in dimension and noise

\end{itemize}

\end{itemize}

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

\begin{frame}{Ring-LWE -- Setting the Scene}
\headdwo{Ring-LWE (R-LWE)} \cite{LPR2010} is a LWE variant adapted to \text{polynomial rings} (instead of integers) to improve efficiency
\vspace{1em}

\subheadwo{Remember:} A polynomial is of the form $\sum\limits_{i=0}^{d} c_i x^i$, where:
\begin{itemize}
\item  $x$ is the indeterminate, $d$ is the degree of the polynomial (i.e. the highest power of $x$), and $c_i \in \Z$ are the coefficients
\end{itemize}

\vspace{1em}

Polynomials can be represented by their coefficient vector \( \vec{c} = (c_0, c_1, \ldots, c_d) \)
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame}{Ring-LWE -- Setting the Scene}
\begin{itemize}
\item \headdwo{Polynomial Ring $R$:} Let \( R = \Z[x] / f(x) \)
for some monic polynomial $f(x)$ of degree $d=n$, (e.g. $f(x)=x^n + 1$)
\begin{itemize} 
\item Elements of \( R \) are polynomials  of degree \( < n \) with integer coefficients
\begin{itemize}
\item $R$ is a set of polynomials reduced  modulo  $f(x)$ 
\end{itemize}

\end{itemize} 
\vspace{1em}
\pause

\item \headdwo{Polynomial Ring $R_q$:} 
Let \( R_q = \Z_q[x] / f(x) \)
\begin{itemize}
\item Elements of $R_q$ are polynomials of degree $< n$ with coefficients in  in $\Z_q$
\end{itemize} 

\end{itemize}
\vspace{1em}
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame}{Ring-LWE}
 
\textbf{Definition:} Given polynomial rings $R$ and $R_q$, and an error distribution $\chi$ over small elements of ring $R$
\vspace{1em}

The \headdwo{(Search) Ring-LWE  (R-LWE)} problem, denoted by $(\text{R-LWE}_{q,n,\chi})$, is defined as follows:
\begin{itemize}
    \item Sample polynomials \(a_1, \ldots, a_n \in R_q\) independently and uniformly at random. Let $\vec{a}=(a_1,\ldots, a_n)$
    
   
    \item Sample error polynomials \( e_1, \dots, e_n\) independently from   \(\chi \). Let \(\vec{e}=(e_1, \ldots, e_n)\)
\end{itemize}
~\\
\inputText \( (\vec{a}, \vec{b} = s~\vec{a} + \vec{e} \bmod qR)\), for some fixed polynomial $s \in R_q$~\\
\outputText Recover \( s \)
\pause
\vspace{1em}

\textcolor{red}{Note:} \(\bmod~qR\) means reducing polynomial coefficients modulo \( q \), where \( qR \) is the ideal in \( R \) generated by \( q \)

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

\begin{frame}{Decisional Ring-LWE}
The \headdwo{Decisional Ring-LWE (D-R-LWE)} problem denoted by ($\text{D-R-LWE}_{q,n,\chi}$) can be defined similarly where the task is to distinguish  \( (\vec{a}, \vec{b}) \), where  
\[
\vec{b} = s \vec{a} + \vec{e} \mod qR
\]
  from a uniform tuple $(\vec{a}, \vec{b})  \in R_q^n \times R_q^n$
  
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------
\begin{frame}{Hardness of Ring-LWE}

Lyubashevsky, et al.~\cite{LPR2010,LPR2013} gave the following results
\[
\text{Ideal-SIVP}_\gamma \text{(worst case)}
\;\leq_{\text{quantum polytime}}
\text{D-R-LWE}_{q,n,\chi}
\]

\begin{itemize}
\item If you can solve D-R-LWE, there is a \textbf{quantum algorithm} that can solve 
$\text{Ideal-SIVP}_\gamma \text{(worst case)}$
\end{itemize}
\vspace{1em}
\pause

\[
\text{R-LWE}_{q,n,\chi} \;\leq\;
\text{D-R-LWE}_{q,n,\chi}
\]
\begin{itemize}
\item If you can solve Decisional R-LWE, there is a \textbf{classical algorithm} that can solve Search R-LWE

\end{itemize}
\end{frame}

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

\begin{frame}{Ring-LWE vs.~LWE}

\begin{itemize}
\item R-LWE yield more efficient constructions
\begin{itemize}
\item Multiplication in the polynomial ring is more efficient, e.g.~using FFT-like techniques

\item Smaller element representations (Elements from $R_q$ vs. elements from $\Z$)
\begin{itemize}
\item Storage cost in standard LWE: $O(m \cdot n)$ integers (typically $O(n^2)$ since $m = O(n)$)
\item Storage cost in Ring-LWE: $O(n)$ integers

\end{itemize}
\end{itemize}
\vspace{1em}

\item Like LWE's relation to SIS, Ring-LWE retains worst-case hardness due to its close connection to Ring-SIS 

\end{itemize}
\vspace{1em}

\pause
\textcolor{red}{\textbf{Note:}} R-LWE is defined over \textbf{structured lattices} (ideal lattices with algebraic structure), 
whereas LWE works over \textbf{general, unstructured lattices}
\begin{itemize}
\item  R-LWE assumes hardness for a special class of lattices
\end{itemize}

\end{frame}
%------------------------------------------------------------------------------------
\begin{frame}{Module-LWE –- Intuition}
\intuitionhead \headdwo{M-LWE} is a bridge between (unstructured) LWE and structured Ring-LWE
\begin{itemize}
    \item {LWE:} Elements are simple vectors over $\mathbb{Z}_q^n$ (unstructured)
    ~\\~\\
    \item {Ring-LWE:} Elements are polynomials from a ring $R_q$ (highly structured)
~\\~\\
\pause   
    \item {M-LWE:} Elements are vectors of polynomials in $R_q^k$, 
     more structured than LWE but less structured than Ring-LWE
    \begin{itemize}
        \item Interpolates between LWE and Ring-LWE
    \end{itemize}
\vspace{1em}
\pause

 Ring-LWE is a special case of Module-LWE where $k=1$
 \end{itemize}
 
\end{frame}

%------------------------------------------------------------------------------------
\begin{frame}{Module-LWE -- Definition }
\vspace{-0.8mm}
Similarly to the setup for Ring-LWE, given 
\[
R = \Z[x]/f(x), \quad 
R_q = R/qR,
\] 
a module rank \(k\), and an error distribution \(\chi\) over small elements of \(R\)


\vspace{1em}

\pause
The \headdwo{(Search) Module-LWE (M-LWE)} problem, denoted by $(\text{M-LWE}_{q,n,k,\chi})$, is:

\begin{itemize}
    \item Sample elements \(\vec{a}_1, \ldots, \vec{a}_n \in R_q^k\) independently and uniformly at random. 
    Let $\mat{A} = (\vec{a}_1, \ldots, \vec{a}_n) \in R_q^{n \times k}$.
    \item  Independently sample error elements \(e_1, \ldots, e_n \in R_q\) from \(\chi\). 
    Let $\vec{e} = (e_1, \ldots, e_n) \in R_q^n$.
\end{itemize}

\vspace{0.5em}

\pause

\inputText \( (\mat{A}, \vec{b} = \mat{A} \vec{s} + \vec{e} ) \in R_q^{n \times k} \times R_q^{n}\), for some secret vector of polynomials \(\vec{s} \in R_q^k\)~\\
\outputText Recover \(\vec{s}\)

\end{frame}

%----------------------------------------------------------------------------------
\begin{frame}{Module-LWE -- A Closer Look}
\begin{figure}
\centering
\begin{tikzpicture}[scale=0.9, every node/.style={transform shape}]
    % Matrix A
    \fill[gray!30] (0,0) rectangle (3,2);
    \draw[thin] (0,0) rectangle (3,2);
    \node at (1.5,1) {\Large $\mat{A}$};

    % Secret s vector
    \fill[blue!30] (3.2,0) rectangle (3.5,2);
    \draw[thin] (3.2,0) rectangle (3.5,2);
    \node at (3.35,1) {\Large $\vec{s}$};


    \node at (4.3,1) {\Large $~+~$};

    % Error e vector
    \fill[red!30] (4.6,0) rectangle (4.9,2);
    \draw[thin] (4.6,0) rectangle (4.9,2);
    \node at (4.75,1) {\Large $\vec{e}$};

  
    \node at (5.7,1) {\Large $~=~$};

    % Output b vector
    \fill[green!30] (6,0) rectangle (6.3,2);
    \draw[thin] (6,0) rectangle (6.3,2);
    \node at (6.15,1) {\Large $\vec{b}$};

    % Dimensions
  \draw [<->,gray] (-0.2,2) -- (-0.2,0) node[midway,xshift=-10pt] {\large $n$};
    \draw [<->,gray] (0,-0.2) -- (3,-0.2) node[below,midway] {\large $k$};

    \draw [<->,gray] (3.7,2) -- (3.7,0) node[right,midway,xshift=-2pt] {\large $k$};
    \draw [<->,gray] (3.1,-0.2) -- (3.6,-0.2) node[below, midway] {\large $1$};

    \draw [<->,gray] (5.1,2) -- (5.1,0) node[right,midway,xshift=-2pt] {\large $n$};
    \draw [<->,gray] (4.5,-0.2) -- (5,-0.2) node[below, midway] {\large $1$};

    \draw [<->,gray] (6.5,2) -- (6.5,0) node[right,midway,xshift=-2pt] {\large $n$};
    \draw [<->,gray] (5.9,-0.2) -- (6.4,-0.2) node[below, midway] {\large $1$};
    \end{tikzpicture}
\end{figure}
\vspace{1em}

\notehead:~Some formulations explicitly sample $\vec{s}$ from a distribution $\chi_s$ (e.g.~discrete Gaussian or binomial); others assume $\vec{s}$ is uniform in $R_q^k$
\vspace{1em}
\pause

\subheadwo{Comparison with Ring-LWE:}~\\
\begin{itemize}
\item Ring-LWE is a special case of M-LWE when $k = 1$
\end{itemize}
\end{frame}

%----------------------------------------------------------------------------------
%----------------------------------------------------------------------------------
\begin{frame}{Hardness of Module-LWE}
Langlois \& Stehl\'{e} \cite{LS2015} showed that 
\[
  \text{Module-SIVP}_\gamma \;\leq_{\text{quantum polytime}}\; \text{M-LWE}_{q,n,k,\chi}
\]

\begin{itemize}
\item If $\text{M-LWE}_{q,n,k,\chi}$ can be solved efficiently, 
then worst-case $\text{Module-SIVP}_\gamma$ can also be solved efficiently 
(by a quantum polynomial-time algorithm)
\end{itemize}

\end{frame}


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

\begin{frame}{Efficiency of Module-LWE}
Storage cost in Module-LWE is $O(n \cdot k)$
\vspace{1em}

\pause
NIST-standard CRYSTALS-Kyber (key encapsulation mechanism) and CRYSTALS-Dilithium (signature) both rely on Module-LWE
\vspace{1em}
\pause 

\examw~\\ In CRYSTALS-Kyber 512, the M-LWE parameters used are: $n=k=2$, $f(x)=X^{256} + 1$, and $q=3329$

\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------
\begin{frame}{Decisional Module-LWE -- Definition}
The setup is similar to search M-LWE

\vspace{1em}
\pause

\headdwo{Decisional Module-LWE (D-M-LWE)}: The problem $(\text{D-M-LWE}_{q,n,k,\chi})$ is to \textbf{distinguish} between:
\[
(\mat{A}, \vec{b} = \mat{A} \vec{s} + \vec{e}),
\]

for a secret $\vec{s} \in R_q^k$, an error vector $\vec{e} \in R_q^n$ with entries independently sampled from $\chi$, and $\mat{A}$ is a uniformly random matrix over $R_q^{n \times k}$; and

\[
(\mat{A}, \vec{b}) \in R_q^{n \times k} \times R_q^n
\]

sampled uniformly at random
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\begin{frame}{Main Takeaways}
\vspace{-0.9mm}
    \begin{itemize}
        \item \headdwo{Worst-Case vs. Average-Case Problems:}
        \begin{itemize}
            \item Worst-case: Focus on the hardest instances (e.g., SVP)
            \item {Average-case}: Focus on typical instances (e.g., SIS)
        \end{itemize}
        
        \item \headdwo{Shortest Vector Problem (SVP):}
        \begin{itemize}
            \item Finding the shortest non-zero vector in a lattice
        \end{itemize}

        \item \headdwo{Closest Vector Problem (CVP):}
        \begin{itemize}
            \item Finding the closest lattice vector to a given point
   
          \end{itemize}

        \item \headdwo{Short Integer Solution( SIS):}
        \begin{itemize}
            \item Finding short integer solutions to modular equations
        \end{itemize}

        \item \headdwo{Learning With Errors (LWE):}
        \begin{itemize}
            \item Recovering a secret vector from noisy linear equations
        \end{itemize}
        
   \item \headdwo{Ring Learning With Errors (R-LWE):}  A variant of LWE defined over polynomial rings
  \begin{itemize}
    \item Recovering a secret polynomial from noisy polynomial equations
  \end{itemize}
  
  \item \headdwo{Module Learning With Errors (M-LWE):} A generalization of LWE and R-LWE that balances efficiency and security across modules

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

\begin{frame}
\frametitle{Additional Resources  \& Reading }
\begin{itemize}
\item D. Micciancio. Efficient reductions among lattice problems. In ACM-SIAM symposium on Discrete algorithms (SODA), 2008.
\end{itemize}
\end{frame}
%------------------------------------------------------------------------------------
%------------------------------------------------------------------------------------

\setbeamertemplate{bibliography item}[text]
\hypersetup{
    colorlinks=true,    % Enable colored links
    linkcolor=blue,     % Set link color (Table of Contents, internal links)
    citecolor=blue      % Set citation color
}

\begin{frame}{References}
\small
    \begin{thebibliography}{9}  

        \bibitem{Ajt1996} 
        M. Ajtai. 
        Generating hard instances of lattice problems.
        In \textit{Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing (STOC)}, 1996.

        \bibitem{BLP+2013}
        Z. Brakerski, A. Langlois, C. Peikert, O. Regev,  D. Stehl\'{e}. Classical hardness of learning with errors. 
        In \textit{ACM symposium on Theory of Computing (STOC)}, 2013.
 
		\bibitem{LS2015}
		A. Langlois, D. Stehl\'{e}. 
		{Worst-Case to Average-Case Reductions for Module Lattices}, 
		In \textit{Designs, Codes and Cryptography}, 2015.

		\bibitem {LPR2010} 
		V. Lyubashevsky, C. Peikert, O. Regev. 
		On ideal lattices and learning with errors over rings. 
		In \textit{Eurocrypt}, 2010.
		
	    \bibitem {LPR2013} 
		V. Lyubashevsky, C. Peikert, O. Regev. 
		On ideal lattices and learning with errors over rings. 
		In \textit{J. ACM}, 2013.

		\bibitem {Reg2009}  O. Regev. 
		On lattices, learning with errors, random linear codes, and cryptography. 
		In \textit{J. ACM 56, 6}, 2009.
   \end{thebibliography}
\end{frame}


\end{document}

