\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}{October 31, 2019}{Nir Bitansky}{Due: November 14}

\paragraph{Instructions:}
\begin{itemize}
  \item
  Type your solution and email it to "focf19hw@gmail.com", with subject "HW\#, ID\#, Name".
  \item
  You're encouraged to use latex. You can find on the webpage the assignment's tex file to help you.
  \item
  You can collaborate. 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}