%N999424
\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
\usepackage{graphicx}
%uncomment to get hyperlinks
%\usepackage{hyperref}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Some macros (you can ignore everything until "end of macros")
\def\class{0}
\topmargin 0pt \advance \topmargin by -\headheight \advance
\topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt \evensidemargin \oddsidemargin \marginparwidth
0.5in
\textwidth 6.5in
%%%%%%
\newcommand{\getsr}{\gets_{\mbox{\tiny R}}}
\newcommand{\bits}{\{0,1\}}
\newcommand{\bit}{\{0,1\}}
\newcommand{\Ex}{\mathbb{E}}
\newcommand{\To}{\rightarrow}
\newcommand{\e}{\epsilon}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\F}{\mathbb{F}}
\newcommand{\GF}{\mathsf{GF}}
\newcommand{\maxpr}{\text{\rm max-pr}}
\newcommand{\cclass}[1]{\mathbf{#1}}
\renewcommand{\P}{\cclass{P}}
\newcommand{\NP}{\cclass{NP}}
\newcommand{\PH}{\cclass{PH}}
\newcommand{\coNP}{\cclass{coNP}}
\newcommand{\AvgP}{\cclass{AvgP}}
\newcommand{\DTIME}{\cclass{DTIME}}
\newcommand{\BPP}{\cclass{BPP}}
\newcommand{\BQP}{\cclass{BQP}}
\newcommand{\NTIME}{\cclass{NTIME}}
\newcommand{\SIZE}{\cclass{SIZE}}
\newcommand{\Ppoly}{\cclass{P_{/poly}}}
\newcommand{\SPACE}{\cclass{SPACE}}
\newcommand{\PSPACE}{\cclass{PSPACE}}
\newcommand{\BPL}{\cclass{BPL}}
\newenvironment{summary}{\begin{quote}\textbf{Summary.}}{\end{quote}}
\newtheorem{theorem}{Theorem}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}{Claim}[theorem]
\theoremstyle{definition}
\newtheorem{exercise}{Exercise}
\newtheorem{definition}{Definition}
\newcommand{\sstart}{\triangleright}
\newcommand{\send}{\triangleleft}
\newcommand{\CSAT}{\ensuremath{\mathsf{CSAT}}}
\newcommand{\SAT}{\ensuremath{\mathsf{3SAT}}}
\newcommand{\IS}{\mathsf{INDSET}}
\newcommand{\poly}{\mathrm{poly}}
\newcommand{\inp}{\mathsf{in}}
\newcommand{\outp}{\mathsf{out}}
\newcommand{\Adv}{\mathsf{Adv}}
\newcommand{\Supp}{\mathsf{Supp}}
\newcommand{\dist}{\Delta}
\newcommand{\indist}{\approx}
\newcommand{\PRG}{\mathsf{G}}
\newcommand{\Enc}{\mathsf{E}}
\newcommand{\Dec}{\mathsf{D}}
\newcommand{\Fcal}{\mathcal{F}}
\newcommand{\Gen}{\mathsf{Gen}}
\newcommand{\Sign}{\mathsf{Sign}}
\newcommand{\Ver}{\mathsf{Ver}}
\newcommand{\Com}{\mathsf{Com}}
\newcommand{\angles}[1]{\langle #1 \rangle}
\newcommand{\eqdef}{\stackrel{\vartriangle}{=}}
\newcommand{\view}{\mathsf{view}}
\newcommand{\trans}{\mathsf{trans}}
\newcommand{\qstart}{q_{\text{\tiny start}}}
\newcommand{\qacc}{q_{\text{\tiny acc}}}
\newcommand{\qrej}{q_{\text{\tiny rej}}}
\newcommand{\csp}{\mathsf{CSP}}
\newcommand{\ared}{\text{\tt alph-red}}
\newcommand{\qred}{\text{\tt q-red}}
\newcommand{\dred}{\text{\tt deg-red}}
\newcommand{\amp}{\text{\tt gap-amp}}
\newcommand{\LC}{\mathcal{LC}}
\renewcommand{\H}{\mathcal{H}}
\newcommand{\iprod}[1]{\langle #1 \rangle}
\newcommand{\pmo}{\{\pm 1\}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{COS 433 --- Cryptography --- Homework 1.}
\author{Boaz Barak}
\date{Total of 125 points. Due February 10, 2010. \\ (Email or hand to Sushant by
the beginning of class on Wednesday.) }
\begin{document}
\maketitle
\noindent\textbf{Important note:} In all the exercises where you
are asked to prove something you need to give a \emph{well
written} and \emph{fully rigorous} proof. This does not mean the
proofs have to be overly formal or long --- a two-line proof is
often enough as long as it does not contain any logical gaps. If
a proof is made up of several steps, consider encapsulating each
step as a separate claim or lemma.
I prefer you type up your solutions using \LaTeX . To make this
easier, the \LaTeX\ source of the exercises are available on the
course's website.
\setcounter{exercise}{-1}
\begin{exercise}[10 points] Send email to Boaz (
\texttt{boaz@cs.princeton.edu} ) with subject \texttt{COS433 student} containing \textbf{(1)} a
couple of sentences about yourself, your background, and what you hope to learn in this course and
\textbf{(2)} your level of comfort with the following mathematical concepts: mathematical proofs,
elementary probability theory, big-Oh notation and analysis of algorithms, Turing machines and
NP-completeness. Please also describe any courses you've taken covering these topics.
\end{exercise}
%\begin{exercise}[10 points] Contact Boaz at \texttt{boaz@cs.princeton.edu}
%to schedule a 15 minute meeting no later than October 2nd.
%\end{exercise}
%\begin{exercise}[10 points] Prove that \[
%\Pr_{x\getsr \bits^{101}} [ \text{\# of $1$'s in $x$} \leq 50 ]
%= \frac{1}{2} \;\;.
%\]
%See footnote for hint\footnote{\textbf{Hint:} \tiny Letting $E$
%denote the event, this will follow if you'll show that
%$|E|=|\bits^{101} \setminus E|$. You can do this by exhibiting a
%bijection between these two sets.}
%\end{exercise}
\begin{exercise}[20 points]\label{ex:var} In the following exercise $X,Y$
denote finite random variables. That is, there are finite sets
of real numbers $\mathcal{X},\mathcal{Y}$ such that $\Pr[
X=x]=0$ and $\Pr[ Y=y]=0$ for every $x \not\in \mathcal{X}$ and
$y\not\in\mathcal{Y}$. We denote by $\Ex[X]$ the expectation of
$X$ (i.e., $\sum_{x\in\mathcal{X}} x\Pr[X=x]$), and by $Var[X]$
the variance of $X$ (i.e., $\Ex[(X-\mu)^2]$ where $\mu=\Ex[X]$).
The standard deviation of $X$ is defined to be $\sqrt{Var[X]}$.
\begin{enumerate}
\item Prove that $Var[X]$ is always non-negative.
\item Prove that $Var[X] = \Ex[X^2] - \Ex[X]^2$.
\item Prove that always $\Ex[X^2] \geq \Ex[X]^2$.
\item Give an example for a random variable $X$ such that
$\Ex[X^2] \neq \Ex[X]^2$.
\item Give an example for a random variable $X$ such that
its standard deviation is \emph{not equal} to $\Ex[ | X
- \Ex[X] | ]$.
\item Give an example for two random variables $X,Y$ such
that $\Ex[XY] = \Ex[X]\Ex[Y]$.
\item Give an example for two random variables $X,Y$ such
that $\Ex[XY] \neq \Ex[X]\Ex[Y]$.
\item Prove that if $X$ and $Y$ are independent random
variables (i.e., for every $x \in
\mathcal{X},y\in\mathcal{Y}$, $\Pr[X=x \wedge
Y=y]=\Pr[X=x]\Pr[Y=Y]$) then $\Ex[XY]=\Ex[X]\Ex[Y]$ and
$Var[X+Y]=Var[X]+Var[Y]$.
\end{enumerate}
\end{exercise}
\begin{exercise}[20 points] Recall that two distributions $X$ and $Y$ that range over some set $S$ are
\emph{identical} if for every $s$ in $S$, $\Pr[ X = s] = \Pr[ Y = s ]$. Below $n$ is some integer
$n\geq 3$. (You can get partial credit for solving the questions below for the special case that
$n=3$ and $z$ (in Question~2) is the string $111$.)
\begin{enumerate}
\item Let $X_1,...,X_n$ be random variables where $X_i \in \bit$ chosen such that each $X_i$ is
chosen to equal $0$ with probability $1/2$ and equal $1$ with probability $1/2$, and all of
the $X_i$'s are independent. Let $Y_1,...,Y_n$ be random variables where $Y_i \in \bit$
chosen as follows: first an $n$ bit $0/1$ string $y$ is chosen uniformly at random from the
set $\bit^n$ of all possible $n$-bit $0/1$ strings, and then $Y_i$ is set to be the
$i^{th}$ coordinate of $y$. Prove that the distributions $(X_1,...,X_n)$ and
$(Y_1,...,Y_n)$ are identical.
\item Let $z$ be a fixed string in $\bit^n$, and let $Z_1,...,Z_n$ be random variables chosen
as follows: first a string $w \in \bits^n$ is chosen uniformly from $\bit^n$, and then
$Z_i$ is set to $z_i \oplus w_i$, where $\oplus$ is the XOR operation (i.e., $0\oplus 1 = 1
\oplus 0 = 1$ and $0 \oplus 0 = 1 \oplus 1 = 0$). Prove that the distribution
$(Z_1,...,Z_n)$ is identically distributed to $(X_1,...,X_n)$ and $(Y_1,...,Y_n)$ above.
\item Let $W_1,...,W_n$ be random variables where $W_i \in \bit$ chosen as follows: first a
string $w$ is chosen uniformly at random from the set of all $n$-bit $0/1$ strings
satisfying $w_1 \oplus w_2 \oplus \cdots \oplus w_n = 0$, and then $W_i$ is set to be
$w_i$. \textbf{(a)} Prove that $W_1$ and $W_2$ are independent. \textbf{(b)} Prove or
disprove that the random variables $W_1,...,W_n$ mutually independent.
\end{enumerate}
\end{exercise}
\begin{exercise}[25 points] Show formally that the following schemes do
\emph{not} satisfy the definition of perfect security given in class (if it's more convenient you
can use Definitions 2.1 or 2.4 from the Katz-Lindell book instead). (Below we use $\Z_n$ to denote
the set of numbers $\{0,\ldots,n-1\}$ and identify the letters of the English alphabet with
$\Z_{26}$ in the obvious way.)
\begin{enumerate}
\item {\it (Caesar cipher)} Key: a random $k \getsr \Z_{26}$.
Encrypt a length-$2$ string $x \in \Z_{26}^2$ to the
pair $\angles{x_1 + k \pmod{26} , x_2 + k \pmod{26}}$
\item {\it (``Two-time pad'')} Key: $k \getsr \bits^{n}$.
Encrypt
$x \in \bits^{2n}$ by $x_{1..n} \oplus k$, $x_{n+1..2n}
\oplus k$, where $\oplus$ denotes bitwise XOR.
\item {\it (Substitution cipher)} Key: a random permutation
$\pi:\Z_{26}\To\Z_{26}$. Encrypt $x \in \Z_{26}^{2}$ by
$\pi(x_1),\pi(x_2)$.
\end{enumerate}
\end{exercise}
%\begin{exercise}[20 points] Prove that the definition of perfect
%security given in class is equivalent to Definition 2.1 (page 31) in the Katz-Lindell book (see
%link to Chapter 1 on the website). That is, prove that for every scheme $(E,D)$, $(E,D)$ is
%perfectly secure under our definition if and only if $(G,E,D)$ is perfectly secret under definition
%2.1 (where $G$ denotes the key generator that outputs a random $k$ in $\bits^n$).
%\end{exercise}
\begin{exercise}[25 points] Give examples (with proofs) for
\begin{enumerate}
\item A scheme such that it is possible to efficiently
recover $90\%$ of the bits of the key given the
ciphertext, and yet it is still perfectly secure. Do you
think there is a security issue in using such a scheme
in practice?
\item An encryption scheme that is \emph{insecure} but yet
it provably hides the first $20\%$ bits of the key. That
is, if the key is of length $n$ then the probability
that a computationally unbounded adversary guesses the
first $n/5$ bits of the key is at most $2^{-n/5}$.
\end{enumerate}
You can use the results proven in class and above. Also the
examples need not be natural schemes but can be ``contrived''
schemes specifically tailored to obtain a counter-example.
\end{exercise}
\begin{exercise}[Bonus 25 points] In class we saw that any
perfectly (and even imperfectly) secure private key encryption
scheme needs to use a key as large as the message. But we
actually made an implicit subtle assumption: that the encryption
process is \emph{deterministic}. In a \emph{probabilistic
encryption scheme}, the encryption function $\Enc$ may be
probabilistic: that is, given a message $x$ and a key $k$, the
value $\Enc_k(x)$ is not fixed but is distributed according to
some distribution $Y_{x,k}$. Of course, because the decryption
function is only given the key $k$ and not the internal
randomness used by $\Enc$, we need to require that $\Dec_k(y)=x$
for \emph{every} $y$ in the support of $Y_{k,x}$ (i.e.,
$\Dec_k(y)=x$ for every $y$ such that $\Pr[ \Enc_k(x)=y]>0$).
Prove that even a probabilistic encryption scheme cannot have
key that's significantly shorter than the message. That is, show
that for every probabilistic encryption scheme $(\Dec,\Enc)$
using $n$-length keys and $n+10$-length messages, there exist
two messages $x,x' \in \bits^{n+10}$ such that the distributions
$\Enc_{U_n}(x)$ and $\Enc_{U_n}(x')$ are of statistical distance
at least $1/10$. See footnote for hint\footnote{\textbf{Hint:}
\tiny Define $\mathcal{D}$ to be the following distribution over
$\bits^{n+10}$: choose $y$ at random from $\Enc_{U_n}(0^{n+5})$,
choose $k$ at random in $\bits^n$, and let $x = \Dec_{k}(y)$.
Prove that if $(\Enc,\Dec)$ is $1/10$-statistically
indistinguishable then for every $x\in\bits^{n+10}$,
$\Pr[\mathcal{D} = x ] \geq 2^{-n-1}$. Derive from this a
contradiction.}
\end{exercise}
\end{document}