%% HOW TO USE THIS TEMPLATE:
%%
%% Ensure that you replace "YOUR NAME HERE" with your own name, in the
%% \studentname command below. Also ensure that the "answers" option
%% appears within the square brackets of the \documentclass command,
%% otherwise latex will suppress your solutions when compiling.
%%
%% Type your solution to each problem part within
%% the \begin{solution} \end{solution} environment immediately
%% following it. Use any of the macros or notation from the
%% header.tex that you need, or use your own (but try to stay
%% consistent with the notation used in the problem).
%%
%% If you have problems compiling this file, you may lack the
%% header.tex file (available on the course web page), or your system
%% may lack some LaTeX packages. The "exam" package (required) is
%% available at:
%%
%% http://mirror.ctan.org/macros/latex/contrib/exam/exam.cls
%%
%% Other packages can be found at ctan.org, or you may just comment
%% them out (only the exam and ams* packages are absolutely required).
% the "answers" option causes the solutions to be printed
\documentclass[11pt,addpoints]{exam}
\usepackage{amsmath,amsfonts,amssymb,amsthm}
% any of the following packages may be safely omitted if they are not
% available on your system (but they should be)
\usepackage{fullpage}
\usepackage{times}
\usepackage{hyperref}
\usepackage{pdfsync}
\usepackage{microtype}
% required macros -- get latest header.tex file from course web page
\input{header}
% VARIABLES
\newcommand{\hwnum}{2}
\newcommand{\duedate}{February 10} % changing this does not change the
% actual due date :)
\newcommand{\studentname}{YOUR NAME HERE}
% END OF SUPPLIED VARIABLES
\hwheader % execute homework commands
\begin{document}
\pagestyle{head} % put header on every page
\noindent This homework is due by the \textbf{start of class on
\duedate} via the
\href{https://t-square.gatech.edu/portal/site/29001.201102/}{course
page on T-Square}. Start early!
\medskip
\noindent \textbf{Instructions.} Solutions must be typeset in \LaTeX\
(a template for this homework is available on the course web page).
Your work will be graded on \emph{correctness}, \emph{clarity}, and
\emph{conciseness}. You should only submit work that you believe to
be correct; if you cannot solve a problem completely, you will get
significantly more partial credit if you clearly identify the gap(s)
in your solution. It is good practice to start any long solution with
an informal (but accurate) ``proof summary'' that describes the main
idea.
\medskip
\noindent You may collaborate with others on this problem set and
consult external sources. However, you must \textbf{\emph{write your
own solutions}} and \textbf{\emph{list your
collaborators/sources}} for each problem.
% QUESTIONS START HERE. PROVIDE SOLUTIONS WITHIN THE "solution"
% ENVIRONMENTS FOLLOWING EACH QUESTION.
% definitional problem: define some notion that turns out to be
% equivalent to pseudorandomness. incompressible?
\begin{questions}
\question \emph{(Number theory.)}
\begin{parts}
\part[6] Let $N$ be the product of two distinct $n$-bit primes,
and suppose there is an efficient algorithm $\Adv$ that computes
square roots on a noticeable fraction of quadratic residues mod
$N$: \[ \Pr_{y \gets \QRN^{*}}[\Adv(N, y) \in \sqrt{y} \bmod N] =
\delta \geq 1/\poly(n). \] Construct an efficient algorithm
$\AdvB$ that, using $\AdvA$ as an oracle, computes the square root
of \emph{any} $y \in \QRN$ with \emph{overwhelming} probability
(solely over the random coins of $\Adv$ and $\AdvB$). That is,
for every $y \in \QRN$, it should be the case that
\[ \Pr[\AdvB^{\AdvA}(N, y) \in \sqrt{y} \bmod N] = 1 - \negl(n). \]
\begin{solution}
\end{solution}
\part[4] We have seen in class that the ``most significant bit''
$[x > \tfrac{p-1}{2}]$ is a hard-core predicate for the modular
exponentiation function $f_{p,g}(x) = g^{x} \bmod p$, where $p >
2$ is prime, $g$ is a generator of $\Zp^{*}$, and $x \in \Zp^{*} =
\set{1, \ldots, p-1}$.
Prove that the ``least significant bit'' $[x \text{ is odd}]$ is
\emph{not} a hard-core predicate for $f_{p,g}$.
\begin{solution}
\end{solution}
\end{parts}
\question \emph{(Indistinguishability potpourri.)} Prove or
disprove (giving the simplest counterexample you can find) the
following statements. In constructing a counterexample, you may
assume the existence of another OWF / PRG / PRF.
\begin{parts}
\part[3] For a probability distribution $D$ over $\Omega$ and
positive integer $m$, let $D^{m}$ denote the \emph{product
distribution} over $\Omega^{m}$, obtained by drawing an tuple of
$m$ independent samples from $D$. Let $\calX = \set{X_{n}}$ and
$\calY = \set{Y_{n}}$ be ensembles of distributions that are
efficiently sampleable (in PPT), and let $m(n) = \poly(n)$.
If $\calX \compind \calY$, then $\set{X^{m(n)}_{n}} \compind
\set{Y^{m(n)}_{n}}$. (Why is it important that $X_{n}$, $Y_{n}$
be efficiently sampleable?)
\begin{solution}
\end{solution}
\part[3] If an injective (one-to-one) function $f$ has a hard-core
predicate $h$, then $f$ is one-way.
\begin{solution}
\end{solution}
\part[4] Let $G$ be a PRG with output length $\ell(n) > n$. The
function $G'(s) = G(s) \oplus (s | 0^{\ell(\len{s})-\len{s}})$ is
a PRG, where $|$ denotes concatenation.
\begin{solution}
\end{solution}
\part[5] A PRG $G$ with output length $\ell(n) = 2n$ is itself a
one-way function. (Why do we take $\ell(n) = 2n$ instead of, say,
$\ell(n) = n+1$?)
\end{parts}
\question In this problem, you will use a PRG to implement what
we'll call a secure ``locking'' scheme. A locking scheme is a
protocol between two players, a locker $L$ and a verifier $V$. It
allows $L$ to lock itself into one of two choices ($0$ or $1$)
without $V$ knowing which choice was made, then later reveal its
choice. The protocol works in two phases: in the first ``locking''
phase, $L$ and $V$ exchange some messages, which result in $L$ being
bound to its (secret) choice bit. In the second ``unlocking''
phase, $L$ reveals its choice bit and some additional information,
which allows $V$ to check consistency with the earlier messages.
We define the following model for a locking scheme, in which the
locking phase consists of an initial message from the verifier,
followed by a response from the locker.
\begin{itemize}
\item The verifier $V()$ is a PPT algorithm that takes no input
(except for the implicit security parameter $1^{n}$ and its random
coins) and outputs some message $v \in \bit^{*}$.
\item The locker $L(\sigma, v; r_{L})$ is a PPT algorithm that takes
a choice bit $\sigma \in \bit$, the verifier's initial message
$v$, and random coins $r_{L}$, and outputs some message $\ell \in
\bit^{*}$.
\end{itemize}
In the unlocking phase, the locker simply reveals $\sigma$ and
$r_{L}$, and the verifier checks that $\ell = L(\sigma, v; r_{L})$.
\begin{parts}
\part[3] A secure locking scheme should be ``hiding,'' i.e., a
malicious (but computationally \emph{bounded}) verifier $V^{*}$
should not be able to learn anything about the honest locker $L$'s
choice bit $\sigma$, no matter what initial message $v^{*}$ the
malicious verifier sent.
Using the notion of indistinguishability, give a formal definition
of this hiding property.
\begin{solution}
\end{solution}
\part[3] A secure locking scheme should also be ``binding''
against even a computationally \emph{unbounded} malicious locker
$L^{*}$. That is, there should not exist any $\ell^{*}$ that can
successfully be unlocked as both choice bits $\sigma \in \bit$,
except with negligible probability over the choice of the honest
verifier $V$'s initial message $v$.
Give a formal definition of this binding property.
\begin{solution}
\end{solution}
\part[3] Let $G$ be any length-tripling function, i.e., one for
which $\len{G(x)} = 3 \len{x}$ for every $x \in \bit^{*}$. Give
an upper bound on the probability, over the choice of a random
$3n$-bit string $R$, that there exist two inputs $x_{1}, x_{2} \in
\bit^{n}$ such that $G(x_{1}) \oplus G(x_{2}) = R$.
\begin{solution}
\end{solution}
\part[6] Let $G$ be a length-tripling PRG (which we have seen can
be obtained from any PRG). Use $G$ to construct a secure locking
scheme, and prove that it is both hiding and binding according to
your definitions.
\begin{solution}
\end{solution}
\end{parts}
\end{questions}
\end{document}
%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End: