\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}
\usepackage{url}
\usepackage{hyperref}
% packages for the graphs:
%\usepackage{tikz}
%\usepackage{tikz-qtree}
\begin{document}
\input{preamble.tex}
\lecture{12: {\large Functional Encryption}}{January 11, 2018}{Nir Bitansky}{ }
\section{Previously on Foundations of Crypto}
We've started exploring new cryptographic tools developed in recent years and targeted mostly to protecting various forms of delegated information and computation. Last week, we learned about fully-homomorphic encryption. Today, we'll learn about another powerful tool known as {\em functional encryption} (FE).
\section{Functional Encryption}
One limitation of FHE is that encrypted data processed on the cloud will always stay encrypted. In particular, to act upon the result of a computation, the server must send the encrypted $Enc(f(x))$ back to the client for decryption. For instance, consider a spam filter that sits on our email server. We would like the server to only forward non-spam messages, can we do it over encrypted messages? clearly, for the server to avoid sending us spam, it must at least learn that an encrypted message is spam. If it simply runs the spam filter homomorphically, it will only get an encryption of the result, and will not be able to decide.\footnote{FHE would still let us save some of the work on the client side, by tagging the email as spam under the encryption, the client would be able to first decrypt only this short tag, and accordingly decide whether to process the rest.} Somehow, we would like that the server would be able to learn if the message was spam, but nothing beyond regarding its contents.
FE is a tool that allows for such fine-grained control of encrypted data. Roughly speaking, it allows generating partial decryption keys $sk_f$ associated with functions $f$ (e.g., a spam filter), so that someone in possession of this key and an encryption of $m$, can learn $f(m)$ but nothing else regarding $m$. We will define the public key variant of FE.
\scribes{add Fig 1}
\begin{definition}[Functional Encryption]
A public-key functional encryption scheme consists of PPT algorithms $(G,KG,E,D)$ satisfying:
\begin{itemize}
\item
{\bf syntax:}
\begin{itemize}
\item $G(1^n)$ outputs a master secret key $msk$ and a public key $pk$.
\item $KG(msk,f)$ takes the master secret key $msk$ and circuit $f:\zo^n\rightarrow\zo^*$ and outputs a function key $sk_f$.
\item $E_{pk}(m)$ given the public key $pk$ and message $m\in\zo^n$, outputs a ciphertext $ct$.
\item $D_{sk_f}(ct)$ takes a function key $sk_f$ and a ciphertext $ct$ and outputs a value $y$.
\end{itemize}
\item
{\bf Functionality:} for any $f$, $m\in \zo^n$,
$$
\Pr\[D_{sk_f}(ct) = f(m) \pST \begin{array}{c} msk,pk\gets G(1^n)\\ sk_f\gets KG(msk,f)\end{array}\] = 1\enspace.
$$
\item
{\bf Indistinguishability:} for any n.u. PPT $A=\set{A_n}$ there is a negligble $\mu$ such that it wins the following game with probability at most $1/2+\mu(n)$:
\begin{itemize}
\item $A$ obtains the public key, and can ask for functional keys for $f$ of her choice.
\item $A$ submits two messages $m_0,m_1\in \zo^n$ and obtains a ciphertext $ct=E_{pk}(m_b)$ for a random $b\gets \zo$.
\item $A$ may ask for more function keys.
\item $A$ outputs a guess $b'$.
\item $A$ wins if $b=b'$ and for all queries $f$ that it made $f(m_0)=f(m_1)$.
\end{itemize}
\end{itemize}
\end{definition}
\paragraph{Immediate Application: Verifiable Delegation \cite{ParnoRV12}.} So far we've discussed settings where the server was honest-but-curious. Another concern is whether the server computes the prescribed computation at all. Here the client would like to verify that the server computes correctly, but without performing the computation on her own.
Functional encryption gives us an amortized solution for the problem. Say that you have a client that would like to evaluate a circuit $f:\zo^n\rightarrow \zo$ on many inputs, potentially $\gg |f|$. Then it can do the following:
\begin{itemize}
\item Consider the function $g:\zo^{3n}\rightarrow\zo^n$ that maps
$$(x,r_0,r_1) \longmapsto \begin{cases} r_0 & \text{if } f(x) = 0\\ r_1 & \text{if } f(x) =1\end{cases}\enspace.$$
Generate and send the server a functional key $sk_g$ --- takes time $\approx |g| \approx |f|$.\footnote{Formally some fixed polynomial in $|f|$.}
\item
When the client wishes the server to compute $f(x)$, it chooses random $r_0,r_1$, and sends the server an encryption $ct$ of $(x,r_0,r_1)$.
\item
The server cab then use the function key $sk_g$ to return $f(x),r_{f(x)}$, which the verifier can check in time $O(n) \ll |f|$.
\end{itemize}
To convince the client to accept the wrong result $1-f(x)$, the server must learn $r_{f(x)}$, however the security of FE prevents her from doing so. Indeed, assume w.l.o.g that $f(x)=0$ (other case is similar, then since $g(x,r_0,r_1)=r_0$ does not depend on $r_1$, it holds that
$$ sk_g,E_{pk}(x,r_0,r_1) \approx_c sk_g,E_{pk}(x,r_0,0^n) \enspace.$$
\paragraph{A Weak FE Scheme from Plain PKE \cite{SahaiS10}.} We will now show how to construct an FE scheme that is weak in two aspects:
\begin{itemize}
\item {\bf Encryption Scales with Functions.} The scheme will only work for circuits $f$ of a-priori bounded size $s(n)$, the time to encrypt may in particular grow with $s(n)$, and not just with the message length $n$.
\item {\bf Selective Security.} The scheme will satisfy a weaker security notion:
\begin{itemize}
\item $A$ obtains the public key.
\item She then submits submits two messages $m_0,m_1\in \zo^n$ and {\bf a single} function $f$.
\item She obtains a ciphertext $ct=E_{pk}(m_b)$ for a random $b\gets \zo$, and outputs a guess $b'$.
\item $A$ wins if $b=b'$ and $f(m_0)=f(m_1)$.
\end{itemize}
\end{itemize}
%
We now construct such a scheme $(G,KG,E,D)$ from a PKE $(G',E',D')$ and a circuit garbling scheme $(CEnc,IEnc,Eval)$. Recall that in a garbling scheme we have a circuit encoder $CEnc$ that given $f$ and a secret key $sk$ outputs an encoding $\hat f$ and a local input encoder $IEnc$ that given the secret key $sk$ and $(i,x_i) \in [n]\times \zo$ outputs an encoding $\hat x_i$ of the $i$th input bit.\footnote{We defined the locality more generally, but saw that Yao's garbled circuit has input locality one.} We also have an evaluation algorithm $Eval$ that given a circuit and input encodings $\hat f,\hat x$, decodes $f(x)$. The security guarantee says that the encodings reveal nothing but the output. That is, there is a simulator $SIM$ such that $\hat f,\hat x \approx_c SIM(f(x))$.\footnote{We actually asked that garbling only hides the input $x$ (meaning that the simulator also got $f$). A function-hiding garbling can be easily obtained from an input hiding one by considering a universal circuit (make sure you understand why). In our construction, it will be slightly more convenient in terms of notation to consider function-hiding garbling.}
\begin{itemize}
\item $G(1^n)$: for $i,b\in [s]\times\zo$, sample $(sk_{i,b},pk_{i,b})\gets G'(1^n)$. Output $pk=\set{pk_{i,b}}$ and $msk=\set{sk_{i,b}}$.
\item $KG(msk,f)$: for $f\in \zo^s$, outputs $sk_f = \set{sk_{i,f_i}}$.
\item $E_{pk}(m)$:
\begin{itemize}
\item Let $U_m$ be a universal circuit that given as input a circuit $f$, outputs $f(m)$.
\item Sample a secret key for a garbled circuit $gsk\gets \zo^n$.
\item Compute an encoding $\hat U_m \gets CEnc_{gsk}(U_m)$.
\item Compute an encoding for each possible input bit $\set{\hat x_{i,b} \gets IEnc_{gsk}(i,b)}_{i,b\in [s]\times\zo}$.
\item Compute encryptions of the input encodings under the corresponding public keys $ct_{i,b} \gets E'_{pk_{i,b}}(\hat x_{i,b})$.
\item
Output $ct = \hat U_m,\set{ct_{i,b}}_{i,b}$.
\end{itemize}
\item $D_{sk_f}(ct)$: use the keys $\set{sk_{i,f_i}}$ to decrypt corresponding inputs encodings $\hat x = \set{\hat x_{i,f_i} \gets D'_{sk_{i,f_i}}(ct_{i,f_i})}_{i\in [s]}$ output $Eval(\hat U_m,\hat x)$.
\end{itemize}
\begin{claim}
The above scheme is functional and satisfies selective security.
\end{claim}
\begin{proof}[Proof Sketch]
The functionality of the scheme follows directly from the correctness of PKE and garbling --- if everything is performed honestly then the decryptor obtains an input encoding $\hat x = IEnc_{gsk}(f)$ and
$$
Eval(\hat U_m, \hat x) = U_m(f) = f(m)\enspace.
$$
We'll now argue that the scheme is selectively secure. Consider an adversary $A$ that submits $f,m_0,m_1$ such that $f(m_0)=f(m_1)$. We'll show that $(sk_f, E_pk(m_b))$ is computationally indistinguishable from a distribution that doesn't depend on $b$.
We will do this by a hybrid argument. First note that
\begin{align*}
sk_f, E_{pk}(m_b) \equiv &\set{sk_{i,f_i}}, \set{E'_{pk_{i,b}}(\hat x_{i,b})}_{i,b}, \hat U_{m_{b}} \approx_c \\
&\set{sk_{i,f_i}},\set{E'_{pk_{i,1-f_i}}(\bot)}_{i}, \set{E'_{pk_{i,f_i}}(\hat x_{i,f_i})}_{i}, \hat U_{m_{b}} \approx_c \\
&\set{sk_{i,f_i}},\set{E'_{pk_{i,1-f_i}}(\bot)}_{i}, \set{E'_{pk_{i,f_i}}(\hat z_i)}_{i}, \hat Z \text {\hspace{.5cm} where\hspace{.5cm} } (\hat z,\hat Z)\gets SIM(U_{m_{b}}(f))\enspace.
\end{align*}
However $U_{m_b}(f)=f(m_b)=f(m_0)$, and thus the latter distribution doesn't depend on $b$.
\end{proof}
Note that the constructed encryption scheme is indeed weak:
\begin{itemize}
\item The encryption indeed grows with the size $s$ of circuits $f$ (it contains a garbled circuit that has to evaluate $f$.)
\item It is insecure if the adversary can ask for multiple keys. (In fact, even two --- if it can ask for a key for $f$ and a circuit $g$ where each bit $g_i$ in its description is $1-f_i$, then it can decrypt the entire garbled circuit and learn everything.)
\end{itemize}
\paragraph{Beyond Weak Functional Encryption.} Can we overcome the two weaknesses described above? it turns out that overcoming any one of them would give a tremendous jump in the power of functional encryption and would make it essentially ``complete'' for cryptography.
\begin{theorem}[Informal (and Inaccurate)]
Assume selectively-secure FE where either:
\begin{itemize}
\item the complexity of encryption is independent of $s=|f|$ (depends only on $n=|m|$).
\item the adversary can ask for any polynomial number of functional keys.
\end{itemize}
Then there exists indistinguishability obfuscation.
\end{theorem}
Indistinguishability obfuscation is an extremely powerful tool that turns out to suffice for basically any crypto task that we know. At this point, we do not know how to achieve it, however, under standard (or even just ``nice") assumptions. Indeed, this is also the case for full-fledged FE.\footnote{There are settings of FE that are somewhat in between and can be achieved under standard assumptions. For instance, under LWE it is known how to construct single-key FE where the complexity of encryption only scales with the output size, and not necessarily the circuit size \cite{GoldwasserKPVZ13}.} We will discuss this further next lecture.
\section{FE for Restricted Functions: The Case of IBE}
While full-fledged FE has yet to be constructed from standard assumptions, we can construct FE for interesting restrictions of this notion. A well-known special case, introduced more than 20 years before FE \cite{Shamir84}, is that of {\em identity-based encryption} (IBE). Here the idea is that instead of remembering the public-keys of all of your contacts, their public-key can be as simple as their identity, or something that determines it, such as their e-mail address.
Such a scheme allows generating identity decryption keys $sk_{id}$, which can only decrypt encryptions under identity $id$, and reveal nothing about encryptions for other identities. Indeed, it is a special case of FE for the class of functions
$$
f_{id}(id',m) = \begin{cases} m & \text{if } id'=id\\ \bot & \text{if } id'\neq id\end{cases}\enspace.
$$
The functionality and security definitions accordingly follow from those for general FE.
A property that is crucial for IBE is that the public key is {\em compact} that is $|pk| \ll 2^{|id|}$, otherwise IBE follows directly from plain PKE (think why).
\def \GG {\mathbb{G}}
\def \HH {\mathbb{H}}
\def \ZZ {\mathbb{Z}}
\paragraph{Bilinear Maps in Cryptography.} For more than a decade and a half, it was not known how to construct IBE from the commonly used hard problems in crypto. This naturally led to searching for new hard problems with additional structure. An avenue that turned out to be very successful, and in particular led to IBE, is that of Bilinear maps, which are a generalization of discrete log groups.
In the classical setting of discrete-log groups, we have a group $\GG$, say of prime order $q$ (for instance quadratic residues mod a prime $p=2q+1$). The group allows to encode elements $x\in \ZZ_q$ in the exponent as $g^x$, and conjecture that $x$ is hard to recover as long as it is chosen at random. This hard problem already exhibits some structure; specifically, we can homomorphically compute in the exponent any affine function $L(x) = ax+b$ (for known constants $a,b\in \ZZ_q$). In particular, if we think about the map $x \mapsto g^x$ as an encryption of $x$ then it already allows to learn some function of $x$, in fact for any $g^{x_1}\dots g^{x_n}$ and affine $L(x_1,\dots,x_n)$ we can test if $L(x_1,\dots,x_n) = 0$ (simply by comparing to $g$).
What about more complex functions, say quadratic functions $Q(x)$. This is generally not possible in discrete log groups and in fact under the common Diffie-Hellman assumption, which says that given $g^x,g_y$ for random $x,y$ it is hard to compute $g^{xy}$. Bilinear groups essentially extend the concept of discrete-log groups to also support quadratic functions. These are groups $\GG$ associated with another group $\HH$ (known as the target group) and a (bilinear) map
$$
(g^x,g^y) \overset{e}{\longmapsto} h^{xy}\enspace,
$$
where $g$ and $h$ are some fixed generators of $\GG$ and $\HH$.
This in, particular allows encoding elements $g^{x_1},\dots g^{x_n} \in \GG$ and quadratic $Q(x_1,\dots,x_n)$ to test whether it is zero, indeed any such $Q$ could be written as a linear function $L$ in the variables $y_{ij}=x_i x_j$ and we can use the mapping to compute each $h^{y_{ij}}=e(g^{x_i},g^{x_j})$ and then test if $L((y_{ij} :i,j\in [n]))=0$ in $\HH$. We can then consider corresponding hard problems such as the bilinear Computational Diffie-Hellman assumption (BCDH) that says that given $g^x,g^y,g^z$ for random $x,y,z$ it is hard to find $h^{xyz}$, or even that $h^{xyz}$ is pseudorandom which is the decision version of the problem (known as BDDH).
Finding candidate groups that have such a mapping and where problems like BCDH may hold is not an easy task, and there are no easy to describe examples such as in the case of discrete-log groups. Known candidates are based on Weil/Tate pairings in certain Eliptic curve groups, and describing them is outside the scope of this course.
\paragraph{Constructing IBE from Bilinear groups.} Here we'll see how to construct IBE from such groups with BDDH under a weak security definition where the adversary obtains the identity key $sk_{id}$ for polynomially many identities {\bf chosen at random} and then tries to distinguish encryptions under another random identity $id^*$.
\begin{itemize}
\item $G(1^n)$: sample $x\gets \ZZ_q$ and output $pk=g^x$ and $msk=x$.
\item $KG(msk,id)$: interpret $id\in \GG$ and output $id^x$.
\item $E_{pk}(id,m)$: sample $z$, and output $ct=(g^z,e(id^z,g^x) \cdot m)$, where we interpret $m\in \HH$.
\item $D_{sk_{id}}(ct)$: parse $sk_{id}$ as $A\in \GG$ and $ct$ as $B,C\in \GG\times \HH$ and , output $C/e(A,B)$.
\end{itemize}
To see correctness, let $id = g^y$, note that when trying to decrypt $E_{pk}(id,m)$ with a matching $sk_{id}$
$$
C/e(A,B) = e(g^{yz},g^x) \cdot m / e(g^{yx},g^z) = h^{xyz}m/h^{xyz} = m\enspace.
$$
To prove security, consider an adversary $A$ that
\begin{itemize}
\item is given random (w.l.o.g distinct) identities $id_1,\dots,id_t,id^*$ and the keys $id_1^{x},\dots,id_t^{x}$
\item it chooses $m_0,m_1\in \HH$, and obtains $g^z,e(g^xz,id^*)m_b$ for a random $b$
\item guesses $b$ with probability $1/2+\varepsilon$.
\end{itemize}
%
Then we can break BDDH with advantage $\varepsilon$. Our reduction given $g,g^x,g^y,g^z,T$ emulates $A$ as follows:
\begin{itemize}
\item
It chooses $y_1,\dots,y_t\gets \ZZ_q$ and gives the identities $g^{y_1},\dots,g^{y_t},g^y$ and the keys $g^{xy_1},\dots,g^{xy_t}$ (which it can compute using the $y_i$'s) to $A$.
\item
$A$ produces $m_0,m_1$, and the reduction gives it back $g^z,T m_b$ for a random $b\gets \zo$.
\item
The reduction returns $1$ if and only if $A$ guesses $b$ correctly.
\end{itemize}
Note that if $T = g^{xyz}$ then $A$'s emulated view is identical to her view in the real scheme, implying that she will guess $b$ with probability $1/2+\varepsilon$, whereas if $T$ is random the $A$ can guess $b$ with probability $1/2$.
\paragraph{From Random Identities to Arbitrary Ones via Random Oracles.} A common way to remove the assumption on random identities is to consider a model where all parties have access to a random oracle $R$. In this case, we can adapt the construction so that the instead of exponentiating $id$ directly we exponentiate $R(id)$. Of course that the real world does not have random oracles, and the random oracle is heuristically replaced with some specific hash functions, such as SHA256. While such instantiation won't have a reduction to any standard assumption, in reality it is still not known how to break it. Although by now we also have schemes that do not rely on random oracle, in reality the above scheme is still more common because it is simple and relatively efficient.
\bibliographystyle{alpha}
\bibliography{bib12}
\end{document}