In the first section of this chapter, we want to build an Elliptic Curve Cryptosystem based on ElGamal. We follow the procedure described in \citep{DBLP:journals/corr/abs-0903-3900} to build an additive homomorphic scheme.
In the second section, we extend this cryptosystem with Shamir Secret Sharing in order to split the secret between two parties, e.g. MU and SPU.
In the third section, we discuss various design decisions.
Let $E$ be an elliptic curve over finite filed $\mathbb{GF}(p)$, the order of the curve $E$ be $n = \#E$ the cardinality of $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.\par
In order to define an additively homomorphic scheme \citep{DBLP:journals/corr/abs-0903-3900}, we define the function
\begin{align*}
map \colon \mathbb{GF}(p) & \longrightarrow E \\
m & \longmapsto mG
\end{align*}
such that the $map(\cdot)$ function is additively homomorphic, i.e.
$$map(m_1 + m_2) = map(m_1) + map(m_2).$$
Similarly, we define the reverse mapping function $rmap(\cdot)$ that extract $m$ from a given point $mG$, i.e. $$rmap(map(m)) = m.$$
By definition, this mapping is additively homomorphic. However it has the inconvenient to be hard to revert. Extracting $m$ from $mG$ is known as the Elliptic Curve Discrete Logarithm Problem and is known to be hard to solve \citep{Koblitz1987}. As this $map(\cdot)$ is a trapdoor function, we compute and store beforehand a lookup table to reverse the mapping. This is further discussed in \refsec{ecceg-mapping-decision}.
The decryption procedure for ECCEG scheme is described in Algorithm~\ref{alg-ecceg-dec}. The proof of the decryption can be found in \refappendix{proof-ecceg-dec}.
ElGamal on Elliptic Curve with our mapping function has by design the interesting property to be additively homomorphic and homomorphic for multiplication by a scalar. Proofs for both homomorphic properties can be found in \refappendix{proof-homo-add} and \refappendix{proof-homo-scale}.
In order to share the security of the genomic material between the MU and the SPU, we introduce the notion of Threshold Cryptosystem on top of EC-ElGamal cryptosystem. With a $(t,n)$-Threshold Cryptosystem, a ciphertext can only be decrypted if at least $t$ parties among $n$ participating collaborate to decrypt the ciphertext. If less than $t$ parties collaborate to decrypt the ciphertext, they obtain no useful information on the plaintext.\par
Here we use a degenerated version of a $(t,n)$-Threshold Cryptosystem where $2$ parties among $2$ collaborate to decrypt the ciphertext, i.e. $(t,n) = (2,2)$.
In order to build a Threshold Cryptosystem on top of ECCEG, we follow \citep{Ruan2012} which applies Shamir Secret Sharing with Lagrange Interpolation to Elliptic Curve ElGamal. Precisions on Lagrange Interpolation and Shamir Secret Sharing can be found in \refappendix{ecceg-tc-basis}.
Assume from now that only the SPU and MU share parts of the secret key. The public key $PK$ is generated and distributed to all parties. The Key Manager distributing the key shares generates partial keys $SK_1$, $SK_2$ and distributes one to every party participating. The ECCEG-TC Key Generation procedure is described in \refalgo{alg-ecceg-tc-key}.
\begin{algorithm}[H]
\caption{ECCEG-TC Key Generation}
\label{alg-ecceg-tc-key}
\begin{algorithmic}
\REQUIRE secret key $x$, generator $G$ on elliptic curve $E$
\ENSURE public key $PK = (E, G, Y)$, secret keys $SK_i, \; \forall i = 1,2$
\STATE $Y := xG$
\STATE select randomly $a_1 \in \mathbb{Z}_q$
\STATE $a_0 := x$
\STATE $SK_i := f(i) \mod q = a_0 + a_1 i \mod q, \; i=1,2$
\end{algorithmic}
\end{algorithm}
\subsection{ECCEG-TC Encryption}
The encryption for ECCEG-TC is the same as with ECCEG based on the same public key. \refalgo{alg-ecceg-tc-enc} describes the encryption procedure of a message.
\begin{algorithm}[H]
\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{ECCEG-TC Decryption}
The partial decryption is slightly different than the traditional ECCEG decryption procedure. Every party decrypts the ciphertext using its secret key share $SK_i$ following the procedure described in \refalgo{alg-ecceg-tc-pdec} and outputs a fragment $(i, R, S, T_i)$. Then a party collects all the 2 fragments. It assembles both of the fragments using the procedure described in \refalgo{alg-ecceg-tc-fdec} and obtains the cleartext message. Details on how to compute the $b_i$ factor in \refalgo{alg-ecceg-tc-fdec} can be found in \refappendix{shamir-secret}.
\subsection{Bijection between Message Space and Elliptic Curve} \label{ecceg-mapping-decision}
As the mapping described in \refsec{ecceg-setup} is hard to reverse, an effort was made to investigate other homomorphic mappings or solutions.
The common use of ElGamal on Elliptic Curve does not require a deterministic mapping between message space and elliptic curve. Common encryption schemes such as Elliptic Curve Integrated Encryption Scheme (ECIES) or Hashed ElGamal \citep{chevallier2006encoding} do not process messages on elliptic curve space. As such schemes loose the homomorphic property we need, we investigate deterministic homomorphic mappings from message space onto elliptic curve.\par
There exist probabilistic mappings \citep{Koblitz1987} \cite[chap. 2.4]{fouque2013injective} of message space onto elliptic curve, but none of them map the whole message space onto the Elliptic Curve. Some more complex probabilistic mappings \citep{king2009mapping} appear to map a larger range of the message space. Finally according to \cite[chap. 4]{fouque2013injective}, it is not possible to find a complete mapping between message space and Elliptic Curve.\par
As no mapping found are deterministic and map the whole message space onto the curve, we decided to use the mapping described in \refsec{ecceg-setup} and create a lookup table storing the ciphertext and plaintext for the whole message space. It is clear that this approach is conceivable only for small message spaces. Mapping the whole message space is something expensive to perform as well as looking up an entry in a table or tree of the cardinality of the whole message space. According to \citep{EPFL-CONF-188284}, the message space of our application should not exceed $N=10000$. Hence it is reasonable to generate, store and query a lookup table for the whole message space.