\documentclass[11pt]{article}

\usepackage{
  latexsym,
  amsfonts,
  amssymb,
  amsthm,
  stmaryrd,
  pdfsync,
  graphicx,
  framed,
  empheq,
  physics,
}
\usepackage[hidelinks]{hyperref}
\usepackage{cleveref}
\usepackage[
  margin=1in,
]{geometry}

\theoremstyle{definition}

\newcommand{\hint}[1]{Hint: \emph{#1}}
\newcommand{\bit}{\{0,1\}}
\newcommand{\adv}{\mathcal{A}}

\newcommand{\word}[1]{\mathsf{#1}}
\newcommand{\many}[1]{\mathit{#1}}

\newcommand{\ensem}[2]{\left\{~#1~\left\lvert\begin{array}{l}#2\end{array}\right.\right\}}
\newcommand{\ensemline}[2]{\left\{~#1~\left\lvert~~#2~\right.\right\}}
\newcommand{\prob}[2]{\mathrm{Pr}\left[~#1~\left\lvert\begin{array}{l}#2\end{array}\right.\right]}
\newcommand{\probline}[2]{\mathrm{Pr}\left[~#1~\left\lvert~~#2~\right.\right]}

\newcommand{\G}{\mathbb{G}}
\newcommand{\Z}{\mathbb{Z}}

\newtheorem{problem}{Problem}
\newtheorem{definition}{Definition}
\newtheorem{solution}{Solution}

\title{CS/ECE407 Cryptography -- Homework 4\\
  Hash Functions and Public Key Cryptography}
\author{}
\date{Due: Thursday, April 16, 3:30PM CT}

\begin{document}

\maketitle

Remember, you are free to collaborate with up to one classmate.
See the course webpage for more details.
You are expected to write out and submit your own solutions!
Your collaboration is for discussing problems at a high level, not plagiarizing answers.

Your solutions should be typed or carefully handwritten.
We provide a \LaTeX\ template for this document, if you would like to use it as a starting point.
\textbf{If we cannot read your handwritten answers, they will not receive credit.}

Typed solutions should be submitted through Gradescope (see course webpage).
Hand-written solutions should be scanned and turned in through Gradescope.

\pagebreak

\begin{figure}
\begin{framed}
  \begin{definition}[Collision Resistance]\label{defn:collision_resistant}
    A hash function $H$ with seeds from $S$ is \textbf{collision resistant} if for any polytime adversary $\adv$, the following probability is negligible: 
\begin{align*}
  \prob{
    H(s, x_0) = H(s, x_1)
  }{
    s \gets S(1^\lambda)\\
    (x_0, x_1) \gets \adv(1^\lambda, s)
  } < \mathrm{negl}(\lambda)
\end{align*}
\end{definition}
\end{framed}
\end{figure}

\begin{figure}
\begin{framed}
  \begin{definition}[Discrete Logarithm Hardness]\label{defn:dlog}
    Let $\G_\lambda$ denote a family of cyclic groups with respective generators $g_\lambda$.
    We say that the discrete logarithm problem for this family is hard if for any polytime adversary $\adv$, the following probability is negligible:
    \begin{align*}
      \prob{
        x = y
      }{
        q = |\G_\lambda|\\
        x \gets \Z_q\\
        y \gets \adv(1^\lambda, g_\lambda^x)
      }
      < \mathrm{negl}(\lambda)
    \end{align*}
  \end{definition}
  Informally, we sample a random exponent $x$, give $g^x$ to the adversary, and
  the adversary wins if it outputs $x$.
\end{framed}
\end{figure}

\begin{problem}[Hash Functions]
  Let $h : \bit^\lambda \times \bit^{2\lambda} \rightarrow \bit^\lambda$ be a collision resistant hash function whose seeds are uniformly sampled from $\bit^\lambda$.
Consider the following function $H : \bit^\lambda \times \bit^{3\lambda} \rightarrow \bit^\lambda$ which splits input $x$ into three length-$\lambda$ strings, then calls $h$ twice:

\begin{align*}
  &H(s, x):\\
  &~~(x_0, x_1,x_2) = \word{thirds}(x)\\
  &~~\word{return}~ h(s, h(s, x_0~|~x_1)~|~ x_2)
\end{align*}
\begin{enumerate}
  \item \textbf{(2 points)} $H$ is also collision resistant. Give a security
    reduction that proves this.
  \item \textbf{(2 points)} $H$ is well-defined only for inputs $x$ of length exactly $3\lambda$.
    Use $h$ to construct a hash function $H'$ that is well-defined for any input $x$ that has length \emph{strictly less} than $3\lambda$.
    Give a security reduction that proves your $H'$ is collision resistant.
  \item \textbf{(2 points)} 
    Now, use $h$ to construct a collision-resistant function $H''$ that is well-defined for inputs $x$ of \emph{any} polynomial length.
    Give one or two sentences that informally argument why your $H''$
    is collision resistant; you do not need to prove this formally.
\end{enumerate}
\end{problem}
% \begin{solution}
%   Your solution goes here!
% \end{solution}

\begin{problem}[Discrete Logarithms and Collision Resistance]
  Let $\G_\lambda, g_\lambda$ denote a family of discrete-log-hard groups (see \Cref{defn:dlog}).
  Now, consider the following hash function definition.
  First, its seeds are drawn as follows:
  \begin{align*}
    S(1^\lambda) = \ensem{
      (g, h)
    }{
      q \gets |\G_\lambda|\\
      g \gets g_\lambda\\
      x \gets \Z_q\\
      h \gets g^x
    }
  \end{align*}
  That is, we choose a group depending on $\lambda$, then sample a random group element $h$.
  Now, the hash function $H$ takes a seed $(g, h)$ and two integers $(a, b)$ and outputs a single group element as follows:
  \begin{align*}
    H((g, h), (a, b)) = g^ah^b
  \end{align*}
  \begin{itemize}
    \item \textbf{(3 points)}
      Give a security reduction showing that if the discrete logarithm problem
      is hard for groups $\G_\lambda$, then $H$ is a collision resistant hash
      function.
      \hint{
        Remember, this means that if $H$ is \emph{not} collision resistant---i.e., if there exists an efficient adversary that finds collisions with noticeable probability---then there should also be an adversary that computes discretes logarithms.
      }
  \end{itemize}
\end{problem}
% \begin{solution}
%   Your solution goes here!
% \end{solution}



\begin{problem}[Public Key Encryption]
  \begin{enumerate}
    \item[]
    \item 
      \textbf{(2 points)}
      It is crucial to use randomized encryption when using public keys. 
      Suppose that we use a deterministic public-key encryption algorithm $\many{Enc}(\many{pk}, m)$.
      Describe an adversary that can decrypt a ciphertext from any such scheme in time that scales linearly in $|\mathcal{M}|$ where $\mathcal{M}$ is the scheme's message space.
    \item
    \textbf{(3 points)}
      Consider the following attempt at key exchange:
      \begin{enumerate}
        \item Alice samples random key $k \gets \bit^\lambda$ and random mask $r \gets \bit^\lambda$.
          Alice sends $s = k \oplus r$ to Bob.
        \item Bob samples $t \gets \bit^\lambda$ and sends $u = t \oplus s$ to Alice.
        \item Alice computes $w = u \oplus r$ and sends $w$ to Bob.
        \item Alice outputs $k$; Bob outputs $w \oplus t$.
      \end{enumerate}
      Is the protocol correct? Namely do Alice and Bob compute the same key?
      Is the protocol secure? Why/why not?
  \end{enumerate}
\end{problem}
% \begin{solution}
%   Your solution goes here!
% \end{solution}

\end{document}
