\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage[table]{xcolor}
\usepackage{adjustbox}
\usepackage{dashbox}
\usepackage{cjhebrew}
\usepackage{xspace}
\begin{document}
\input{preamble.tex}
\lecture{1}{November 2, 2017}{Nir Bitansky}{November 16}
\paragraph{Instructions:}
\begin{itemize}
\item
Type your solution and email it to me. Include FOCF17HW in the subject.
You're encouraged to do so in latex. You can find on the webpage the assignment's tex file to help you.
\item
You can cooperate. However, you should write the solution by yourself, and list all collaborators for each question. Same goes for any external sources that you may use.
\item
Do not discuss solutions over the course's forum. You are more than welcome though to ask for clarifications regarding the questions themselves.
\end{itemize}
\bigskip
\begin{enumerate}
\item
(25 pts) In class, we saw that for any encryption scheme $(E,D)$ for messages of length $\ell$, with keys of length $n \leq \ell - 10$, if $E$ is deterministic, there exist two messages $m_0,m_1$ and an inefficient $A$ such that
$$
\Pr\[A(ct)=m_b \pST \begin{array}{l} sk \gets \zo^n\\ b\gets \zo\\ct \gets E_{sk}(m_b)\end{array}\] > 0.99\enspace.
$$
Show that the same holds even if $E$ also tosses, say $n$, coins (on top of the key). That is, an encryption of any message $m\in\zo^\ell$ is drawn from a distribution $\set{ct\pST sk\gets\zo^n, r\gets \zo^n, ct = E_{sk}(m;r)}$.
\item
In this question, let $X_0,X_1$ be two distributions with the same finite support $S$.
Recall that:
$$
\Delta_A(X_0,X_1):=\abs{\Pr\[A(X_0)=1\]-\Pr\[A(X_1)=1\]} \enspace.
$$
\begin{enumerate}
\item (15 pts) Show that for any function $A$ (efficient or not):
$$
\abs{\Pr\[A(x) = b\pST \begin{array}{l}
b \gets \zo\\
x \gets X_b
\end{array}\] - \frac{1}{2}}=\frac{\Delta_A(X_0,X_1)}{2}\enspace.
$$
\item
(15 pts)
Show that
$$
\max_A \Delta_A(X_0,X_1) = \frac{1}{2}\sum_{x\in S}\abs{\Pr\[X_0=x\]-\Pr\[X_1=x\]} = \max_{T\subseteq S}\abs{\Pr\[X_0\in T\]-\Pr\[X_1 \in T\]}\enspace.
$$
\item
(15 pts) let $A$ be a randomized distinguisher that uses $n$ random coins. That is, $A(x;r)$ is given a sample $x$ and a random string $r\gets \zo^n$ (and as usually outputs a bit). Prove that there exists a fixed string $r \in\zo^n$ such that
$$
\Delta_A((X_0;r ),(X_1;r)) \geq \Delta_A((X_0;U_n),(X_1;U_n))\enspace,
$$
where $U_n$ is the uniform distribution on $\zo^n$.\\
(This means that for non-uniform algorithms, we can often assume w.l.o.g that they're deterministic.)
\end{enumerate}
\item
Let $S_0$ and $S_1$ be two non-uniform \PPT algorithms, and let $X = \set{X_n}_{n\in\Nat}$ be a distribution ensemble. Assume that
$$
X,S_0(X) \approx_c X,S_1(X)\enspace,
$$
Here $(X,S_b(X))$ denotes the distribution ensemble $\set{X_n,S_b(X_n)}_{n\in\Nat}$, where a sample $(x,y)$ is given by first sampling $x\gets X_n$ and then sampling $y\gets S_b(x)$ (note that $S_b$ is randomized and may toss additional coins of its own).
Let $p$ be any polynomial. For $b\in \zo$, consider a new ensemble $Y_b=\set{Y_{b,n}}_{n\in\Nat}$, given by
$$
Y_{b,n} = (X_n,\overbrace{S_b(X_n),\dots,S_b(X_n)}^{p(n) \text{ times }})\enspace,
$$
where a sample $(x,y_1,\dots,y_{p(n)})$ is given by sampling $x\gets X_n$ and then independently sampling each $y_i \gets S_b(x)$.
\begin{enumerate}
\item
(30 pts) Show that $Y_0 \approx_c Y_1$.
\item
({\bf Bonus}: 10 pts) show that if $S_0,S_1$ may be {\bf inefficient}, and there exists computationally-secure (secret-key) encryption, the previous claim is not true.
\end{enumerate}
\end{enumerate}
\end{document}