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}.
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.
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
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:
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:
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.
\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:
\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.