\input{template}
\begin{document}
\homeworks{1}{September 15, 2020, 11:59pm AoE}
\section{Problem 1 (20 points)}
Consider the following encryption scheme. The key will be a table such as
{
\makeatletter
\newcommand{\thickhline}{%
\noalign {\ifnum 0=`}\fi \hrule height 1pt
\futurelet \reserved@a \@xhline
}
\newcolumntype{"}{@{\hskip\tabcolsep\vrule width 1pt\hskip\tabcolsep}}
\makeatother
\begin{table}[h]\centering
\begin{tabular}{|c"c|c|c|c|c|c|c|c|c|c|}\hline
& 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\\thickhline
& g & z & a & & t & k & f & w & & s \\\hline
3 & c & m & e & . & b & x & p & u & h & y \\\hline
8 & i & d & v & r & \textunderscore & q & j & l & n & o\\\hline
\end{tabular}
\end{table}
}
The plaintext alphabet will consist of the 26 letters, plus spaces (represented by \textunderscore) and periods. In general, the table will have the following form. It will consist of 4 rows. The numbers 0-9 are always written in the first row, in increasing order. We will call these the column indices. Then 8 plaintext characters are placed in the first row, leaving two black spot. The numbers from the first row corresponding to those blank spots (in our example, 3 and 8) are then written in the third and forth row of the first column, again in increasing order. These will be called the row indices. The remaining 20 characters fill out the rest of the third and fourth row.
Encryption is character by character. For each character, find the character in the table. There are two cases:
\begin{itemize}
\item If the character is in the second row (the first row of non-numbers), that character is encrypted by its column index. So, for example, ``a'' becomes ``2''.
\item If the character is in the third or fourth row, that character is encrypted by its row index followed by its column index. So ``x'' gets encrypted as ``35''.
\end{itemize}
The overall ciphertext is just the concatenation of the encryptions of each letter. So for example, ``attack.'' is encrypted to ``2\enspace 4\enspace 4\enspace 2\enspace 30\enspace 5\enspace 33''. The spaces between the numbers are just to show how the various letters map to numbers; in reality the actually ciphertext would be ``244230533'' with no spaces.
\begin{itemize}
\item[(a)] Explain how to decrypt. Explain for general keys, not just the key given above.
\item[(b)] How many possible keys are there?
\item[(c)] Explain why vanilla frequency analysis wont work. What about frequency analysis using digrams? What are the features of this scheme that lead to this conclusion? You do not need to prove anything; just an intuitive explanation.
\item[(d)] A friend suggests putting characters such as ``a'', ``e'', ``i'', ``o'', ``r'', ``t'' and maybe ``\textunderscore'' in the second row. What \emph{non-security} reasons might your friend have for this suggestion? Do you think this suggestion will help or hurt security, compared to a random placement of characters. (This problem is meant to be open ended)
\end{itemize}
\section{Problem 2 (20 points)}
Sometimes data is lost or corrupted in transit. Suppose Alice encrypts a message $m$, and transmits the ciphertext $c$ to Bob. However, in route to Bob, the $i$th ciphertext character gets deleted, and Bob only receives $c'$ which is $c$ with the $i$th character deleted. Bob does not know which character was deleted, or even that any character was deleted. When Bob decrypts, he will then get a different message $m'$. Hopefully, $m'$ is not to different from $m$, so that Bob still learns the bulk of the desired message.
\begin{itemize}
\item[(a)] In the case of a simple substitution cipher, what is the impact of deleting a single ciphertext character on $m'$? Explain.
\item[(b)] What about polygraphic substitution? Explain.
\item[(c)] What about the Vigen\`ere cipher? Explain.
\item[(d)] Let $\Sigma=\{a,b,c,\dots,z\}$. Let $\mathcal{M}=\Sigma^\ell$ and $\mathcal{C}=\Sigma^n$ for some integers $\ell,n$. Suppose you have an encryption scheme $\enc,\dec$ with message space $\mathcal{M}$ and ciphertext space $\mathcal{C}$ that is guaranteed to be correct. Let $\enc_2(k,m)$ do the following encryption algorithm with message space $\mathcal{M}$ and ciphertext space $\mathcal{C}_2=\Sigma^{2n}$: first compute $c=\enc(k,c)$, and then output $c_2=c||c$ (that is, $c_2$ is just $c$ printed twice).
Devise a decryption algorithm $\dec_2$ with the following guarantee. If $c_2=\enc_2(k,m)$ and $c_2'$ is obtained from $c_2$ by deleting any single character, then $\dec_2(k,c_2')=m$. This must hold regardless of the choice of $m$ or the position of the deleted character. Your $\dec_2$ will run $\dec$ as a subroutine. You do not need to analyze the security of $(\enc_2,\dec_2)$.
\item[(e)] Suppose instead we tried the following transformation: $\enc_3(k,m)=\enc(k,m||m)$. Here, $\enc_3$ has message space $\Sigma^{\ell/2}$ (we assume $\ell$ is even) and ciphertext space $\Sigma^n$, and we encrypt by writing down the message twice, and then encrypting the entire repeated message.
Show that this transformation does \emph{not} in general achieve the desired property. To do so, you will give a concrete example of an encryption scheme $(\enc,\dec)$. To keep things simple, your scheme $(\enc,\dec)$ does not actually need to be secure, but it must be correct. Then you will plug $(\enc,\dec)$ into the conversion above to obtain $\enc_3$. Now Alice chooses a uniformly random message $m\in\Sigma^{\ell/2}$, computes $c_3=\enc_3(k,m)$, and then Bob receives $c_3'$, which is $c_3$ with a the $i$th character deleted, for some $i$. You must show that there are some $i$ such that Bob will be unable to compute $m$ with certainty, no matter what decryption algorithm he may be using. (Bob gets to know the key $k$).
\end{itemize}
\section{Problem 3 (20 points)}
\begin{itemize}
\item[(a)] Show that a Homophonic substitution cipher that encrypts a single character at a time can \emph{never} have perfect secrecy, even for two-character messages, no matter how large the output alphabet is. That is, provide two different two-character messages such that the distributions of encryptions of those two messages are different, regardless of the ciphertext alphabet size or the exact mappings between characters.
\item[(b)] Show that the Vigen\`ere cipher does \emph{not} have perfect secrecy if the message length is even one character longer than the key length.
\item[(c)] Show that the Vigen\`ere cipher does \emph{not} have perfect secrecy if the keyspace is grammatically correct English, even if the message length is smaller than the key length.
\item[(d)] Show that the following cipher has perfect secrecy. Messages are $\ell$ bit strings. The key is a random permutation $P$ on $2\ell$ items. To encrypt a message $m$, write down $m$, followed by $\overline{m}$, the bitwise complement of $m$. Then permute the bits of the resulting $2\ell$-bit string $m||\overline{m}$ according to the permutation described by the key. To decrypt, perform the inverse permutation to recover $m||\overline{m}$ and discard $\overline{m}$.
\item[(e)] What happens in part (d) we replace $\overline{m}$ with $0^\ell$ (here, $0^\ell$ denotes a sequence of $\ell$ zeros). That is, we apply the permutation $P$ to the $2\ell$-bit string $m||0^\ell$. Is the scheme still correct? Is it still secure? Prove why or why not.
\end{itemize}
\section{Problem 4 (20 points)}
\begin{itemize}
\item[(a)] Devise an encryption scheme such that (1) given an encryption of any message, an adversary can figure out 90\% of the secret key, but (2) the scheme is still perfectly secure, despite 90\% of the key being revealed. Do not forget to prove that the scheme is secure and that it is correct.
\item[(b)] Devise an encryption scheme such that (1) given an encryption of any message, an adversary learns \emph{nothing} about the secret key, but (2) the scheme is completely broken (as in, given the ciphertext, an adversary can completely recover the plaintext).
\end{itemize}
\end{document}