-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathhomomorphic-encryption.tex
111 lines (79 loc) · 8.8 KB
/
homomorphic-encryption.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
\section{Homomorphic Encryption}\label{s:homomorphic-encryption}
Some encryption schemes are inherently ``malleable", which means that it is possible to transform a ciphertext into another ciphertext which decrypts to a related plaintext.
Homomorphic encryption is a malleable encryption scheme that allows operations directly on encrypted data so that the results after decryption would correspond to applying matching operations on unencrypted data.
For example, having an encryption mechanism $Enc$, the product of any two ciphertexts is equal to a ciphertext of the sum of the two corresponding plaintexts ($M_1$ and $M_2$). Or more generally the application of a function to the ciphertexts corresponds to another function on the plaintexts, as follows:
\begin{equation}\label{eq:homomorphic}
Enc(M_1) \otimes Enc(M_2) = Enc(M_1 \oplus M_2)
\end{equation}
for some operations $\otimes$ and $\oplus$.
Homomorphic encryption enables outsourcing computations to a third party, as for example on the cloud.
Cloud computing is designed to deal with difficult operations and with computationally demanding algorithms.
However, if user's data are unencrypted they can be exposed to attacks from both the cloud provider and third parties (hackers, government agencies, data breaches, etc.).
Even if the data are stored \textit{(data at rest)} and transferred \textit{(data in transit)} securely, when they are in use they can be exposed to security risks, such as side-channel attacks \cite{zhang2012cross} and hardware Trojans \cite{becker2013stealthy, tsoutsos2014advanced}.
\textit{Data at rest} implies data that is stored physically in any digital form, while \textit{data in transit} means data traversing the network.
Active data under constant change which is stored in a non-persistent digital state typically in computer random access memory (RAM), CPU caches, or CPU registers are called \textit{data in use}.
It is possible, to construct an entire system to work over encrypted data, manipulating and returning encrypted results.
This system would be based on homomorphic encryption, which allows to apply a function to the ciphertexts that corresponds to another function on the plaintexts, and in general enables computation on encrypted data.
The final results can then be obtained by a single decryption.
For instance, given $Enc(M_1)$ and $Enc(M_2)$ (the encryption of $M_1$ and $M_2$), you can compute $Enc(M_1 + M_2)$ without knowing $M_1$, $M_2$ nor the decryption key.
The only point in the process where data would be decrypted is when the user wants to see the result, and that would presumably happen in the application or client software, not in the database server in the cloud, rendering the host incapable of leaking any type of information.
One challenge that homomorphic encryption schemes, and in general every encrypted computation framework, face is the inability to make runtime decisions based on encrypted data.
Using homomorphic operations requires special care to ensure that branching does not reveal any sensitive data by observing side-channel information (\textit{e.g.} the branch target).
For instance, the host is unable to perform operations like ``\texttt{if (x > 0) return;}" when \texttt{x} is an encrypted variable.
This is known as the ``termination problem", introduced in \cite{brenner2011secret}, since performing runtime branch decisions is not possible and therefore rendering the algorithms implemented on top of those systems by design more complex.
To address this problem traditional algorithms must be changed to their homomorphic equivalents, a not straightforward process.
Some work has been done in \cite{mouris2018terminator} by developing benchmarks targeted for computer architectures based on homomorphic operations.
Those benchmarks avoid termination problems while maintaining data privacy.
There is not a sole type of homomorphic encryption, different schemes have been proposed for different types of applications.
\subsection{Partially Homomorphic Encryption}\label{ss:phe}
The most widely used type of homomorphic encryption is partially homomorphic encryption (PHE), with schemes like RSA, ElGamal, Benaloh and Paillier.
PHE has been expanded with applications such as Helios (e-voting PHE based system) \cite{adida2008helios}, Cryptoleq (Heterogeneous abstract machine for both encrypted and unencrypted computation based on PHE) \cite{mazonka2016cryptoleq}, and others.
All those systems, perform manipulations directly on encrypted data without decrypting them, thus no information leakage is possible.
When the result is eventually decrypted, it will be the same as applying the same manipulations on plaintexts.
The two most common cases (but not the only ones) of partially homomorphic cryptosystems are \textit{additively homomorphic} and \textit{multiplicatively homomorphic}.
\begin{itemize}
\item Additively homomorphic systems enable computation over ciphertexts (encrypted data) that result in the encryption of the sum (addition) of two plaintexts. More formally, a cryptosystem is considered to be additively homomorphic iff:
\begin{equation}\label{eq:additively-homomorphic}
Enc(M_1) \otimes Enc(M_2) = Enc(M_1 + M_2)
\end{equation}
for some operation $ \otimes $.
\item Multiplicatively homomorphic systems enable computation over ciphertexts that decrypt to the product (multiplication) of two plaintexts. More formally, a cryptosystem is considered to be multiplicatively homomorphic iff:
\begin{equation}\label{eq:multiplicatively-homomorphic}
Enc(M_1) \otimes Enc(M_2) = Enc(M_1 \cdot M_2)
\end{equation}
for some operation $ \otimes $.
\end{itemize}
Below we describe some widely known cryptosystems that are partially homomorphic.
\subsubsection{RSA Cryptosystem}\label{ss:rsa}
Plain RSA encryption is multiplicatively homomorphic. Consider the encryption algorithm described in section \ref{s:pk-rsa}. We know that $Enc(m) = {m_1}^{e}\pmod{n}$. Given two ciphertexts $Enc(m_1)$ and $Enc(m_2)$ of plaintexts $m_1$ and $m_2$ respectively, we can see that the following holds.
\begin{equation}
\label{eq:homomorphic-rsa}
\begin{gathered}
Enc(m_1) \cdot Enc(m_2) = {m_1}^{e}\pmod{n} \cdot {m_2}^{e}\pmod{n} =\\ ({m_1}\cdot{m_2})^{e}\pmod{n} = Enc({m_1}\cdot{m_2})
\end{gathered}
\end{equation}
So the product of the two ciphertexts corresponds to the ciphertext of the product of the two plaintexts.
\subsubsection{ElGamal Cryptosystem}\label{ss:elgamal}
The ElGamal cryptosystem is also multiplicative homomorphic. Based on the algorithm described in \ref{s:pk-elgamal} we know that $Enc(m) = (G,M) = (g^{r} \pmod{p}, m$, for some random $r \in_{R} \mathbb{Z}_{q}$. Consider we have two ciphertexts $Enc(m_1)$ and $Enc(m_2)$ of plaintexts $m_1$ and $m_2$, respectively. We can see that the following holds.
\begin{equation}
\label{eq:homomorphic-elgamal}
\begin{gathered}
Enc(m_1) \cdot Enc(m_2) = (G1, M1) \cdot (G2, M2) =\\ (g^{r_1} \pmod{p}, m_1 \cdot y^{r_1} \pmod{p}) \cdot (g^{r_2} \pmod{p}, m_2 \cdot y^{r_2} \pmod{p}) =\\ (g^{r_1+r_2} \pmod{p}, (m_1 \cdot m_2) \cdot y^{r_1+r_2} \pmod{p}) = Enc({m_1} \cdot {m_2})
\end{gathered}
\end{equation}
We can see again that the product of the encryptions of two plaintexts results to the encryption of the encryption of the product of the two plaintexts.
\subsubsection{Paillier Cryptosystem}\label{ss:paillier}
The Paillier cryptosystem is additively homomorphic. According to \ref{s:pk-paillier}, we know that $Enc(m) = g^{m} \cdot r^n \pmod{n^2}$, for some random $ r \in_{R} \mathbb{Z}_{n}^{*}$ . Given two ciphertexts $Enc(m_1)$ and $Enc(m_2)$ of plaintexts $m_1$ and $m_2$ respectively, we can see that the following holds.
\begin{equation}
\label{eq:homomorphic-paillier}
\begin{gathered}
Enc(m_1) \cdot Enc(m_2) = (g^{m_1} \cdot {r_1}^n \pmod{n^2}) \cdot (g^{m_2} \cdot {r_2}^n \pmod{n^2}) =\\ (g^{m_1} \cdot {r_1}^n) \cdot (g^{m_2} \cdot {r_2}^n)\pmod{n^2} = g^{m_1 + m_2} \cdot (r_1 \cdot r_2) \pmod{n^2} =\\ Enc({m_1} + {m_2})
\end{gathered}
\end{equation}
We can see that the product of the two ciphertexts will decrypt to the sum of their corresponding plaintexts.
\subsection{Fully Homomorphic Encryption}\label{ss:fhe}
Another form of homomorphic encryption is Fully homomorphic encryption (FHE), first invented by Gentry in \cite{gentry2009fully}.
Due to the fact that FHE enables \textit{arbitrary computation} on ciphertexts, is far more powerful than PHE (which was just called Homomorphic Encryption before FHE systems were discovered) and its appearance sparked the academic interest.
Consecutively a lot of FHE schemes arise, but unfortunately they come along with a huge performance overhead.
This overhead has been a concern and this is the reason that there are not many applications that leverage FHE, despite the wide range of that can benefit from FHE schemes.
Some implementations are the HElib \cite{halevi2014algorithms} and the TFHE \cite{chillotti2016faster}.