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

\begin{document}
\psetnum{1}
\date{2007/02/20}

\begin{pset}
  \begin{problem}
    \begin{subproblem}
      \textbf{False}. Note that since $g$ is a generator of $Z_p^*$,
      $\set{g^x \bmod p | x \in [1,p-1]}$ is a permutation of $[1,
      p-1]$. So the left side of the equality, $\set{x \gets Z_p^* :
        g^x \bmod p}$, is a uniform distribution over the integers in
      $Z_p^*$. On the right side, we can write $g^{xy} \bmod p$ as
      $\left(g^x\right)^y \bmod p$. Then $\set{x \gets Z_p^* ; y \gets
        Z_p^* : g^{xy} \bmod p} = \set{x \gets Z_p^* ; y \gets Z_p^* :
        x^{y} \bmod p}$. This cannot be equal to the left side
      distribution. Note that for every value of $x$, 1 occurs with
      probability at least $\frac{1}{p-1}$ in $\set{y \gets Z_p^* :
        x^{y} \bmod p}$ (for $y = p-1$, by Fermat's little theorem),
      and for $x=1$, 1 occurs with probability 1. So 1 occurs with
      greater probability than other elements on the right side,
      whereas all elements occur with equal probability on the left
      side, so they cannot be equal.
    \end{subproblem}

    \begin{subproblem}
      \textbf{True}. If $g$ is a generator of $Z_p^*$, $\set{x \gets Z_p^* :
        g^x \bmod p}$ is a uniform distribution over the elements in
      $Z_p^*$, as noted above. The same is true of any other
      generator, such as $h$.
    \end{subproblem}

    \begin{subproblem}
      \textbf{False}. Counterexample: let $p=5$ and $g=2$. Then
      $\set{x \gets Z_p^* : x^g \bmod p}$ includes only the quadratic
      residues mod 5, which are 1 and 4; 2 and 3 never occur. So it is
      not equal to the uniform distribution.
    \end{subproblem}

    \begin{subproblem}
      \textbf{False}. Counterexample: let $p=13$, $g=2$, and $h=6$; we
      can verify by inspection that $g$ and $h$ are generators of
      $p$. Note that for all $x$, $x^{gh} \bmod p = x^{p-1} \bmod p =
      1$. Then the right side distribution is always 1. The left side
      distribution is not (for example, for $x=2$, $x^2 = 4$), so they
      cannot be equal.
    \end{subproblem}
  \end{problem}

  \begin{problem}
    Suppose that we have a probabilistic polynomial time algorithm
    that takes inputs $p$, $g$, and $g^x \bmod p$, where $p$ is a
    prime, $g$ is a generator of $Z_p^*$, and $g^x \bmod p$ is prime,
    and outputs $x$. We give a probabilistic polynomial time algorithm
    for solving the same problem without the restriction that $g^x
    \bmod p$ be prime.

    Our algorithm is as follows: choose $y$ at random from $[1, p-1]$,
    compute $g^y \bmod p$ via fast modular exponentiation, and
    multiply it by $g^x \bmod p$ to obtain $g^{x+y} \bmod p$. If
    $g^{x+y} \bmod p$ is not prime (which can be checked in polynomial time),
    choose a new $y$ and try again. Otherwise, use the given algorithm
    for the prime DLP to compute $x+y$ from $g^{x+y} \bmod p$. We can
    recover $x$ from this by subtracting $y$ ($\bmod p$, of course),
    thus solving the discrete logarithm.

    For each randomly chosen $y$, the exponentiation, primality
    testing, and other modular operations can be performed in
    polynomial time; we need only to bound the number of attempts
    until we find a $y$ such that $g^{x+y} \bmod p$ is prime. Because
    $y$ is chosen randomly, $x+y \bmod p$ is chosen uniformly from
    $[1, p-1]$, and so $g^{x+y}$ will be chosen uniformly from $[1,
    p-1]$ (as in Problem 1). The Prime Number Theorem tells us that
    this number will be prime with probability $\bigO{\frac{1}{\log
        p}}$, so in expectation $\bigO{\log p}$ trials will be
    required, which is polynomial in the length of the input.
  \end{problem}

  \vspace{1em}\-\\
  \begin{problem}
    Skipped.
  \end{problem}

  \begin{problem}
    Suppose we have an oracle that can output square roots mod $n$. We
    show that this can be used to factor $n$.

    \begin{lemma}
      If $x$ and $y$ satisfy $x^2 \equiv y^2 \pmod n$, and $x \neq
      \pm y$, then $gcd(x+y, n)$ is a non-trivial factor of
      $n$.
    \end{lemma}

    \begin{proof}
      We can view $n$ as the product of a set of prime factors:
      $\set{p_1, \ldots, p_n}$, where the $p_i$ may not be
      unique. Because $x^2 \equiv y^2 \pmod n$, $(x+y)(x-y) \equiv 0
      \pmod n$, and so $n$ divides $(x+y)(x-y)$. Thus, the set of
      prime factors of $(x+y)(x-y)$ is a superset of
      $\set{p_1, \ldots, p_n}$. Since this is the union of the sets of
      prime factors of $(x+y)$ and $(x-y)$, each of the $p_i$ must
      appear as a prime factor in either $(x+y)$ or $(x-y)$. Note that
      there must be at least one $p_i$ that does not appear as a
      factor in $(x+y)$, because otherwise $x+y \equiv 0 \pmod n$,
      contradicting our assumption; the same holds for $(x-y)$. The
      gcd of $x+y$ and $n$ is the set of factors that appear in both
      $(x+y)$ and $n$; from the above, we know that this is at least
      one but not all of the $p_i$, meaning that it is a non-trivial
      factor of $n$.
    \end{proof}

    Using this lemma, we factor $n$ as follows. We generate a random
    number $x \in [1, n-1]$, compute its square $\bmod n$, and feed
    this to the oracle. Call the oracle's result $y$. If $y = \pm x$,
    then try a different choice of $x$. If $y \neq \pm x$, then we
    have two distinct square roots of $x^2$, and by the lemma above,
    $gcd(x+y,n)$ gives a non-trivial factor of $n$, splitting it. We
    can recursively apply the algorithm to obtain the prime
    factorization, if desired.

    We claim that in expectation the algorithm requires a constant
    number of attempts to find a $x,y$ that are distinct square
    roots. For each prime factor $p$ of $n$, $y = x^2 \pmod{p}$ has
    two solutions. Choosing one of the two square roots for each prime
    factor, the Chinese remainder theorem gives a square root modulo
    $n$. So there are $2^{\text \# prime factors}$ possible square
    roots, of which one is the starting number $x$ and one is $-x$;
    thus at least $\nicefrac12$ of the possible square roots are
    distinct with respect to $x$. The oracle effectively chooses which
    square root to output at random: for each value of $x^2$ it must
    output a single square root; if it always output $x$, this would
    not be a problem since our algorithm was just as likely to choose
    a distinct square root $y$ (satisfying $y^2 \equiv x^2$) to
    square. Thus, the expected number of attempts is bounded by 2, and
    polynomial work is required for each attempt.
  \end{problem}

  \begin{problem}
    Assume factoring is hard. That is,
    \begin{multline*}
      \forall \mathcal{ADV} \in \mathsf{PPTF}\quad \forall c \quad \exists
      k_0 \forall k > k_0 \\
      \Pr{p \gets \mathsf{PRIMES}_k ; \; q \gets \mathsf{PRIMES}_k ;
        \; n = pq; \; x \gets \mathcal{ADV}(n) \; : \; x \in \set{p,q}
      } < \frac{1}{k^c}
    \end{multline*}
  \end{problem}

  This nearly gives us a one-way function, but the domain is over the
  set $\mathsf{PRIMES}_k \times \mathsf{PRIMES}_k$ rather
  than $\kstrings$. We solve this problem using the technique in
  Goldwasser and Bellare's notes for constructing a one-way function
  from a collection of one-way functions. We define a new function $f:
  \kstrings \mapsto \kstrings$ as follows: $f$ generates two prime
  numbers $p$ and $q$ by interpreting its input as a sequence of
  coin-flip outcomes and using these to ``randomly'' select integers,
  testing their primality and retrying until two primes are found. $f$
  then outputs the product $pq$. Since the Prime Number Theorem tells
  us that with probability $\nicefrac{1}{k}$ a randomly-chosen $k$ bit
  number will be prime, we can, with high probability, obtain two
  prime numbers $p$ and $q$ of length $\ell(k)$ bits using $k$ random
  bits, for some polynomial $\ell(k)$.

  $f$ is a one-way function: it can be computed in polynomial time
  since generating random numbers and verifying their primality can be
  done in polynomial time. We claim it also satisfies the hardness
  condition:
  \begin{multline*}
    \forall \mathcal{ADV} \in \mathsf{PPTF}\quad \forall c \quad \exists
    k_0 \forall k > k_0 \\
    \Pr{x \gets \kstrings ;\; y \gets f(x) ;\; z \gets
      \mathcal{ADV}(\mathtt{1}^k,y):\; f(z) = y} < \frac{1}{k^c}
  \end{multline*}
  To see this, observe that by the construction of $f$, $y$ is chosen
  from the set $\set{pq: \;p \gets \mathsf{PRIMES}_{\ell(k)} ; \; q
    \gets \mathsf{PRIMES}_{\ell(k)}}$, so to invert $f$, the adversary
  $\mathcal{ADV}$ must recover $p$ or $q$. The factoring hardness
  assumption states that its probability of success is less than
  $\frac{1}{\ell(k)^c} < \frac{1}{k'^c}$ for some sufficiently large
  choice of $k'$.
\end{pset}
\end{document}