\documentclass{article}
\input{6875-preamble}

\newcommand{\onek}[0]{\mathtt{1}^k}
\begin{document}
\psetnum{1}
\date{2007/02/20}

\begin{pset}
  \begin{problem}
    
    \begin{subproblem}
      \textbf{False}. We'll construct a length-preserving one-way
      function $f$ that has the property that $f(f(x))$ is not
      one-way. We start by assuming that $h(x)$ is a length-preserving
      one-way function. We define $f$ as follows, on an input of
      length $n$
      \[
      f(x) =
      \begin{cases}
        \mathtt{0}^n \qquad& \text{if $x_0x_1 \cdots
          x_{\nicefrac{n}{2}} = \text{0}^{\nicefrac{n}{2}}$}\\
        \mathtt{0}^{\nicefrac{n}{2}} \; |\; h\left(x_0x_1 \cdots
          x_{\nicefrac{n}{2}}\right) \qquad& \text{otherwise}
      \end{cases}
      \]
    \end{subproblem}

    \begin{subproblem}
      \textbf{True}. Suppose that $g(x)$ is not a one-way
      function. That is, suppose there exists some probabilistic
      polynomial time algorithm that, with probability at least
      $\frac{1}{k^c}$ (for some $c$ and for an infinite sequence of
      values of $k$), takes as input $y$ and returns $z$ such that
      $g(z) = y$ (hence $f(\overline{z}) = y$). We can use this to
      invert $f$: given some $y$, use the algorithm to find $z$ such
      that $g(z) = y$, and return $\overline{z}$. This succeeds with
      the same non-negligible probability as the algorithm for
      inverting $g$.
    \end{subproblem}

    \begin{subproblem}
      \textbf{True}. As before, suppose there exists some probabilistic
      polynomial time algorithm that, with probability at least
      $\frac{1}{k^c}$ (for some $c$ and for an infinite sequence of
      values of $k$), takes as input $z$ and returns $x,y$ such that
      $g(x,y) = z$.  Then we can invert $k$: given some $z$, we can
      find $x,y$ such that $g(x,y) = z$; since $g(x,y) = f(x \oplus
      y)$, $x \oplus y$ is a preimage of $z$ under $f$.
    \end{subproblem}

    \begin{subproblem}
      
    \end{subproblem}
  \end{problem}

  \begin{problem}
    
  \end{problem}

  \begin{problem}
    \paragraph{Unpredictability $\implies$ Indistinguishability.}
    Suppose an adversary can distinguish encryptions of 1 from
    encryptions of 0:
    \begin{multline*}
      \exists \mathcal{A} \in \PPT \quad \exists c > 0 \quad \forall
      k_0 \; \exists
      k > k_0 \\
      \Pr{\tup<PK, SK> \gets G(\onek);\; x \gets E_{PK}(\mathtt{0}) ;
        \; y \gets E_{PK}(\mathtt{1})\;:\; \mathcal{A}(\onek, PK, x)
        \neq \mathcal{A}(\onek, PK, y)} \ge \frac{1}{2} + \frac{1}{k^c}
    \end{multline*}


    \paragraph{Indistinguishability $\implies$ Real-or-Random.}
    Suppose an adversary can distinguish real messages from random
    messages:
    \begin{multline*}
      \exists \mathcal{A} \in \PPT \quad \exists c > 0 \quad \forall
      k_0 \; \exists
      k > k_0 \\
      \Pr{\tup<PK, SK> \gets G(\onek);\; x_0 \gets E_{PK}(\mathtt{0})
        ;\; r \gets \bit ;\; x_1 \gets E_{PK}(r) ;\; b \gets \bit ;\;
        g \gets \mathcal{A}(\onek, PK, x_b, x_{1-b})\;:\; b = g }\\\ge
      \frac{1}{2} + \frac{1}{k^c}
    \end{multline*}

    Define a new adversary $\mathcal{A}'$ that works as follows. Given
    some input $x$, 
  \end{problem}
\end{pset}
\end{document}