Homec4science
Diffusion Genome Privacy - SHCS App (SHCS_url) Browse

genopri-shcs/report/sections/appendix/appendix_additional_math_material.tex
94cc1794ed58SHCS_url

Last Change
Raw File

appendix_additional_math_material.tex
View Options

\chapter{Additional Mathematical Material}
%----------------------------------------------------------------------------------------
% EC-ElGamal
%----------------------------------------------------------------------------------------
\section{EC-ElGamal Proofs}
%----------------------------------------------------------------------------------------
\subsection{Decryption} \label{proof-ecceg-dec}
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*}
%----------------------------------------------------------------------------------------
\subsection{Additively Homomorphic Scheme} \label{proof-homo-add}
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$
%----------------------------------------------------------------------------------------
\subsection{Scalar Multiplication Homomorphic} \label{proof-homo-scale}
Denote a scalar $c \in \mathbb{N}^*$. 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$
%----------------------------------------------------------------------------------------
% Basis for Threshold Cryptography for EC-ElGamal
%----------------------------------------------------------------------------------------
\section{Basis for Threshold Cryptography for EC-ElGamal} \label{ecceg-tc-basis}
\subsection{Lagrange Interpolation}
In this section, we describe the mathematical tools we need for Shamir Secret Sharing.\par
Consider a set of $k$ 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} \label{shamir-secret}
Shamir's Secret Sharing is an algorithm to share a secret. It gives every participant a unique share. In order to retrieve the secret, all shares need to be reassembled.
We apply Shamir's algorithm for $k=2$ parties (SPU and MU) sharing a secret $s$.
Let $r$ be a random number. Let $f(x) = a_0 + a_1 * x$. For every party $i=1,2$, we compute $y_i = f(i)$. Then, we compute the Lagrange coefficients around $0$ for the two parties $i=1,2$:
\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$$
c4science · Help