\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{2}{November 16, 2017}{Nir Bitansky}{November 30}

\paragraph{Instructions:}
\begin{itemize}

  \item
  Type your solution and email it to "focf17hw@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 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
  (30 pts) Let $\ell,\ell'$ be two polynomials. An ensemble of functions $\set{f_n:\zo^{\ell(n)}\rightarrow \zo^{\ell'(n)}}_{n\in\Nat}$ is one-way if there exists a poly-time algorithm $f(1^n,x)$ that given $1^n$ and $x\in\zo^{\ell(n)}$ outputs $f_n(x)$, and for every n.u. PPT $A$ there exists a negligible $\mu$ such that for all $n\in\Nat$
  $$
   \Pr_{x\gets \zo^{\ell(n)}}\[A(f_n(x))\in f_n^{-1}(f_n(x))\] \leq \mu(n)\enspace.
  $$
  Show that any such ensemble implies OWFs as defined in class; namely, a function $f$ that is defined on every input length $n$, and not just $\ell(n)$.

  \item
  Let $G$ be a PRG with stretch $\ell$ (that is, $G$ maps $n$ bits to $n+\ell(n)$ pseudorandom bits).
  \begin{enumerate}
     \item (15 pts) Show that if $\ell(n) = \omega(\log n)$, then $G$ is a OWF.
    \item (15 pts) Actually, show that even if $\ell(n) = 1$, then $G$ is a OWF.
    \item ({\bf Bonus:} 10 pts) Assume $\ell(n) = 1$. Define an ensemble of functions $f=\set{f_n:\zo^{2n}\rightarrow \zo^{n+1}}$ by  $(s_0,s_1) \overset{f_n}{\longmapsto} G(s_1)\oplus G(s_2)$. Prove that $f$ is one way or give a counter example.
  \end{enumerate}

  \item
  We say that $f$ is a weak one-way function if there exists a polynomial $p$ such that for any n.u. PPT $A$ and all $n\in\Nat$:
   $$
   \Pr_{x\gets \zo^n}\[A(f(x))\in f^{-1}(f(x))\] \leq 1-\Omega\(\frac{1}{p(n)}\)\enspace.
   $$

 This question aims to show that {\em weak} OWFs may be strictly weaker than OWFs, but can always be amplified to OWFs.
 \begin{enumerate}
   \item
   (10 pts) Show that if there exist OWFs, then there also exist weak OWFs that are not OWFs.
   \item
   Let $f$ be a weak OWF with respect to some polynomial $p$ (as in the above definition), and let $t(n)=\log^2 n\cdot p(n)$. We define the $t$-fold direct product $f_n^{\otimes t}:\(\zo^{n}\)^{t(n)}\rightarrow \zo^*$ as:
   $$
   f_n^{\otimes t}(x_1,\dots, x_{t(n)}) = f(x_1),f(x_2),\dots, f(x_{t(n)})\enspace.
   $$
 We will show that the ensemble $\set{f_n^{\otimes t}}_n$ is one-way. In what follows, let $A$ be an adversary that inverts $f_n^{\otimes t}$ with probability $\varepsilon=\varepsilon(n)$.\\
 For $i\in [t]$, let $G_i\subseteq \zo^n$ be the set of inputs $x$ such that
 $$
 \Pr_{x_1, \dots, x_{i-1}, x_{i+1}, \dots,x_t}\[A \text{ inverts } f^{\otimes t}(x_1, \dots, x_{i-1}, x, x_{i+1} \dots, x_t))\] \geq \varepsilon/2t \enspace.
 $$
 \begin{enumerate}
   \item (12 pts)
Show that there exists an $i\in [t]$ such that
$$\Pr_{x\gets \zo^n}\[x\in G_i\] \geq 1- \frac{\log(2/\varepsilon)}{t}\enspace.$$
\item
(12 pts)
Show that there exists a n.u. adversary $A'$ (depending on $A$ and $i$) whose running time is
$$
time(A') = O\(time(A)\cdot time(f)\cdot \frac{t}{2\varepsilon}\cdot n\)
$$
and which inverts $f$ with probability at least $1- \frac{\log(2/\varepsilon)}{t}-2^{-n}$. (You can use the previous item even if you didn't manage to prove it.)
\item
(6 pts)
Deduce that $\varepsilon(n) = n^{-\omega(1)}$. That is, $f^{\otimes t}$ is a OWF.
 \end{enumerate}
    \end{enumerate}



\end{enumerate}


\end{document}