%me=0 student solutions, me=1 - my solutions, me=2 - assignment
\def\me{0}
\def\num{3} %homework number
\def\due{Dec. 10, 2015} %due date
\def\course{CS-7880 Graduate Cryptography} %course name
\def\name{}
%
\iffalse
INSTRUCTIONS: replace # by the homework number.
(if this is not ps#.tex, use the right file name)
Clip out the ********* INSERT HERE ********* bits below and insert
appropriate TeX code. Once you are done with your file, run
``latex ps#.tex''
from a UNIX prompt. If your LaTeX code is clean, the latex will exit
back to a prompt. To see intermediate results, type
``xdvi ps#.dvi'' (from UNIX prompt)
``yap ps#.dvi'' (if using MikTex in Windows)
after compilation. Once you are done, run
``dvips ps#.dvi''
which should print your file to the nearest printer. There will be
residual files called ps#.log, ps#.aux, and ps#.dvi. All these can be
deleted, but do not delete ps1.tex. To generate postscript file ps#.ps,
run
``dvips -o ps#.ps ps#.dvi''
I assume you know how to print .ps files (``lpr -Pprinter ps#.ps'')
\fi
%
\documentclass[11pt]{article}
\usepackage{tikz}
\usepackage{amsfonts}
\usepackage{latexsym}
\usetikzlibrary{automata,positioning}
\setlength{\oddsidemargin}{.0in}
\setlength{\evensidemargin}{.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}
\newcommand{\handout}[5]{
\renewcommand{\thepage}{#1, Page \arabic{page}}
\noindent
\begin{center}
\framebox{
\vbox{
\hbox to 5.78in { {\bf \course} \hfill #2 }
\vspace{4mm}
\hbox to 5.78in { {\Large \hfill #5 \hfill} }
\vspace{2mm}
\hbox to 5.78in { {\it #3 \hfill #4} }
}
}
\end{center}
\vspace*{4mm}
}
\newcounter{pppp}
\newcommand{\prob}{\arabic{pppp}} %problem number
\newcommand{\increase}{\addtocounter{pppp}{1}} %problem number
\newcommand{\newproblem}[2]{\increase
\section*{Problem \prob~(#1) \hfill {#2}}}
\def\squarebox#1{\hbox to #1{\hfill\vbox to #1{\vfill}}}
\def\qed{\hspace*{\fill}
\vbox{\hrule\hbox{\vrule\squarebox{.667em}\vrule}\hrule}}
\newenvironment{solution}{\begin{trivlist}\item[]{\bf Solution:}}
{\qed \end{trivlist}}
\newenvironment{solsketch}{\begin{trivlist}\item[]{\bf Solution Sketch:}}
{\qed \end{trivlist}}
\newenvironment{code}{\begin{tabbing}
12345\=12345\=12345\=12345\=12345\=12345\=12345\=12345\= \kill }
{\end{tabbing}}
\newcommand{\eqref}[1]{Equation~(\ref{eq:#1})}
\newcommand{\hint}[1]{({\bf Hint}: {#1})}
%Put more macros here, as needed.
\newcommand{\room}{\medskip\ni}
\newcommand{\brak}[1]{\langle #1 \rangle}
\newcommand{\bit}{\{0,1\}}
\newcommand{\zo}{\{0,1\}}
\newcommand {\eps} {\varepsilon}
\newcommand{\nin}{\not\in}
\newcommand{\set}[1]{\{#1\}}
\renewcommand{\ni}{\noindent}
\renewcommand{\gets}{\leftarrow}
\renewcommand{\to}{\rightarrow}
\newcommand{\assign}{:=}
\newcommand{\AND}{\wedge}
\newcommand{\OR}{\vee}
\newcommand{\For}{\mbox{\bf For }}
\newcommand{\To}{\mbox{\bf to }}
\newcommand{\Do}{\mbox{\bf Do }}
\newcommand{\If}{\mbox{\bf If }}
\newcommand{\Then}{\mbox{\bf Then }}
\newcommand{\Else}{\mbox{\bf Else }}
\newcommand{\While}{\mbox{\bf While }}
\newcommand{\Repeat}{\mbox{\bf Repeat }}
\newcommand{\Until}{\mbox{\bf Until }}
\newcommand{\Return}{\mbox{\bf Return }}
\newcommand{\KeyGen}{\mathsf{KeyGen}}
\newcommand{\Enc}{\mathsf{Enc}}
\newcommand{\Dec}{\mathsf{Dec}}
\newcommand{\MAC}{\mathsf{MAC}}
\newcommand {\A} {\mathcal{A}}
\newcommand {\K} {\mathcal{K}}
\newcommand {\C} {\mathcal{C}}
\newcommand {\M} {\mathcal{M}}
\newcommand {\T} {\mathcal{T}}
\newcommand {\U} {\mathcal{U}}
\newcommand {\V} {\mathcal{V}}
\newcommand {\ZZ} {\mathbb{Z}}
\newcommand {\FF} {\mathbb{F}}
\newcommand {\NN} {\mathbb{N}}
\newcommand {\RR} {\mathbb{R}}
\def \SD {\mathsf{SD}}
\def \hinf {H_{\infty}}
\def \poly {\mathsf{poly}}
\def \negl {\mathsf{negl}}
\def \GroupGen {\mathsf{GroupGen}}
\def \G {\mathbb{G}}
\def \Commit {\mathsf{Commit}}
\begin{document}
\ifnum\me=0
\handout{PS\num}{\today}{Name: }{Due:
\due}{Solutions to Problem Set \num}
I collaborated with *********** INSERT COLLABORATORS HERE (INDICATING
SPECIFIC PROBLEMS) *************.
\fi
\ifnum\me=1
\handout{PS\num}{\today}{Name: Daniel Wichs}{Due: \due}{Solution
{\em Sketches} to Problem Set \num}
\fi
\ifnum\me=2
\handout{PS\num}{\today}{Lecturer: Daniel Wichs}{Due: \due}{Problem
Set \num}
\fi
\newproblem{Public Key Encryption -- Decryption Query}{20 pts}
The security definition of public-key encryption that we gave in class gives the adversary the public key which allows him to encrypt arbitrary messages himself. However, it doesn't consider that an adversary might be able to see how ciphertexts are decrypted. In this problem, you're to show that in general this can make a cryptosystem completely insecure.
\paragraph{A.} Show that, if there exists any secure public key encryption scheme $\mathcal{E} = (\KeyGen, \Enc,\Dec)$ according to the definition we gave in class then you can modify it to get an encryption scheme $\mathcal{E}' = (\KeyGen', \Enc', \Dec')$ such that:
\begin{itemize}
\item $\mathcal{E}'$ is a secure encryption scheme according to the definition we gave in class.
\item $\mathcal{E}'$ has the property that, if the attacker can query the decryption function $\Dec'(sk, \cdot)$ even on a single ciphertext $c$ of his choosing and see the output $m = \Dec(sk, c)$ then the attacker can completely recover the secret key $sk$.
\end{itemize}
This is a very undesirable property - if the attacker can learn a single decrypted value (for a ciphertext of his choosing) he can completely break security of the scheme. We will see how to define stronger notions of security that prevent this later on in the class.
\ifnum\me=0
\begin{solution}
***************** INSERT SOLUTION HERE ***************
\end{solution}
\fi
\paragraph{B.} You solution in part A might have been a ``contrived'' scheme which is not very ``natural''. But there are natural schemes that are completely insecure if an adversary can see decryptions of chosen messages -- for example, schemes based on the Rabin trapdoor permutation. Let $N = pq$ be a product of two primes and let $f~:~ QR_N \rightarrow QR_N$ be the Rabin trapdoor permutation defined by $f(x) = x^2 ~\bmod N$. We know this permutation is easily invertible given $p,q$. Show that if an adversary can query $f^{-1}(y)$ for a single value $y$ of its choosing than it can efficiently factor $N$ with non-negligible probability.
\ifnum\me=0
\begin{solution}
***************** INSERT SOLUTION HERE ***************
\end{solution}
\fi
\newproblem{Hedging You Bets}{5 pts}
Assume you have two public-key encryption schemes $\mathcal{E} = (\KeyGen, \Enc,\Dec)$ and $\mathcal{E}' = (\KeyGen', \Enc',\Dec')$. You believe that at least one of them has to be secure but not necessarily both. Construct an encryption scheme $\mathcal{E}^* = (\KeyGen^*, \Enc^*,\Dec^*)$ which is secure as long as at least one of $\mathcal{E}$ or $\mathcal{E}'$ is secure.
\ifnum\me=0
\begin{solution}
***************** INSERT SOLUTION HERE ***************
\end{solution}
\fi
\newproblem{Commitments}{20 pts}
A commitment scheme allows Alice to ``commit'' herself to some message $m$ by giving Bob some value $c = \Commit(m,r)$ generated using randomness $r$. Bob should not learn anything about $m$ given the commitment $c$. Later she can ``open'' the commitment by giving $(m,r)$ to Bob to convince him that $m$ was the value she committed herself to. We will assume that $m \in \bit{}$ is just a single bit -- we can always extend this to a longer message by committing one bit at a time.
Formally, a commitment is a function $\Commit~:~\bit \times \bit^* \rightarrow \bit^*$ that should satisfy the following properties.
\begin{itemize}
\item Hiding: The commitments to $0$ and $1$ are computationally indistinguishable $\Commit(0,U_n) \approx \Commit(1,U_n)$ where $U_n$ denotes the uniform distribution over $\bit^n$.
\item Binding: For all PPT adversaries $A$, we have
$$ \Pr[ \Commit(0,r) = \Commit(1,r') : (r,r') \gets A(1^n)] = \negl(n).$$
\end{itemize}
\paragraph{A.} Show that commitments imply the existence of one-way functions.
\ifnum\me=0
\begin{solution}
***************** INSERT SOLUTION HERE ***************
\end{solution}
\fi
\paragraph{B.} You will now show how to construct a generalized notion of such commitments, which we'll call seeded commitments, from one-way functions. A seeded commitment also contains a seed $s$ and we define the commitment function as $\Commit_s(m,r)$ which takes the seed $s$ as an input. We think of Bob as generating the seed $s$ and therefore we want hiding to hold even if $s$ is chosen maliciously. On the other hand, we want binding to hold when $s$ is chosen randomly. Give a formal definition of the hiding and binding properties for seeded commitments to capture this intuitive description.
Consider the following scheme: Let $G$ be a PRG with $2n$-bit stretch, so that for $|r| =n$, $|G(r)| = 3n$. Let $s \gets \bit^{3n}$ be a random string of length $3n$. Define
$\Commit_s(m, r)$ to be $G(r)$ if $m=0$ and $G(r) \oplus s$ if $m=1$. Show that this scheme satisfies the definition of seeded commitments, and that the binding property holds even if the adversary is computationally unbounded.
\ifnum\me=0
\begin{solution}
***************** INSERT SOLUTION HERE ***************
\end{solution}
\fi
\paragraph{C.} Show that the above scheme could potentially be insecure if we defined $s$ to be some fixed string, say all $1$s, rather than choosing it randomly. To do so, show that if PRGs exist then there exists a PRG $G$ for which such scheme would be insecure.
\ifnum\me=0
\begin{solution}
***************** INSERT SOLUTION HERE ***************
\end{solution}
\fi
\paragraph{D.} In the scheme from part B, the hiding property holds when the adversary is computationally bounded but binding holds even if the adversary is computationally unbounded. We could ask whether the reverse is also possible.
Consider the following commitment scheme based on the discrete-logarithm assumption. The seed $s$ consists of $ s = (\G,q,g,h)$ where $(\G,q,g) \gets \GroupGen(1^n)$ is a description of a cyclic group $\G$ of prime order $q$ with generator $g$, and $h \gets \G$ is a random group element. We define $\Commit_s(m;r) = g^m h^r$ where $m \in \bit$, $r \in \ZZ_q$. (We're changing the syntax a little so that the randomness is uniform over $\ZZ_q$ rather than $\bit^n$. We could also allow $m$ to come from all of $\ZZ_q$ rather than just $\bit$ but let's stick with 1-bit messages to keep the syntax and the definitions consistent).
Show that the above scheme satisfies perfect hiding: for any $s$ (not necessarily random) the distributions $\Commit_s(0,r) \equiv \Commit_s(1,r)$ are identical over the choice of a random $r$. Show that, under the discrete logarithm assumption, the scheme is binding when $s$ is chosen randomly as specified above.
\ifnum\me=0
\begin{solution}
***************** INSERT SOLUTION HERE ***************
\end{solution}
\fi
\end{document}
%\newproblem{Secure or Insecure}{20 pts}
%
%Another edition of your favorite game: secure or insecure?
%
%
%Let $\mathcal{E} = (\KeyGen, \Enc,\Dec)$ be a public key encryption scheme. Are the following modified schemes $\mathcal{E}' = (\KeyGen', \Enc',\Dec')$ necesserally secure? If so give a proof, else give a coutnerexample showing that it is not always the case
%\begin{enumerate}
% \item We modify key generation as follows: $(pk', sk') \gets \KeyGen'(1^n)$ runs $(pk, sk) \gets \KeyGen(1^n)$ and $c^* \gets \Enc(pk, sk)$ where it encrypts the message $m=sk$ under $pk$. It outputs $pk' = (pk, c^*)$ and $sk' = sk$. The procedures $\Enc',\Dec'$ are the same as $\Enc,\Dec$ and simply ignore $c^*$. In other words, the only difference is that the adversary gets $c^*$ which is an encryption of $sk$ under $pk$ in addition to $pk$.
% \item This is the same as the previous problem, but we set $c^* \gets \Enc(pk, pk)$ where we encrypt the message $m = pk$ under $pk$.
%\end{enumerate}
%
%
%Let $\mathcal{S} = (\KeyGen, \Sign,\Verify)$ be a signature scheme. Are the following modified schemes $\mathcal{S}' = (\KeyGen', \Sign',\Verify')$ necesserally secure? If so give a proof, else give a coutnerexample showing that it is not always the case.
%\begin{enumerate}
% \item $\KeyGen'$ is the same as $\KeyGen$ but we modify $\Sign'(sk,m) = \Sign(sk, f(m))$ and $\Verify(vk, m, \sigma) = \Verify(vk, f(m), \sigma)$ where $f$ is a one-way function.
% \item $\KeyGen'$ is the same as $\KeyGen$ but we modify $\Sign'(sk, m) = \Sign(sk, )$ and $\Verify(vk, m, \sigma) = \Verify(vk, f(m), \sigma)$ where $f$ is a one-way function.
%\end{enumerate}