\documentclass[11pt]{article}
\usepackage{amssymb,amsmath,amsthm,url}
\usepackage{graphicx}
\newif\ifpdf
\ifx\pdfoutput\undefined \else
\ifx\pdfoutput\relax
\else
\ifcase\pdfoutput
\else
\pdftrue
\fi
\fi
\fi
%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{\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{\text{\tiny def}}{=}}
\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\}}
\newcommand{\set}[1]{\{ #1 \}}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{COS 433 --- Cryptography --- Homework 10.}
\author{Boaz Barak}
\date{Total of 120 points. Due \textbf{Monday, December 17th, 2007 1:30pm}. \\
\textbf{This exercise will have double weight (counts for two exercises).} }
\begin{document}
\maketitle
\begin{exercise}[30 points] The following questions rely on the definition
of two-party secure function evaluation given in class (using
simulation), you can find a definition also in Oded Goldreich's
book (or the online version) or in Yehuda Lindell's thesis.
Recall that we think of computing a function
$f:\bits^n\times\bits^n\To \bits^n\times\bits^n$, where if Alice
has input $x$ and Bob has input $y$, at the end of the protocol
Alice gets $w$ and Bob gets $z$, where $(w,z)=f(x,y)$, and we
also use the notation $w=f_1(x,y)$, $z=f_2(x,y)$. Neither Alice
nor Bob should get anything else.
\begin{enumerate}
\item Suppose we have a protocol to evaluate every
polynomial-time computable $f()$ whose two outputs are
the same: $f_1(x,y)=f_2(x,y)$ for every $x,y$. Use that
to construct a protocol to evaluate every
polynomial-time computable function.
\item Suppose we have a protocol to evaluate every poly-time
function $f()$, use that to construct a protocol to
evaluate every \emph{poly-time probabilistic process},
where a probabilistic process is a function
$g:\bits^n\times\bits^n\times\bits^n\To\bits^n\times\bits^n$
on \emph{three} inputs, and if Alice has input $x$ and
Bob has input $y$, then Alice gets $w$ and Bob gets $z$
where $(w,z)=f(x,y,r)$ for a uniformly random string $r$
(note that neither Alice nor Bob can control or know
$r$).
\end{enumerate}
\end{exercise}
\begin{exercise}[30 points] The following two questions concerns
the heuristic we saw used in some electronic voting protocols to
transform an interactive public coin proof system into a
non-interactive system (this is known as the \emph{Fiat-Shamir
heuristic}).
\begin{enumerate}
\item Let $L$ be some language and $\Pi$ be a 3-round (first
prover message, verifier message, last prover message)
interactive proof system for $L$ with soundness $2^{-n}$
on inputs of length $n$ that is \emph{public coins}
(i.e., verifier's message is a random string and his
decision is obtained by running a polynomial-time
algorithm on the transcript).\footnote{We don't care if
$\Pi$ is or is not zero knowledge.} Suppose that in the
random oracle model, the verifier's message is computed
by applying the oracle on the input and first message,
to obtain a \emph{non-interactive} proof system for $L$
(the prover computes a proof by computing his first
message, applying the oracle to obtain the verifier's
message, and then responding to that message). Prove
that this proof system has still negligible
($n^{-\omega(1)}$) soundness error with respect to
polynomial-time provers. See footnote for
hint.\footnote{\textbf{Hint:} \tiny This is true as long
as a cheating prover can make at most a polynomial
number of queries to the oracle, regardless of its
running time.} \textbf{Extra 15 points:} Prove this
remains true even if $\Pi$ has a constant (possibly
larger than $3$) number of rounds. That is, we take such
a proof system $\Pi$ and make it non-interactive by
changing every verifier message to be obtained by
applying the oracle to the concatenation of the input
and all previous messages sent by the prover.
\item Show that the previous statement is false if we put no
condition on the number of rounds in $\Pi$. That is,
show a language $L$ and a public-coin proof system $\Pi$
for $L$ with soundness error $2^{-n}$ (possibly using
polynomially many rounds), such that if we replace every
message of the verifier by an application of the random
oracle on all previous messages, then a polynomial-time
cheating prover can come up with an accepting transcript
for an input $x\not\in L$.
\end{enumerate}
\end{exercise}
\begin{exercise}[45 points] For each of the following statements, say whether
it is \emph{true} or \emph{false}, and prove your assertion. You
can consider as true all the assumption given in class as
mentioned in the instructions on the first page. For example, if
the statement is that there exists an object with some
properties, then either prove that such an object exists by
giving a construction based on the assumptions together with a
proof that the construction satisfies the properties, or prove
that such an object cannot exist.
\begin{enumerate}
\item There exists a pseudorandom generator $G = \{ G_n \}$
where for every $n$, $G_n:\bits^n\To\bits^{2n}$ such
that for every $x \in \bits^n$, the first $n/3$ bits of
$G_n(x)$ are zero.
\item There exists a pseudorandom generator $G = \{ G_n \}$
where for every $n$, $G_n:\bits^n\To\bits^{2n}$ such
that for every $x \in \bits^n$, there exist $n/3$ bits
of $G_n(x)$ that are zero.
\item There exists a pseudorandom generator $G = \{ G_n \}$
where for every $n$, $G_n:\bits^n\To\bits^{2n}$ such
that for every $x \in \bits^n$, if the first $n/3$ bits
of $x$ are zero then all the bits of $G_n(x)$ are zero
(i.e., $G_n(x)=0^{2n}$).
\item There exists a pseudorandom function collection $\{
f_s \}_{s\in\bits^*}$ where, letting $n=|s|$,
$f_s:\bits^n \To \bits^n$ that satisfies the following:
for every $x\in\bits^n$, $f_{0^n}(x)=0^n$ (i.e.,
$f_{0^n}(\cdot)$ is the constant zero function).
\item There exists a pseudorandom function collection $\{
f_s \}_{s\in\bits^*}$ where, letting $n=|s|$,
$f_s:\bits^n \To \bits^n$ that satisfies the following:
for every $s\in\bits^n$, $f_s(0^n)=0^n$.
\item \label{itm:CPAcnot} For $\ell \geq 2$ and a string
$x\in\bits^{\ell}$, let
$cnot:\bits^{\ell}\To\bits^{\ell}$ be the following
function: $cnot(x_1,\ldots,x_{\ell}) = x_1,x_2 \oplus
x_1, x_3,\ldots,x_{\ell}$. (That is, $cnot$ flips the
second bit of $x$ according to whether or not the first
bit is one.) There exists a CPA-secure public key
encryption scheme $( \Gen,\Enc, \Dec )$ and a polynomial
time algorithm $A$, such that for every $n$, if $(e,d) =
\Gen(1^n)$ then for every $x \in \bits^{\ell}$ (where
$\ell$ is the message size of the encryption scheme for
security parameter $n$) it holds that
\[
\Dec_d\left( A \Bigl(e,\Enc_e(x)\Bigr) \right) = cnot(x)
\]
\item Same statement as Item~\ref{itm:CPAcnot} but with
CPA-secure replaced with CCA-secure.
\item \label{itm:commitBit} There exists a \emph{commitment
scheme} $C:\bits \times \bits^n \To \bits^m$ (i.e., a
commitment for messages of length one bit, where to
commit to the bit $b$, one chooses $r \getsr \bits^n$
and sends $C(b,r)$) and a polynomial time algorithm
$A:\bits^m \To \bits$, such that for both $b=0$ and
$b=1$,
\[
\Pr_{U_n}[ A\Bigl( C(b,U_n) \Bigr) \oplus b = 1 ] \geq 2/3
\]
where $U_n$ denotes the uniform distribution over $\bits^n$.
\item Same statement as Item~\ref{itm:commitBit} but with
$2/3$ replaced with $1/2$.
\end{enumerate}
\end{exercise}
\end{document}