Homec4science
Diffusion Genome Privacy - SHCS App (mobile_app) Browse

genopri-shcs/documentation/research/elgamal_homomorphic.tex
900c8a86c920mobile_app

Last Change
Raw File

elgamal_homomorphic.tex
View Options

\documentclass[]{article} % A4 paper and 11pt font size
%define margins
\usepackage[top=1.5cm, bottom=1.5cm, left=2cm, right=2cm]{geometry}
\usepackage[english]{babel} % English language/hyphenation
\usepackage{natbib}
% use math packages
\usepackage{amsmath,amsfonts,amsthm} % Math packages
\usepackage{algorithm}
\usepackage{algorithmic}
% modify section commands
\usepackage{sectsty}
\allsectionsfont{ \normalfont\scshape}
\setlength\parindent{0pt} % Removes all indentation from paragraphs - comment this line for an assignment with lots of text
%----------------------------------------------------------------------------------------
% Title page
%----------------------------------------------------------------------------------------
\newcommand{\horrule}[1]{\rule{\linewidth}{#1}} % Create horizontal rule command with 1 argument of height
\title{
\normalfont \normalsize
\textsc{Ecole Polytechnique Federale de Lausanne (EPFL)}\\
\textsc{School of Computer and Communication Sciences, IC}\\ [10pt]
\horrule{0.5pt} \\
\huge Elliptic Curve ElGamal Encryption \\
\horrule{2pt} \\
}
\author{Franck Youssef}
\date{\normalsize\today}
\begin{document}
\maketitle
\section{Traditional Ellitpic Curve ElGamal Cryptosystem (ECCEG)}
%----------------------------------------------------------------------------------------
% Setup
%----------------------------------------------------------------------------------------
\subsection{Setup \citep{DBLP:journals/corr/abs-0903-3900}}
Let $E$ be an elliptic curve over finite filed $\mathbb{GF}(p)$, the order of the curve $E$ be $n = \#E$, $G$ the generator point of curve $E$.
Also, let $x \in \mathbb{GF}(p)$ be the secret key and $Y = xG$ be the public key.
Define the mapping function
\begin{align*}
map \colon \mathbb{GF}(p) & \longrightarrow E \\
m & \longmapsto mG
\end{align*}
such that $$map(m_1 + m_2 + ...) = map(m_1) + map(m_2) + ...$$
Similarly, define the reverse mapping function $rmap()$ that extract $m$ from a given point $mG$.
Problem: How do we reverse this mapping? Must solve the Elliptic Curve Discrete Logarithm Problem. Need lookup tables or do we have more efficient mapping functions? Some approaches described in \citep{Tang_ecdkg:a}.
%----------------------------------------------------------------------------------------
% Encryption
%----------------------------------------------------------------------------------------
\subsection{Encryption}
Algorithm ~\ref{alg-eceg-enc} describes the encryption process using Elliptic Curve ElGamal scheme.
\begin{algorithm}
\caption{EC-ElGamal encryption}
\label{alg-eceg-enc}
\begin{algorithmic}
\REQUIRE public key $Y$, plaintext $m$
\ENSURE ciphertext $(R,S)$
\STATE choose random $k\in [1,n-1]$
\STATE $M := map(m)$
\STATE $R := kG$
\STATE $S := M + kY$
\RETURN $(R,S)$
\end{algorithmic}
\end{algorithm}
%----------------------------------------------------------------------------------------
% Decryption
%----------------------------------------------------------------------------------------
\subsection{Decryption}
Algorithm ~\ref{alg-eceg-dec} describes the decryption process using Elliptic Curve ElGamal scheme.
\begin{algorithm}
\caption{EC-ElGamal decryption}
\label{alg-eceg-dec}
\begin{algorithmic}
\REQUIRE secret key $x$, ciphertext $(R,S)$
\ENSURE plaintext $m$
\STATE $M := -xR + S$
\STATE $m := rmap(M)$
\RETURN $m$
\end{algorithmic}
\end{algorithm}
%----------------------------------------------------------------------------------------
\subsubsection{Proof}
Let represent the encryption of a message $m$ with the public key $Y$ as $$\mathcal{E}_Y[m] = (R,S) = (kG, M + kY)$$ where $M$ is the mapped message from $\mathbb{GF}(p)$ onto the elliptic curve $E$ and $k \in [1, n-1]$ randomly chosen.
We verify that the decryption decrypts properly
\begin{align*}
\mathcal{D}_x\left[ (R,S) \right] & = rmap \left( -xR + S \right) \\
& = rmap \left( -xkG + M + kY \right) \\
& = rmap \left( -xkG + M + kxG \right) \\
& = rmap (M) \\
& = m
\end{align*}
%----------------------------------------------------------------------------------------
\subsubsection{Additively homomorphic scheme}
Let denote the encryption of message $m$ with public key $Y$ as $\mathcal{E}_Y[m]$. We verify that ElGamal encryption over an Elliptic Curve is additively homomorphic. We want to show that
$$\mathcal{D}_x \left[ \mathcal{E}_Y[m_1] + \mathcal{E}_Y[m_2] \right] = \mathcal{D}_x \left[ \mathcal{E}_Y [m_1 + m_2] \right]$$
First, we have that
\begin{align*}
\mathcal{E}_Y[m_1] + \mathcal{E}_Y[m_2] &= \left( k_1 G, map(m_1) + k_1 Y \right) + \left( k_2 G, map(m_2) + k_2 Y \right)\\
&= \left( (k_1 + k_2) G, map(m_1) + map(m_2) + (k_1+k_2) Y \right)
\end{align*}
Now, as we assume $map$ to be linear, we have
\begin{align*}
\mathcal{D}_x \left[ \mathcal{E}_Y[m_1] + \mathcal{E}_Y[m_2] \right] &= \mathcal{D}_x \left[ \left( (k_1 + k_2) G, map(m_1+m_2) + (k_1+k_2) Y \right) \right]\\
&= rmap \left( map(m_1+m_2) + (k_1+k_2) Y - x(k_1 + k_2) G \right)\\
&= rmap \left( map(m_1+m_2) \right)\\
&= m_1+m_2
\end{align*}
On the other side, we have by definition of $\mathcal{E}(\cdot)$ and $\mathcal{D}(\cdot)$
\begin{align*}
\mathcal{D}_x \left[ \mathcal{E}_Y [m_1 + m_2] \right] &= m_1 + m_2
\end{align*}
\hfill$\square$
\subsubsection{Scalar multiplication}
Denote a scalar $c \in \mathbb{N}^*$ (we may need to restrict this to some $\mathbb{Z}_q$ ?). We want to show that
$$\mathcal{D}_x \left[ \mathcal{E}_Y[c \cdot m] \right] = \mathcal{D}_x \left[c \cdot \mathcal{E}_Y[m] \right].$$
We compute the result for the left hand side:
\begin{align*}
\mathcal{E}_Y[c \cdot m] &= \left( k_1 G, map(c \cdot m) + k_1 Y \right) \\
\Rightarrow \mathcal{D}_x \left[ \mathcal{E}_Y[c \cdot m] \right] &= rmap\left( map(c \cdot m) + k_1 Y - x k_1 G \right) \\
&= rmap\left( map(c \cdot m) \right) \\
&= c \cdot m
\end{align*}
We then compute the resulting value for the right hand side
\begin{align*}
c \cdot \mathcal{E}_Y[m] &= c\cdot \left( k_2 G, map(m) + k_2 Y \right)\\
&= \left( c k_2 G, c \cdot map(m) + c k_2 Y \right)\\
\Rightarrow \mathcal{D}_x \left[c \cdot \mathcal{E}_Y[m] \right] &= rmap \left( c \cdot map(m) + c k_2 Y - c k_2 x G \right)\\
&= rmap \left( c \cdot map(m) \right)
\end{align*}
Now, we need our mapping function $map$ to be linear. Hence
\begin{align*}
\mathcal{D}_x \left[c \cdot \mathcal{E}_Y[m] \right] &= rmap \left( c \cdot map(m) \right)\\
&= rmap\left( map(c \cdot m) \right)\\
&= c \cdot m
\end{align*}
\hfill$\square$
%----------------------------------------------------------------------------------------
\section{Elliptic Curve ElGamal Threshold Cryptosystem (ECCEG-TC) \citep{Ruan2012}}
\subsection{Introduction}
Before defining the cryptosystem, we need to define the Lagrange interpolation.
We use Lagrange interpolation to split the secret key into multiple parts that we distribute among the parties.
\subsection{Lagrange Interpolation}
Consider a set of $k-1$ points $\{(x_1, y_1), (x_2, y_2), ..., (x_k, y_k)\}$ that define a polynomial $f(x)$ of degree $k-1$, with district $x_i$ and $y_i = f(x_i)$. Then, consider the Lagrange coefficients:
$$\lambda_j (x) [x_1, x_2, ..., x_k] = \prod_{i = 1, i \neq j}^{k} \frac{x - x_i}{x_j - x_i}.$$
We know that
\begin{align*}
f(x) & = \sum_{j=1}^{k} y_j \lambda_j (x) [x_1, x_2, ..., x_k] \\
& = \sum_{j = 1}^{k} y_j \prod_{i = 1, i \neq j}^{k} y_j \lambda_j (x) [x_1, x_2, ..., x_k]
\end{align*}
In consequence to that, we have
\begin{align*}
f(0) & = \sum_{j=1}^{k} y_j \lambda_j (0) [x_1, x_2, ..., x_k] \\
& = \sum_{j=1}^{k} y_j \prod_{i=1, i \neq j}^{k} \frac{-x_i}{x_j - x_i}
\end{align*}
\subsection{Shamir Secret Sharing}
We apply the Lagrange interpolation to sharing the our secret among two parties such that we need two fragments from our two parties to be able to decrypt the message. We see that this is a degenerated form of Shamir Secret sharing, when we need two from two encrypted fragments.
We compute the Lagrange coefficients around $0$ for two parties:
\begin{align*}
b_1 &= \lambda_1 (0) = \prod_{i = 1, i \neq 1}^{2} \frac{0 - x_i}{x_j - x_i} = \prod_{i = 1, i \neq 1}^{2} \frac{-i}{1 - i} = 2 \mod q \\
b_2 &= \lambda_2 (0) = \prod_{i = 1, i \neq 2}^{2} \frac{0 - x_i}{x_j - x_i} = \prod_{i = 1, i \neq 2}^{2} \frac{-i}{2 - i} = -1 \mod q
\end{align*}
Hence to recover our secret
$$a_0 = f(0) = y_1 b_1 + y_2 b_2 = 2 y_1 - y_2$$
%%%%%%%%%%%
\subsection{Key Generation}
Assume from now that there are only two parties share the parts of the secret key. The public key $PK$ is generated and distributed to all parties. The party distributing the keys generates partial keys $SK_i$ and distributed one to each party having to decrypt together a message. Algorithm ~\ref{alg-ecceg-tc-key} describes the key generation.
\begin{algorithm}
\caption{ECCEG-TC key generation}
\label{alg-ecceg-tc-key}
\begin{algorithmic}
\REQUIRE secret key $a$, generator $g$ on $E_p$
\ENSURE public key $PK = (E, g, y)$, secret keys $SK_i, \; \forall i = 1,2$
\STATE $y := ag$
\STATE select randomly $a_1 \in \mathbb{Z}_q$
\STATE $a_0 := a$
\STATE $SK_i := f(i) \mod q = a_0 + a_1 i \mod q, \; i=1,2$
\end{algorithmic}
\end{algorithm}
\subsection{Encryption}
The encryption works as traditional ECCEG. Algorithm ~\ref{alg-ecceg-tc-enc} describes the encryption of a message.
\begin{algorithm}
\caption{ECCEG-TC encryption}
\label{alg-ecceg-tc-enc}
\begin{algorithmic}
\REQUIRE public key $y$, plaintext $m$
\ENSURE ciphertext $(R,S)$
\STATE choose random $k\in \mathbb{Z}_q$
\STATE $M := map(m)$
\STATE $R := kg$
\STATE $S := M + ky$
\RETURN $(R,S)$
\end{algorithmic}
\end{algorithm}
\subsection{Decryption}
The partial decryption is slightly different than the traditional ECCEG decryption. Every party having a partial decrypts partially the message with its partial private key $SK_i$ and sends its fragment to one central host who will be able to regroup the fragments and get the clear text. Algorithm ~\ref{alg-ecceg-tc-pdec} describes the partial decryption of a message by a party and algorithm ~\ref{alg-ecceg-tc-fdec} describes the decryption of a message based on all the decryption fragments collected from all parties.
\begin{algorithm}
\caption{ECCEG-TC partial decryption}
\label{alg-ecceg-tc-pdec}
\begin{algorithmic}
\REQUIRE partial secret key $SK_i$, ciphertext $(R,S)$
\ENSURE decryption fragment $(i, R, S, T_i)$
\STATE $T_i := R \cdot SK_i$
\RETURN $(i, R, S, T_i)$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}
\caption{ECCEG-TC full decryption}
\label{alg-ecceg-tc-fdec}
\begin{algorithmic}
\REQUIRE decryption fragments $(i, R, S, T_i), \; \forall i=1,2$
\ENSURE plaintext $m$
\STATE $\forall i=1,2:\quad b_i = \prod_{j=1, j\neq i}^{2} \frac{-x_j}{x_i - x_j} \mod q$
\STATE $F := \sum_{j=1}^{2} b_j T_j = ky$
\STATE $M := S - v = M + ky - F$
\STATE $m := rmap(M)$
\RETURN $m$
\end{algorithmic}
\end{algorithm}
%----------------------------------------------------------------------------------------
% Design Decisions
%----------------------------------------------------------------------------------------
\section{Design Decisions}
\subsection{Mapping function from message space onto Elliptic Curve}
Not possible to find full mapping of message space onto Elliptic Curve \citep[chap. 4]{fouque2013injective}.
Basic probabilistic mappings described in \citep{Koblitz1987}. Difficulties and efforts to find mappings with basic probabilistic embeddings in \citep[chap. 2.4]{fouque2013injective}. More complex probabilistic mappings are described here \citep{king2009mapping}.
Usually not needed as we perform either ECIES or ``hashed'' ElGamal which does not require mapping onto the elliptic curve.
\subsection{Finite field level}
Possibility to either do over the prime field $\mathbb{GF}(p)$ or the binary field $\mathbb{GF}\left( 2^m \right)$.
Seems to be computationally more expensive over binary field, but inversion faster over binary than prime field. In the end, the binary field seems more advantageous.
\subsection{Elliptic curve group level \citep{MA_Ugus,Ugus_performanceof}}
Decide on which coordinate system should it be stored on:
\begin{itemize}
\item Affine
\item Projective
\item Jacobian
\item Chudnovsky-Jacobian
\item Modified Jacobian
\item Mixed coordinate system
\end{itemize}
%----------------------------------------------------------------------------------------
% Targets and Pipeline
%----------------------------------------------------------------------------------------
\section{Targets}
\begin{itemize}
\item Find group of mapping function from message space onto Elliptic Curve $E_p$.
\item Write unit tests
\item Compare performance of these groups
\item Need to analyze the operations needed for the homomorphic operations, e.g. analyze where is multiplicative inversion needed and where point addition needed.
\item Analyze requirements in terms of storage
\end{itemize}
%----------------------------------------------------------------------------------------
% Targets and Pipeline
%----------------------------------------------------------------------------------------
\bibliography{research}{}
\bibliographystyle{plain}
%----------------------------------------------------------------------------------------
\end{document}
c4science · Help