\documentclass[ps,pdf,slideColor,colorBG,rico]{prosper}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\usepackage{hyperref}
\title{Introduction to Knapsack Cipher}
\author{89010900 Jine-chen Gao, 89013900 En-ran Zhou}
\institution{On the security of Knapsack PKC, Chi Sung Laih\\
The Rise and Fall of Knapsack Cryptosystems, A. M. Odlyzko}
\DefaultTransition{Replace}

\begin{document}
\maketitle
\begin{slide}{Outline}
\begin{itemize}
\item{What's Knapsack problem}
\item{Easy sequences}
\item{Mekle-Hellman knapsack PKC}
\item{Shamir-Zippel attack}
\item{Low Density}
\item{Generate High Density Sequence}
\item{Linear Shift Knapsack PKC}
\item{Reference and Acknowledgement}
\end{itemize}
\end{slide}

\begin{slide}{What's Knapsack problem}

\begin{itemize}
\item $S$ be a nonnegtive integer
\item $A = (a_1, a_2, \ldots, a_n)$ be an integer sequence with $a_i > 0$
\item $X = (x_1, x_2, \ldots, x_n)$ be a binary sequence.
\end{itemize}

\vskip 0.2in
Given $A$ and $S$ to find $X$ such that
\begin{displaymath}
S = \sum a_i x_i = A \cdot X
\end{displaymath}

\vskip 0.2in
\em{Note: Knapsack is a NP-Complete problem.}
\end{slide}

\begin{slide}{Easy sequences}

\begin{itemize}
\item{Superincreasing sequence}
\item{Graham-Shamir sequence}\\skip.
\item{Laih-Gau sequence}\\skip.
\end{itemize}

\vskip 0.2in
\em{Note:}
Generally speaking, it's easy to calculate $S$ when given $A$ and $X$, but given $A$ and $S$ to find $X$ is really hard.

\end{slide}

\begin{slide}{Superincreasing sequence}
A sequence $A = (a_1, a_2, \ldots. a_n)$ is called a {\em Superincreasing sequence} if
\begin{displaymath}
a_i > \sum_{j=1}^{i-1}a_j,\quad 1 \leq i \leq n.
\end{displaymath}
Then let $A$ be superincreasing sequence and $S = \sum a_ix_i$, we can solve $X$ easily by
\begin{displaymath}
x_i = \left\{
\begin{array}{ll}
1 & \text{if\,} (S - \sum_{j=i+1}^{n}a_jx_j) > a_i , \\
0 & \text{otherwise.}
\end{array}\right.
\end{displaymath}
\end{slide}

\begin{slide}{Example}
Given
\begin{itemize}
\item{$A = (1, 2, 4, 8, 16, 32, 64, 128)$\quad Superincreasing sequence}
\item{$S = 157$}
\end{itemize}
We can easily find $X = (1, 0, 1, 1, 1, 0, 0, 1)$

\vskip 0.2in
But givem
\begin{itemize}
\item{$A = (53, 2, 57, 61, 81, 1)$}
\item{$S = 115$}
\end{itemize}
is hard to solve.

\end{slide}

\begin{slide}{Mekle-Hellman knapsack PKC}
\begin{itemize}
\item{Key generation}
\item{Encryption}
\item{Decryption}
\item{Choosing parameters}
\item{Security}
\item{Basic flow}
\item{Example}
\end{itemize}
\end{slide}

\begin{slide}{Key generation}

\begin{itemize}
\item $A$ be a superincreasing sequence
\item $m > \sum a_i$
\item $w$ where $gcd(w, m) = 1$
\item $w^{-1}$ where $w^{-1} \cdot w \mod m = 1$
\item  $B = (b_1, b_2, \ldots, b_n)$ where $b_i = a_i \cdot w \mod m$
\end{itemize}

\vskip 0.2in
\em{Note:}
\begin{itemize}
\item $A$, $m$, $w^{-1}$ is private key
\item $B$ is public key
\end{itemize}

\end{slide}

\begin{slide}{Encryption and Decryption}
\begin{itemize}
\item{Encryption}\\
Assume the message to transmit is plaintext $X = (x_1, x_2, \ldots, x_n)$, we can calculate the ciphertext $S = \sum b_ix_i$, and transfer $S$ to receiver(who owns private key).
\item{Decryption}\\
When receiver get the ciphertext $S$, let $S' = S \cdot w^{-1} \mod m$, receiver can obtain plaintext $X$ by calculate
\begin{displaymath}
x_i = \left\{
\begin{array}{ll}
1 & \text{if\,} (S' - \sum_{j=i+1}^{n}a_jx_j) > a_i , \\
0 & \text{otherwise.}
\end{array}\right.
\end{displaymath}
\end{itemize}
\end{slide}

\begin{slide}{Choosing parameters and Security}
\begin{itemize}
\item{Choosing parameters}\\
\begin{itemize}
\item{$n = 100$}
\item{$a_i \in [(2^{i - 1} - 1)\cdot 2^{100} + 1, 2^{i - 1} \cdot 2^{100}]$}
\item{$m \in [2^{201} + 1, 2^{202} - 1]$}
\item{$w \in [2, m - 2]$ and $gcd(w, m) = 1$}
\end{itemize}

\item{Security}\\
Schroeppel-Shamir algorithm can solve knapsack problem with time $T = O(2^{\frac{n}{2}})$ and Space $S = O(2^{\frac{n}{4}})$.  If $n = 200$, the algorithm is computationally infeasible.
\end{itemize}
\end{slide}

\begin{slide}{Basic flow}
\includegraphics{mh.eps}
\end{slide}

\begin{slide}{Example}
\begin{itemize}
\item{$A = (2, 3, 6, 12, 25)$}
\item{$m = 53 > \sum a_i = 48$}
\item{$w = 46, w^{-1} = 15$}
\item{$B = F(A) = (39, 32, 11, 22, 37)$\quad$b_i = a_i \cdot w \mod m$}
\end{itemize}
$B$ is public key, and $A$, $m$, $w^{-1}$ is private key.

\vskip 0.2in
Assume the message to send is $X = (1, 1, 1, 0, 1)$, then we can calculate and send $S = B \cdot X = 39 + 32 + 11+ 37 = 119$
\end{slide}

\begin{slide}{Example continued}
After received $S$, Let $S' = S \cdot w^{-1} \mod m = 119 \cdot 15 \mod 53 = 36$

\begin{align}
36 \geq 25 & \Rightarrow x_5 = 1\\
36 - 25 = 11 < 12 & \Rightarrow x_4 = 0\\
11 \geq 6 & \Rightarrow x_3 = 1\\
11 - 6 = 5 \geq 3 & \Rightarrow x_2 = 1\\
5 - 3 = 2 \geq 2 & \Rightarrow x_1 = 1\\
& \Rightarrow X = (1, 1, 1, 0, 1)
\end{align}
\end{slide}

\begin{slide}{Shamir-Zippel attack}
If $m$ is known, than we can find
\begin{displaymath}
q = \frac{b_1}{b_2} = \frac{a_1w}{a_2w} = \frac{a_1}{a_2}\mod m,
\end{displaymath}
or
\begin{displaymath}
a_1 = a_2q \mod m.
\end{displaymath}
Consider the set
\begin{displaymath}
Z = \lbrace 1 \cdot q\mod m, 2 \cdot q\mod m, \ldots, 2^{101} \cdot q\mod m\rbrace
\end{displaymath}
\end{slide}

\begin{slide}{Shamir-Zippel attack continued}
All these $2^{101}$ multiples are very evenly distributed in the interval $[0, m - 1]$, thus the smallest number among then is likely to be around
\begin{displaymath}
\frac{m}{2^{101}} \approx 2^{101}, a_1 \leq 2^{100},
\end{displaymath}
Thus, $a_1$ is likely to be one of the smallest number in $Z$. By using the {\em continued fraction approximation} of the ratio $\frac{q}{m}$, we can find $a_1$ and then break the system.
\end{slide}

\begin{slide}{Example}
\begin{itemize}
\item{$A = (171, 196, 457, 1191, 2410)$}
\item{$m = 8443 > \sum a_i$}
\item{$w = 3950, w^{-1} = 2550$}
\item{$B = (5457, 1663, 216, 6013, 7439)$}
\item{$S = 15115$}
\end{itemize}

\vskip 0.2in
\em{Note:}$B$ is public key, and $S$ may get by others.
\end{slide}

\begin{slide}{Example continued}
After get $B$ and $C$
\begin{itemize}
\item{$c_i = b_i \cdot 46 \mod 77$}
\item{$C = (2, 37, 3, 14, 6)$}
\item{$C' = (2, 3, 6, 14, 37)$ reorder from $C$}
\item{$S' = 46 \cdot 15115 \mod 77 = 57$}
\end{itemize}

\vskip 0.2in
We can get $X' = (0, 0, 1, 1, 1)$ by using $C'$, after reorder we can get $X = (0, 1, 0, 1, 1)$

\vskip 0.2in
\em{Note:}private key $A$ is not necsessary.

\end{slide}

\begin{slide}{Low Density}
\begin{displaymath}
Density = \frac{n}{\log_2(\max b_i)}
\end{displaymath}

\vskip 0.2in
In MH knapsack system, for most knapsack problem with low density ($density < \frac{1}{2}$) can be solved by \em{LLL algorithm}.
\end{slide}

\begin{slide}{Generate High Density Sequence}
Let
\begin{itemize}
\item{$A'$ is superincreasing sequence}
\item{$b'_i = a'_i \cdot w \mod m$}
\item{$c_i = \lfloor\frac{b'_i}{w}\rfloor$}
\end{itemize}
then we can calculate
\begin{itemize}
\item{$a_i = a'_i - c_i$}
\item{$b_i = b'_i \mod w$}
\end{itemize}
\end{slide}

\begin{slide}{Example}
\begin{itemize}
\item{$A' = (111, 189, 445, 770, 2399, 4325)$}
\quad$a_i > \sum_{j=1}^{i-1}a_j + v$
\item{$w = 259$}
\item{$m = 8443$}
\quad$\lfloor\frac{m}{w}\rfloor = v = 32$
\item{$B' = (3420, 6736, 5496, 5421, 5002, 5699)$}
\item{$C = (13, 26, 21, 20, 19, 22)$}
\quad$c_i = \lfloor\frac{b_i}{w}\rfloor$
\item{$A = (98, 163, 424, 750, 2380, 4303)$}
\quad$a_i = a'_i - c_i$
\item{$B = (53, 2, 57, 241, 81, 1)$}
\quad$b_i = b'_i \mod w$
\end{itemize}
\end{slide}

\begin{slide}{Linear Shift Knapsack PKC}
\begin{itemize}
\item{Key generation}
\begin{itemize}
\item{$B$ is a high density knapsack sequence}
\item{$Q = (q_1, q_2, \ldots, q_n)$ is a random binary sequence}
\item{$k$ is a integer with $0 < k < min(b_i)$}
\end{itemize}
then then linearly shift $e_i = b_i - kq_i$ and $E = (e_1, e_2, \ldots, e_n)$ is the public key.

\item{Encryption}\\
$S = \sum e_ix_i$
\end{itemize}
\end{slide}

\begin{slide}{Linear Shift Knapsack PKC continued}
\begin{itemize}
\item{Decryption}
\begin{displaymath}
\begin{split}
S' & = \sum(b_ix_i)w^{-1} \mod m \\
   & = \sum((e_i + kq_i)x_i)w^{-1} \mod m \\
   & = \sum(e_ix_i)w^{-1} + \sum(q_ix_i)kw^{-1} \mod m\\
   & = Sw^{-1} + \sum(q_ix_i)kw^{-1} \mod m
\end{split}
\end{displaymath}
and $0 \leq \sum(q_ix_i) \leq y \leq n$ where $y = \sum q_i$.  Thus, we can guess the correct $S$ at most $y + 1 \leq n + 1$ times.  If the system is one-to-one, then we can decrypt x correctly.
\end{itemize}
\end{slide}

\begin{slide}{Reference and Acknowledgement}
\begin{itemize}

\item{Reference}
\begin{itemize}
\item{On the security of Knapsack PKC, Chi Sung Laih}
\item{The Rise and Fall of Knapsack Cryptosystems, A. M. Odlyzko}
\end{itemize}

\item{Acknowledgement}
\begin{itemize}
\item{\href{http://www-cs-faculty.stanford.edu/~knuth/}{Donald E. Knuth} -- the author of \TeX typesetting system}
\item{\href{http://www.latex-project.org/}{\LaTeX} -- a TeX macro system}
\item{\href{http://prosper.sourceforge.net/}{Prosper} -- a macro to create slide for \LaTeX}
\end{itemize}

\end{itemize}
\end{slide}

\end{document}