2017-04-19-081147.tex

 
\documentclass{beamer}

\usetheme{Madrid}
\usepackage{graphicx}


\definecolor{MyLightMagenta}{cmyk}{0.1,0.8,0,0.1}

\title{Gr\"obner Basis and Their Applications}


\author{MIDN 1/ C Ben Liu, USNA 
\\advised by Professor S. Margulies}


\institute[United States Naval Academy] 
{
  Department of Mathematics\\
  United States Naval Academy
}


\date{Service Academy Student Mathematics Conference, 2017}


\subject{Theoretical Computer Science}

\AtBeginSubsection[]


\begin{document}

\begin{frame}
  \titlepage
\end{frame}

\begin{frame}
\includegraphics[width=12cm, height=6cm]{picture1}
\end{frame}

\begin{frame}
\includegraphics[width=12cm, height=6cm]{picture2}
\end{frame}

\begin{frame}\frametitle{Overview of Public-Key Cryptography}
\[
\begin{array}{c||c||c}
\text{Alice} & \text{Public} & \text{Bob}\\ \hline\
{\Big( \text{Key}_{\text{private}},  \text{Key}_{\text{public}} \Big)} &  & \\
\text{Key}_{\text{public}} \Longrightarrow& \text{Key}_{\text{public}} & \\
 & & \text{plaintext}\\
& & \downarrow\\
& & \textbf{encrypt with } \text{Key}_{\text{public}}\\
& & \downarrow\\
\text{ciphertext} &\Longleftarrow \text{ciphertext} & \Longleftarrow \text{ciphertext}\\
 \downarrow & & \\
\textbf{decrypt with } \text{Key}_{\text{private}} & & \\
 \downarrow & & \\
 \text{plaintext} & &\\
& (Eve) &
\end{array}
\]
\end{frame}

\begin{frame}\frametitle{Overview of Public-Key Cryptography}
\[
\begin{array}{c||c||c}
\text{Alice} & \text{Public} & \text{Bob}\\ \hline\
{\Big( \text{Key}_{\text{private}},  \text{Key}_{\text{public}} \Big)} &  & \\
\text{Key}_{\text{public}} \Longrightarrow& \text{Key}_{\text{public}} & \\
 & & \text{plaintext}\\
& & \downarrow\\
& & \textbf{encrypt with } \text{Key}_{\text{public}}\\
& & \downarrow\\
\text{ciphertext} &\Longleftarrow \text{ciphertext} & \Longleftarrow \text{ciphertext}\\
 \downarrow & & \\
\textbf{decrypt with } \text{Key}_{\text{private}} & & \\
 \downarrow & & \\
 \text{plaintext} & &\\
& (Eve) &
\end{array}
\]
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
\text{Let us have a plaintext $\overline{x} = \{x_1, x_2,..., x_n\}$ that resides in the finite field $\mathbb{F}_2$} \\
\vspace{20pt}
\uncover<2->{
\textbf{Example:}
\begin{align*}
\{x_1, x_2,..., x_n\} &= \{1,0,0,...,1\}
\end{align*}}
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
\text{The first thing we do is set $\overline{u} = A\overline{x} + \overline{c}$} 
where A is a $n \times n$ invertible matrix and c is a constant vector of length $n$\\
\vspace{20pt}
\uncover<2->{
\textbf{Example:}
\[A = \left( \begin{array}{ccc}
1 & 0 & 1\\
0 & 1 & 1\\
0 & 0 & 1\end{array} \right)\]
\vspace{.3cm}
\[ \bar{c}= (1,0,0) \]
\begin{align*}
u_1 &= x_1 + x_3 + 1 
\\u_2 &= x_2 + x_3
\\u_3 &= x_3
\end{align*}}
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
We then set the $\overline{u}$ values as the coefficients of the indeterminates in a quotient ring $\mathbb{K}$ with basis $\{1, X^1, X^2, ..., X^{n-1}\}$ modulo an irreducible polynomial $f(X)$ and denote $\textbf{u} = u_1 + u_2X + u_3X^2 + ... + u_nX^{n-1}$.\\
\vspace{20pt}
\uncover<2->{
\textbf{Example:}
\begin{center}
$f(X) = X^3 + X^2 + 1$
\end{center}
\begin{align*}
\textbf{u} = (x_1 + x_3 + 1) +  (x_2 + x_3)X +  (x_3)X^2
\end{align*}}
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
We raise $\textbf{u}$ to a certain exponent $h$ and denote $\textbf{v} = \textbf{u}^h$.\\
\vspace{20pt}
\uncover<2->{
\textbf{Example:}
\begin{align*}
\textbf{v} = &(x1^2 + x1*x2 + x1*x3 + x2^2 + x2*x3 + x2 + x3 + 1)\\ &+ (x1*x3 + x2^2 + x2*x3 + x3^2 + x3)X\\  &+ (x1*x2 + x2*x3 + x2 + x3^2)X^2
\end{align*}}
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
We set $\overline{v}$ as the coefficients of $\textbf{v}$\\
\vspace{20pt}
\uncover<2->{
\textbf{Example:}
\begin{align*}
v_1 &= x1^2 + x1*x2 + x1*x3 + x2^2 + x2*x3 + x2 + x3 + 1 
\\v_2 &= x1*x3 + x2^2 + x2*x3 + x3^2 + x3
\\v_3 &= x1*x2 + x2*x3 + x2 + x3^2
\end{align*}}
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
We establish $\overline{y} = B^{-1}(\overline{v}-\overline{d})$, where 
$B^{-1}$ is the inverse of a $n \times n$ matrix $B$ and $\overline{d}$ is a constant vector of length $n$.\\
\vspace{20pt}
\uncover<2->{
\textbf{Example:}
\[B^{-1} = \left( \begin{array}{ccc}
1 & 1 & 1\\
1 & 1 & 0\\
0 & 1 & 1\end{array} \right)\]
\vspace{.3cm}
\[ \bar{d}= (0,1,0) \]
\begin{align*}
y_1 &= x_1^2 + x_2x_3 
\\y_2 &= x_1^2 + x_1x_2 + x_2 + x_3^2
\\y_3 &= x_1x_2 + x_1x_3 + x_2^2 + x_2 + x_3 + 1
\end{align*}}
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
In Summary:
\begin{center}
$x_1,...,x_n$
\pause
\\$\Downarrow$
\\$\bar{u}$ = A$\bar{x}$ + $\bar{c}$
\pause
\\$\Downarrow$
\\$\textbf{u}$ = $\sum$ $u_iX^{i-1}$
\pause
\\$\Downarrow$
\\$\textbf{v} = \textbf{u}^{h}$
\pause
\\$\Downarrow$
\\$\bar{y}$ = $B^{-1}(\bar{v} - \bar{d}$).
\end{center}
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
Rules:
\begin{center}
$0 \leq \theta \leq n-1$ 
\vspace{.5cm}
\\$q$ is a power of 2, where $\mathbb{F}_q$ is the finite field we are working in
\vspace{.5cm}
\\The exponent $h$, $0 \leq h \leq q^n$, is of the form \\$h = q^{\theta} + 1$
and satisfies the condition g.c.d.($h,q^n - 1$) = 1
\end{center}
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
\begin{center}
Let $\theta = 2$, $q = 2$, $h = 5$,
\\the quotient ring is modulo the irreducible polynomial $f(X) = X^3 + X^2 + 1$
\[A = \left( \begin{array}{ccc}
1 & 0 & 1\\
0 & 1 & 1\\
0 & 0 & 1\end{array} \right), \hspace{.5cm}
B = \left( \begin{array}{ccc}
1 & 0 & 1\\
1 & 1 & 1\\
1 & 1 & 0\end{array} \right) \]
\[ \bar{c}= (1,0,0) , \hspace{1cm}  \bar{d}= (0,1,0). \]
\end{center}
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
\begin{center}
Public Key:
\end{center}
\begin{align*}
y_1 &= x_1^2 + x_2x_3 
\\y_2 &= x_1^2 + x_1x_2 + x_2 + x_3^2
\\y_3 &= x_1x_2 + x_1x_3 + x_2^2 + x_2 + x_3 + 1
\end{align*}
\begin{center}
plaintext: (0,1,0) $\Rightarrow$ ciphertext: (0,1,1)
\end{center}  
\end{frame}

\begin{frame}
Alice's Decryption:
\begin{center}
$y_1,...,y_n$
\pause
\\$\Downarrow$
\\$\bar{v}$ = B$\bar{y}$ + $\bar{d}$
\pause
\\$\Downarrow$
\\$\textbf{v}$ = $\sum$ $v_iX^{i-1}$
\pause
\\$\Downarrow$
\\$\textbf{u} = \textbf{v}^{h'}$
\pause
\\$\Downarrow$
\\$\bar{x}$ = $A^{-1}(\bar{u} - \bar{c}$).
\end{center}
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
Let $\textbf{R}$ be a ring, an $\textit{ideal}$ of $\textbf{R}$ is a subset of $\textbf{R}$ that is defined as a subset $I \subset \textbf{R}$ that satisfies:
\begin{align*}
(i)\thinspace &0 \in I.
\\(ii)\thinspace &\textit{If f, g} \in I, \textit{then f + g} \in I.
\\(iii)\thinspace &\textit{If f} \in \textit{I and h} \in \textbf{R}, \textit{then hf} \in I.
\end{align*}
An example of an ideal would be the multiples of 3 in ring of integers $\mathbb{Z}$. 
\vspace{.5cm}
\\$I = \{x_1^2 + x_2x_3, x_1^2 + x_1x_2 + x_2 + x_3^2 + 1, x_1x_2 + x_1x_3 + x_2^2 + x_2 + x_3 \}$
\end{frame}

\begin{frame}
\vspace{.5cm}
A finite subset $G$ = ${g_1,...g_t}$ of an ideal $I$ is said to be a $\textbf{Gr\"obner basis}$ if 
\begin{center}
$\langle LT(g_1),..., LT(g_t) \rangle = \langle LT(I) \rangle.$
\end{center}
\end{frame}

\begin{frame}
$\textbf{Theorem (Buchberger's Algorithm).}$ Let $I$ = $\langle f_1,..., f_s \rangle \neq {0}$ be a polynomial ideal. Then a Gr\"obner basis for $I$ can be constructed in a finite number of steps by the following algorithm:

Input: $F$ = ($f_1,...,f_s$)

Output: a Gr\"obner basis $G$ = ($g_1,..., g_t$) for $I$, with $F$ $\subset$ $G$
\vspace{.5cm}

$G$ := $F$

REPEAT

\hspace{1cm}$G'$ := $G$

\hspace{1cm}FOR each pair{$p,q$}, $p \neq q$ in $G'$ DO

\hspace{2cm}$S$ := $\overline{S(p,q)}^{G'}$

\hspace{2cm}IF $S \neq 0$ THEN $G := G \cup {S}$

UNTIL $G = G'$
\end{frame}

\begin{frame}
S-Polynomials
\vspace{.5cm}
Let $f,g \in k[x_1,..., x_n]$ be nonzero polynomials.
\begin{flushleft}
(i) If multideg($f$) = $\alpha$ and multideg($g$) = $\beta$, then let $\gamma = (\gamma_1,...,\gamma_n)$, where $\gamma_i =$ max($\alpha,\beta_i$) for each $i$. We call $x^{\gamma}$ the $\textit{least common multiple}$ of LM($f$) and LM($g$), written $x^{\gamma}$ = LCM(LM($f$),LM($g$)).
\\(ii) The $\textit{S-polynomial}$ of $f$ and $g$ is the combination
\end{flushleft}
\begin{center}
S($f,g$) = $\frac{x^{\gamma}}{LT(f)}\cdot f - \frac{x^{\gamma}}{LT(g)}\cdot g$
\end{center}
\uncover<2->{
\textbf{Example:}
\begin{center}

$f = x^3y^2 - x^2y^3 + x$ and $g = 3x^4y + y^2$

$S(f,g) = \frac{x^4y^2}{x^3y^2}\cdot f - \frac{x^4y^2}{3x^4y}\cdot g$

$S(f,g) = -x^3y^3 + x^2 - (1/3)y^3$
\end{center}}
\end{frame}

\begin{frame}
  But it is well-known that Gr\"obner bases cannot be found in polynomial time, even for low degree, and even for a small number of polynomials, even if $\textbf{P} = \text{NP}$. Gr\"obner bases are EXPSPACE-complete. Recall the known complexity class inclusions:
\begin{align*}
\text{P} \subseteq \text{NP} \subseteq \text{PSPACE} \subseteq \text{EXPTIME} \subseteq \text{NEXPTIME} \subseteq \text{EXPSPACE}
\end{align*}
Furthermore, by the time hierarchy theorem and the space hierarchy theorem, the following \emph{proper} inclusions are known (see Papadimitriou's Computational Complexity text as reference or \url{https://en.wikipedia.org/wiki/EXPTIME})
\begin{align*}
\text{P} \subsetneq \text{EXPTIME} \quad \text{and} \quad \text{NP} \subsetneq \text{NEXPTIME} \quad \text{and} \quad \text{PSPACE} \subsetneq \text{EXPSPACE}
\end{align*}
Therefore, it is known that \text{NP} is a \emph{proper} subset of EXPSPACE.  Therefore, even if $\textbf{P} = \text{NP}$, the complexity of finding a Gr\"obner bases would remain unchanged since \emph{exponential space is required to even write the bases down} in general.
\end{frame}

\begin{frame}{The Imai-Matsumoto System}
Gr\"obner Basis:
\begin{align*}
g_{1} &= x_2^4 + x_2^3x_3 + x_2x_3^3 + x_2x_3 + x_3^2 + 1\\g_{2} &=  x_1x_2 + x_1x_3 + x_2^2 + x_2 + x_3\\g_{3} &=  x_1^2 + x_2x_3\\g_{4} &=  x_1 + x_2^3 + x_2^2x_3 + x_3^3 + 1\\g_{5} &=  x_1^2 + x_1x_2 + x_2 + x_3^2 + 1\\g_{6} &=  x_1x_3 + x_2^2 + x_2x_3 + x_3^2 + x_3 + 1\\g_{7} &=  x_2^3x_3 + x_2^2x_3^2 + x_2^2 + x_2x_3 + x_3^4 + x_3^2 + 1\\g_{8} &=  x_2^6 + x_2^4x_3^2 + x_2^4 + x_2^3x_3 + x_2x_3^3 + x_3^6 + x_3^2\\g_{9} &=  x_2^2 + 1\\g_{10} &=  x_3
\end{align*}
\end{frame}

\begin{frame}
\begin{center}
Buchberger's Algorithm and S-Polynomials Analysis
\end{center}
\url{https://cloud.sagemath.com/projects/e92ee2f7-c8d2-4f13-bc73-d8b824e125f5/files/Presentation_example.sagews}
\end{frame}

\begin{frame}
Techniques for Crytanalysis:
\begin{center}
\vspace{.5cm}
Chosen Plaintext Attack
\pause

Examples where n = 2,3,5
\pause

Probability Testing for Random Invertible Matrices when n = 3
\pause

Examples with identity matrices and zero constant vectors
\pause

Manipulating irreducible polynomials, h, and monomial ordering
\pause

Going From Ciphertext to Plaintext
\end{center}
\end{frame}

\begin{frame}
\begin{center}
Thank you for your attention!
\end{center}
\end{frame}

\end{document}