\documentclass[12pt]{article}
\usepackage{amsmath,amssymb}
\usepackage{graphicx}
\author{89010900 Jine-chen Gao, 89013900 En-ran Zhou}
\title{Introduction to Knapsack Cipher}
\begin{document}
\maketitle

\section{What's Knapsack problem}
Let $A = (a_1, a_2, \ldots, a_n)$ be an integer sequence with $a_i > 0, \forall i$, $S$ be a nonnegtive integer, and $X = (x_1, x_2, \ldots, x_n)$ be a binary sequence.  Given $A$ and $S$ find $X$ such that
\begin{displaymath}
S = \sum a_i x_i = A \cdot X
\end{displaymath}

\section{Which sequences are easy to solve}
\subsection{Superincreasing sequence}
A sequence $A = (a_1, a_2, \ldots. a_n)$ is called a {\em Superincreasin sequence} if
\begin{displaymath}
1 \leq i \leq n, a_i > \sum_{j=1}^{i-1}a_j.
\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}

\subsection{Graham-Shamir sequence}
skip.

\subsection{Laih-Gau sequence}
skip.

\section{Mekle-Hellman knapsack}
\subsection{Key generation}
Let $A$ be a superincreasing sequence, select $m$ where $m > \sum a_i$ and $w$ where $gcd(w, m) = 1$, then we can calculate $w^{-1}$ and $B = (b_1, b_2, \ldots, b_n)$ where $b_i = a_i \cdot w \mod m$.  Now $A$, $m$, $w^{-1}$ is private key, and $B$ is public key.

\subsection{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).

\subsection{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}

\subsection{Basic flow}
\includegraphics[scale=0.8]{mh.eps}

\subsection{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}

\subsection{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.

\section{Other Knapsack problems}
skip.

\section{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}
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}, \therefore 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.

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

\subsection{Encryption}
$S = \sum e_ix_i$

\subsection{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
\begin{displaymath}
0 \leq \sum(q_ix_i) \leq y \leq n, y = \sum q_i
\end{displaymath}
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.

\section{Conclusion}
skip.

\section{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}

\end{document}