\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{6}{January 14, 2017}{Nir Bitansky}{January February 4}
\paragraph{Instructions:}
\begin{itemize}
\item
Type your solution and email it to "focf17hw@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}
\def \ZZ {\mathbb{Z}}
\bigskip
\begin{enumerate}
\item
In this question, let $binLWE_{q,B}$ be the same assumption as $LWE_{q,B}$ defined in class with the exception that the secret $s$ is sampled uniformly at random from $\zo^n$ instead of $\ZZ_q^n$. In what follows, let $\chi=\chi_n$ be the $B$-bounded distribution on $\ZZ_q$ given by $binLWE_{q,B}$ and assume that $q$ is a prime of size $\Theta(2^{\sqrt{n}})$ and $B\leq \sqrt{q}$.
Consider the following secret-key bit-encryption scheme:
\begin{itemize}
\item
The secret key is $sk = (-1,s)$ where $s\gets \zo^n$.
\item
To encrypt $m\in \zo$, sample $a\gets \ZZ_q^n$ and $e\gets \chi$, and output $ct = (\langle a,s\rangle +2e + m,a)$.
\item
To decrypt $ct$, output $[\langle sk, ct \rangle]_q \mod 2$ where for any $a\in \ZZ_q$, $[a]_q$ is the unique value in $[\frac{-q+1}{2},\frac{q-1}{2}]$ such that $a=[a]_q \mod q$.
\end{itemize}
\begin{enumerate}
\item (15 pts) Prove that under $binLWE_{q,B}$, the scheme is CPA secure.\footnote{Hint: recall that $2$ has a multiplicative inverse modulo $q$.}
\item (15 pts) Prove that the scheme supports any polynomial number of homomorphic Xor operations.
\item (10 pts) Prove that under $binLWE_{q,B}$, the scheme is {\em circular secure} --- the scheme is CPA secure even when the adversary gets as input encryptions of the bits of $sk$.
\item
(Bonus: M.Sc. thesis) Construct a boostrappable FHE scheme. That is, a homomorphic encryption scheme that is circular secure and can evaluate its own decryption circuit.
\end{enumerate}
\item
Let $(E,D)$ be a secret-key bit-encryption scheme that is homomorphic to Xor, and assume that each bit encryption is of size $n$ (this concerns both fresh encryption and encryptions that have been homomorphically manipulated).For two ciphertexts $ct$ and $ct'$, we will denote by $ct \widehat \oplus ct'$ the ciphertext resulting from their {\bf homomorphic} Xor, for two bits $b$ and $b'$ we denote by $b\oplus b'$ their Xor.
Consider the following suggestions for a public-key encryption scheme:
\begin{itemize}
\item
Sample $r \gets \zo^{2n}$, $sk\gets \zo^n$.\\ The public key $pk$ consists of $(r,ct_1,\dots,ct_{2n})$, where $ct_i \gets E_{sk}(r_i)$.\\ The secret key is $sk$.
\item
To encrypt $m\in \zo$, sample $x\gets \zo^{2n}$ and output $(a,b) = \(\widehat\bigoplus_{i:x_i=1} ct_i, m \oplus \(\bigoplus_{i:x_i=1} r_i\)\)$
\item
To decrypt $(a,b)$, output $D_{sk}(a) \oplus b$.
\end{itemize}
\begin{enumerate}
\item (20 pts) Prove that if the original secret-key scheme is CPA secure then so is the constructed public-key scheme.
\item (20 pts) Assume that the original secret-key scheme is fully homomorphic, show that so is the new public-key scheme. You can assume that homomorphic evaluation can reoperate on ciphertexts that are themselves the result of homomorphic evaluation (as in all constructions we've seen).
\end{enumerate}
\item
We say that a public-key encryption scheme $(G,E,D)$ is secure against chosen-ciphertext attacks (CCA-secure) if for any n.u. PPT $A=\set{A_n}$ there is a negligible $\mu$, such that it wins the following game with probability at most $1/2+\mu(n)$.
\begin{itemize}
\item
The challenger samples $(sk,pk)\gets G(1^n)$.
\item $A$ obtains the public key $pk$, and can perform decryption queries; namely, it can submit ciphertexts $ct$ and obtain $D_{sk}(ct)$.
\item $A$ submits two messages $m_0,m_1\in \zo^n$ and obtains a challenge ciphertext $ct^*=E_{pk}(m_b)$ for a random $b\gets \zo$.
\item $A$ may perform more decryption queries.
\item $A$ outputs a guess $b'$.
\item $A$ wins if $b=b'$ and for all queries $ct$ that it made $ct\neq ct^*$.
\end{itemize}
\begin{enumerate}
\item (20 pts) Show that any CCA-secure scheme is non-malleable in the following sense. For any n.u. PPT $A=\set{A_n}$ and any collection of non-constant poly-time functions $f=\set{f_n:\zo^n\rightarrow\zo^n}$, there is a negligible $\mu$, such that for any $n\in \Nat$ and any $m,m'\in \zo^n$
$$
\abs{\Pr\[\begin{array}{c} ct \gets A(pk,ct^*)\\ ct\neq ct^*\\ D_{sk}(ct)=f_n(m) \end{array}\pST \begin{array}{c}(sk,pk) \gets G(1^n)\\ ct^* \gets E_{pk}(m)\end{array}\]-\Pr\[\begin{array}{c} ct \gets A(pk,ct^*)\\ ct\neq ct^*\\ D_{sk}(ct)=f_n(m) \end{array}\pST \begin{array}{c}(sk,pk) \gets G(1^n)\\ ct^* \gets E_{pk}(m')\end{array}\]}\leq \mu(n)\enspace.
$$
\item (Bonus: 10 pts) Let $(Gen,Sign,Ver)$ be a one-time signature scheme such that $G(1^n)$ outputs verification keys of size $n$. Let $(G,IDG,E,D)$ be an identity-based public-key encryption scheme for identities in $\zo^n$. Consider the following public-key encryption scheme:
\begin{itemize}
\item
Sample $(msk,pk) \gets G(1^n)$
The secret key is $msk$ and the public key is $pk$.
\item
To encrypt $m\in \zo^n$, sample signing and verification keys $(k,vk) \gets Gen(1^n)$, compute $c = E_{pk}(m,vk)$ (an encryption of $m$ under id $vk$) and $\sigma = Sign_{k}(c)$. Output $ct = (c,vk,\sigma)$.
\item
To decrypt $ct=(c,vk,\sigma)$, if $Ver_{vk}(c,\sigma)=0$ output $\bot$, else derive $sk_{vk} \gets IDG(msk,vk)$, and output $D_{sk_{vk}}(c)$.
\end{itemize}
Prove that the scheme is CCA secure.
\end{enumerate}
\end{enumerate}
\end{document}