\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 \}}
\newcommand{\jacobi}[2]{\left(\frac{#1}{#2}\right)}
% end of macros
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{COS 433 --- Cryptography --- Homework 9.}
\author{Boaz Barak}
\date{Total of 120 points. Due April 14th, 2007.}
\begin{document}
\maketitle In the following two questions, we consider a zero knowledge proof system for proving statements of the form
``$x \in L$'' where $L$ is a subset (also called ``language'') of $\bits^*$. (We're only concerned here with standard
soundness and not knowledge soundness.) We want to show that unless it's easy to verify statements like that just from
the public input $x$ (in which case there's a trivial zero knowledge protocol where the prover doesn't say anything),
then both interaction and randomization are necessary.
\begin{exercise}[Interaction is necessary, 15 points]
Let $L$ be a language that is not decidable in polynomial time
(that is, there is no efficient (possibly probabilistic)
algorithm that on input $x$ outputs $1$ if $x\in L$ and $0$
otherwise). Show that there is no \emph{non-interactive} zero
knowledge proof system for $L$. That is, show that if a language
$L$ has a proof system that consists of a single message from
the prover to the verifier then $L$ is decidable by a
polynomial-time algorithm.
\end{exercise}
\begin{exercise}[Randomness is necessary, 15 points]
Let $L$ be a language that is not decidable in polynomial-time.
Show that there is no \emph{deterministic} zero knowledge proof
system for $L$. That is, show that if a language $L$ has a proof
system where the verifier is deterministic then $L$ is decidable
by a polynomial-sized algorithm.
\end{exercise}
In the following exercises we'll use the \textbf{Quadratic Residuosity Axiom}: the following two distributions $(X,N)$
and $(Y,N)$ are computationally indistinguishable where $N$ is a random Blum integer (obtained by setting $N=PQ$ where
$P,Q$ are two random $n$ bit primes satisfying $P,Q = 3\pmod{4}$), $X$ is a random quadratic residue modulo $N$, and
$Y$ is a random quadratic non-residue modulo $N$ of Jacobi symbol $+1$.
The Jacobi symbol of $X$ modulo a prime $P$ (also known as the Legendre symbol for this case), denoted by
$\jacobi{X}{P}$, is $+1$ is $X$ is a quadratic residue and $-1$ if $X$ is not a quadratic residue. The Jacobi symbol of
$X$ modulo $N=PQ$, is $\jacobi{X}{N} = \jacobi{X}{P}\jacobi{X}{Q}$. There is a known polynomial-time algorithm to
compute the Jacobi symbol $\jacobi{X}{N}$.
It can be easily verified that the set of $X\in\Z^*_N$ with $\jacobi{X}{N}=+1$ is a subgroup of $\Z^*_N$ of size
$|\Z^*_N|/2$. The Chinese remaindering theorem implies that if $X$ is a quadratic residue modulo $N$ than
$\jacobi{X}{N}=+1$, although the quadratic residues account for only $|\Z*_N|/4$ of the $X$'s with $\jacobi{X}{N}=+1$.
\begin{exercise}[15 points] Prove that if $N$ is a Blum integer, then $-1$ is a non-quadratic residue modulo $N$ and
$\jacobi{-1}{N}=+1$.
\end{exercise}
\begin{exercise}[25 points] \begin{enumerate}
\item Prove that the following public key cryptosystem $(G,E,D)$ is CPA secure under the Quadratic Residuosity axiom:
\begin{description}
\item[Key generation] Given security parameter $n$, let $P,Q$ two $n$-bit prime random primes and let $N=PQ$. The
public key is $N$ and the secret key is $P,Q$.
\item[Encrypt] To encrypt a bit $b\in\bits$, choose $X \getsr \Z^*_N$ and output $X^2(-1)^b \pmod{N}$.
\item[Decrypt] To decrypt $Y\in \Z^*_N$, output $0$ if $Y$ is a quadratic residue and $1$ otherwise. (Knowing the
factorization, quadratic residuosity can be tested using Chinese remaindering.)
\end{description}
\item Prove that there is an algorithm that given the public key $N$ and two ciphertexts $Y,Y' \in \Z^*_N$ that decrypt
to $b,b'$, outputs $Z$ such that $Z$ is identically distributed to an encryption of $b \oplus b'$ (where $\oplus$ denotes XOR).
This property is called being \emph{homomorphic} with respect to XOR. Does this property contradict CPA security?
how about CCA security?
\end{enumerate}
This cryptosystem is due to Goldwasser and Micali.
\end{exercise}
\begin{exercise}[50 points] In the ``cloud computing problem'' we think of a user Alice that wishes to store a large database on
the cloud of the server Bob, but doesn't wish Bob to learn anything about Alice's data. Specifically, we think of the
database as just a very long string $A \in \bits^M$. We'll think of $M$ as being much larger than the key size/security
parameter $n$ we use for our cryptosystems etc.. A \emph{cloud computing protocol} consists of the following:
\begin{itemize}
\item (Uploading phase) Alice uploads the database to Bob by sending him a string $\Hat{A}$. She may keep a small
state of $\poly(n)$ bits to herself where $n$ is the security parameter, but she does not have memory to store
the entire $M$ bit long database on her own.
\item (Recovery phase) Later, if Alice wants to recover $A_i$ for some $i\in [M]$, she sends a message $\Hat{i}$ to
Bob, and gets back a message $\Hat{b}$ from Bob. She should be able to obtain $x_i$ from $\Hat{b}$ (and her own
state) by some efficient procedure.
\end{itemize}
The security notion for this protocol is that for every $A,A' \in \bits^M$ and $i,i' \in [M]$, the messages that Alice
sends when uploading $A$ and querying $i$ are indistinguishable from the messages she sends when uploading $A'$ and
querying $i'$. (This simplified security notion is just protecting against passive/eavesdropping attacks by Bob--- in
real life we'd want to protect against active attacks as well.) We require Bob, Alice to run in polynomial time in
$n,M$.
\begin{enumerate}
\item Show that there exists a secure cloud computing protocol.
\item Consider the following variant of cloud computing, where we think of the database $A$ as a $\sqrt{M}$ by
$\sqrt{M}$ matrix over $\GF(2)$ and $i$ as a vector in $\GF(2)^{\sqrt{M}}$, and Alice wished to recover the
vector $Ai$. Show that there is a secure cloud computing protocol for this variant, where the length of the
messages exchanged between Alice and Bob in the recovery phase is at most $\sqrt{M}\poly(n)$.
\item Show that there exists a secure cloud computing protocol (in the standard sense) where the length of the
messages exchanged between Alice and Bob in the recovery phase is at most $\sqrt{M}\poly(n)$.
\end{enumerate}
\end{exercise}
\end{document}