\documentclass[10pt]{article}
\usepackage{amsfonts,amsthm,amsmath,amssymb}
\usepackage{array}
\usepackage{epsfig}
\usepackage{fullpage}
\usepackage[table]{xcolor}
\usepackage{adjustbox}
\usepackage{dashbox}
\usepackage{cjhebrew}
\usepackage{xspace}

\begin{document}
\input{preamble.tex}

\lecture{4}{December 19, 2019}{Nir Bitansky}{January 2}

\paragraph{Instructions:}
\begin{itemize}

  \item
  Type your solution and email it to "focf19hw@gmail.com", with subject "HW\#, ID\#, Name".
  \item
  You're encouraged to use latex. You can find on the webpage the assignment's tex file to help you.
  \item
  You can cooperate. However, you should write the solution by yourself, and list all collaborators for each question. Same goes for any external sources that you may use.
  \item
  Do not discuss solutions over the course's forum. You are more than welcome though to ask for clarifications regarding the questions themselves.
\end{itemize}

\bigskip
\begin{enumerate}
\item
In this question, we will understand the relations between the different security notions of encryption. In what follows, let $(G,E,D)$ be an encryption scheme. To present the definitions in a way that applies to both the secret and the public settings we shall agree that $G(1^n)$  outputs three keys $(sk,ek,pk)$:
\begin{itemize}
\item
$sk$ is the secret decryption key.
\item
$ek$ is an encryption key.
\item
$pk$ is a public key.
\item
In the secret key setting, $ek=sk$ and $pk$ is empty, whereas in the public-key setting $ek=pk$.
\end{itemize}
We consider the following security notions:
\vspace{-2mm}
\paragraph{Known Plaintext Attacks:} The scheme is $t$-message KPA-secure, for a polynomially bounded function $t$, if any n.u. PPT adverasry $A=\set{A_n}$ wins the following game with probability at most $1/2+\mu(n)$ for some negligible $\mu$.
\begin{itemize}
\item
$A_n$ submits $t(n)$ pairs of equal length messages $(m_{0,1},m_{1,1}),\dots,(m_{0,t},m_{1,t})$.
\item
$A_n$ obtains $pk,Enc_{ek}(m_{b,1}),\dots,Enc_{ek}(m_{b,t})$ for a random $b\gets \zo$.
\item
$A_n$ outputs a bit $b'$, and wins if $b=b'$.
\end{itemize}

\vspace{-2mm}
\paragraph{Chosen Plaintext Attacks:} The scheme is CPA-secure, if any n.u. PPT adverasry $A=\set{A_n}$ wins the following game with probability at most $1/2+\mu(n)$ for some negligible $\mu$.
\begin{itemize}
\item
$A_n$ obtains $pk$.
\item
$A_n$ can repeatedly submit a message $m$ and obtain an encryption $E_{ek}(m)$.
\item
$A_n$ submits two equal-length messages $m_0,m_1$ and obtains $Enc_{ek}(m_{b})$ for a random $b\gets \zo$.
\item
$A_n$ can once more repeatedly submit a message $m$ and obtain an encryption $E_{ek}(m)$.
\item
$A_n$ outputs a bit $b'$, and wins if $b=b'$.
\end{itemize}
Show that:
\begin{enumerate}
  \item (20 pts) Any scheme that is CPA-secure is also $t$-message KPA-secure for any polynomial $t$ (in either the secret-key or public-key setting).
  \item ({\bf Bonus:} 10 pts) If there exist secret-key encryption schemes that are $t$-message KPA-secure for any polynomial $t$, than there exist ones that are not CPA secure.
      \item (20 pts) Any public-key bit-encryption scheme that is $1$-message KPA-secure is CPA secure.

\end{enumerate}

\newpage
\item
In this question, we'll construct a two-message bit commitment scheme based on PRGs. Let $G:\zo^n\rightarrow\zo^{3n}$ be a length-tripling PRG. Consider the following protocol between a sender $S$ and a receiver $R$:
\begin{itemize}
\item
$R$ samples a random string $r\gets \zo^{3n}$ and sends it to $S$.
\item
$S$ samples $s\gets \zo^n$, and commits to a bit $b$, by sending $Com_r(b;s)$ defined by:
\begin{itemize}
  \item $G(s)$ if $b=0$,
  \item $G(s)\oplus r$ if $b=1$.
\end{itemize}
\end{itemize}
Show that the commitment is:
\begin{itemize}
  \item (15 pts) {\bf Binding:} with overwhelming probability over the choice of $r$, the commitment is binding:
  $$
  \Pr_{r\gets \zo^{3n}}\[\exists s_0,s_1: Com_r(0;s_0)=Com_r(1;s_1)\]\leq 2^{-n}\enspace.
  $$
  \item (15 pts) {\bf Hiding:} for every (even malicious) choice of $r$, the sender's message is computationally-hiding:
  $$
  \set{Com_r(0;U_n)}_{\begin{subarray}{l}n\in\Nat\\r\in\zo^{3n}\end{subarray}} \approx_c \set{Com_r(1;U_n)}_{\begin{subarray}{l}n\in\Nat\\r\in\zo^{3n}\end{subarray}}\enspace.
  $$

\end{itemize}



%\begin{itemize}
%  \item {\bf Computational Hiding:} for any malicious n.u. PPT receiver $R^*$,
%  $$
%  \set{\prot{S(m_0)}{R^*}}_{\begin{subarray}{c}n\in\Nat\\
%  m_0,m_1\in \zo^n\end{subarray}} \approx_c \set{\prot{S(m_1)}{R^*}}_{\begin{subarray}{c}n\in\Nat\\
%  m_0,m_1\in \zo^n\end{subarray}}\enspace,
%  $$
%  where $\prot{S(m_0)}{R^*}$ denotes the output of $R^*$ after interacting with $S$ that commits to $m_0$.
%  \item
%\end{itemize}
%\end{definition}

\item
(30 pts) Consider the NP language of solvable Soduko puzzles. That is, all $n^2\times n^2$ matrices over values $\set{\bot}\cup [n^2]$ for which the values $\bot$ can be replaced with values in $[n^2]$, so that every line , column, or $n\times n$ subsquare contain the values $[n^2]$. (By subsquare here we mean the entries corresponding to the intersection of rows $in+1,\dots,in+n$ with columns $in+1,\dots,in+n$ for some $i,j\in \set{0,\dots,n-1}$.)

Describe a zero-knowledge proof for this language, based on non-interactive commitments, with perfect completeness, soundness error $s\leq 1- n^{-O(1)}$, and expected poly-time simulator. Re zero-knowledge, you can describe the simulator, without writing the proof of its validity and run-time.

\end{enumerate}


\end{document}