From cb1cb2e96d53ab2cbe24e7adeb6f947bff3aac29 Mon Sep 17 00:00:00 2001
From: Dennis Brentjes <d.brentjes@gmail.com>
Date: Sun, 16 Apr 2017 10:42:58 +0200
Subject: Added some basic CMix information and the first results for EC.

---
 content/cmix.tex | 145 +++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 145 insertions(+)
 create mode 100644 content/cmix.tex

(limited to 'content/cmix.tex')

diff --git a/content/cmix.tex b/content/cmix.tex
new file mode 100644
index 0000000..0fe3797
--- /dev/null
+++ b/content/cmix.tex
@@ -0,0 +1,145 @@
+\section{The CMix network} 
+
+This section will explain how the CMix network works, it's starts by explaining what a mix network is. Then it explains what the CMix mix network does differently and why.
+ 
+\newcommand{\NODE}[1]{
+$node_{#1}$
+}
+
+\subsection{Mix networks}
+
+%TODO3: Find and quote David Chaums original paper about mix networks.
+%TODO4: Find a paper about TOR.
+
+%TODO1: find out how to credit and who. 
+CMix is a new anonymity mix network developed by *1*. Just like any other mix network it aims to provide anonymity by hiding timing information of messages.
+
+%TODO2: check if we HAVE to sign the message in the original mixnetwork.
+The first mix network was developed by David Chaum. this mix network consists of $N$ nodes. Each of these nodes have a public/private key pair. Users that want to use the mix network have to package their message as follows, it prepends the the identifier of the destination to the message and encrypts it with the public key of \NODE{N-1}. It then prepends the identifier of \NODE{N-1} and encrypts it with the public key of \NODE{N-2} He does this for all the nodes in the network working backwards and sends it to the first node.
+
+This first node can now unpack the message it receives and retreive an identifier for the next node and a encrypted message which only \NODE{N+1} can decrypt. The last node can decrypt the original message which contains its destination and sends it the end user. Up until this point this is roughly how the TOR anonymity network operates, but there is a difference. The first node in this network does not immediately send out the messages it receives. The node first collects up to $P$ messages. When this threshold is achieved it will decrypt all the messages and randomly shuffle the order they were in, otherwise known as mixing. It then sends them to the next node.
+
+This causes an arbitrary amount of delay on client connection messages. Furthermore, an outsider analyzing the input and output of the nodes cannot see which packet went where in the mixing operation. So it cannot keep track of a specific message. This is what grants anonymity in mix networks. The downside however is the amount of public key operations the client and nodes need to do to send a single message. And while this isn't really an issue in modern day desktop computers and or low volume traffic, it is an issue for mobile phones and low-power devices.
+
+\subsection{The CMix protocol}
+A CMix network is a fixed network consisting of $N$ nodes. This means there is a fixed network order and which computer represents which node is known in advance. It uses elgamal encryption as the homomorphic encryption property of elgamal is used extensively in the protocol.
+
+The CMix network operates in 3 phases. Initialization, precomputation and real-time. The Initialization phase is only to do some key setup. This is the only time clients need to do public key operations as they have to establish a shared key every node using Diffie Hellman. This is why all communcations between the nodes have to be authenticated, so one way to do this is having SSL connections between the nodes and between the clients and the nodes.
+
+During the initialization phase the first node sends his public key to the next node which multiplies his own public key with the value he received and sends it to the next. The last nodes sends it back to the first node which stores this final value and sends it on the next node which does the same. Now all nodes have the product of the all the nodes' public keys.
+
+$$ D = \prod_N d_i $$
+\vspace{-1em}
+where:
+\begin{itemize}[label=]
+\item $d_i$ is the public key of node $i$
+\item $E$ is the shared key between nodes
+\end{itemize}
+
+When a client connects, the client agrees upon a key using Diffie-hellman key-exchange with each node. These keys will be used to send messages into the network, which will be used during the realtime-phase
+
+$$ K_c = \{k_0, k_1, k_{N-1}\} $$
+\vspace{-1em}
+where:
+\begin{itemize}[label=]
+\item $k_i$ shared key between client and node $i$
+\item $K_c$ The vector of Keys stored by the client
+\end{itemize}
+
+During any part of the protocol a client may send a message into the network. When using multiplicative group elgamal, It does this by multiplying a plain-text message with the shared keys in $K_c$. Then it sends this result to the first node. When using elliptic curve however the group elements, such as messages and shared keys, and need to be added.
+
+\begin{equation}[]
+Message = M * k_0 * k_1 * ... * k_{N-1} \label{form:message}
+\end{equation}
+\vspace{-1em}
+where:
+\begin{itemize}[label=]
+\item $K_c$ The shared key between client and node $i$
+\item $M$ The plain-text message
+\end{itemize}
+
+The Precomputation phase can be started as soon $P$, the minimum number of messages to have accumulated in \NODE{0}, is known. The first node generates $P$ random values $R$ and $S$. $R$ is a vector of $P$ values as is $S$. When encrypting or multiplying these vectors the component-wise encryption or multiplication is implied. It also generates a random permutation function $\pi$ which can randomly shuffle $P$ messages. 
+
+The Precomputation can be split up into 3 phases.
+
+In the first phase the first node encrypts his $R$ with the key $E$ and sends it to the $node_{next}$. $Node_{next}$ also generates $P$ random values $R$ and $S$ and encrypts his $R$ with the key $E$. $Node_{next}$ multiplies it's encryption result with the values received by the first node, and by the homomorphic encryption property of elgamal the result of this multiplication is the encryption of the of the multiplication of the two original $R$ vectors. It then sends the result of the multiplication to the next node which also encrypts his $R$ and multiplies and sends in on.
+
+$$ \mathcal{E}_E(R_0 * R_1) = \mathcal{E}_S(R_0) * \mathcal{E}_S(R_1)  $$
+\vspace{-1em}
+where:
+\begin{itemize}[label=]
+\item $\mathcal{E}_E$ is elgamal encryption under key $E$
+\item $R_i$ is the R vector of node $i$
+\end{itemize}
+
+Whenever the result reaches the first node again it uses its permutation function $\pi$ on the incoming vector of values and multiplies that result with the encryption of $S$. It sends its result to the next node which does the same. The last node gets the following result.
+
+\begin{align}
+&\mathcal{E}_E( \nonumber \\
+&\hspace{1em}\pi_{N-1}( ... \nonumber  \\ 
+&\hspace{2em}\pi_{1}( \nonumber  \\
+&\hspace{3em}\pi_{0}(R_{0} * ... * R_{N-1}) * S_0 \nonumber  \\
+&\hspace{2em}) * S_1 \nonumber \\
+&\hspace{1em} ... ) * S_{N-1} \label{form:EPiRS} \nonumber  \\
+&) 
+\end{align}
+\vspace{-1em}
+where:
+\begin{itemize}[label=]
+\item $\mathcal{E}_E$ is elgamal encryption under key $E$
+\item $R_i$ is the R vector of node $i$
+\item $S_i$ is the S vector of node $i$
+\item $\pi_i$ is the permutation function of node $i$
+\end{itemize}
+
+The third part of the precomputation is decrypting this value, and every node has a part of the decryption it can do. So each node calculates its decryption share and multiplies this with the value it receives. Which is elgamal decryption, but as the key is spread over all the nodes the result is still encrypted with keys of the other nodes. The result is passed over to the next node in the network. The last node in the network stores the value for use in the real-time phase. This value is the decrypted value of formula \eqref{form:EPiRS}
+
+Whenever the first node received $P$ messages as described in formula \eqref{form:message}, and the precomputation has ended, the realtime-phase can begin. The realtime-phase can also be split into 3 different stages.
+
+In the first stage each node multiplies the message with the inverse of the key it agreed upon in the initialization phase. it then multiplies with that result with $r_i$, where i is the position of the message in the buffer, replacing $K_c$ with one of the values in $R$. The result is not yet permuted so the messages stay in the same place. The result gets passed to the next node which does the same steps. So for all the messages in the input we do.
+
+\[
+M_{out} = M_{in} * K_{ci}^{-1} * R_j
+\]
+\vspace{-1em}
+where:
+\begin{itemize}[label=]
+\item $M_{in}$ is one of the input messages $E$
+\item $R_j$ the corresponding r of $M_{in}s$ position
+\item $K_{ci}$ Is the shared key of $M_{in}s$ position
+\end{itemize}
+
+The second phase is similar to the second phase of the precomputation, A node takes the message buffer, swaps around the messages according to its permutation function $\pi$ it then multiplies it by $S$, each node does this step.
+
+\begin{align}
+&Messages\_out = \pi_{N-1}( \ldots \nonumber  \\ 
+&\hspace{1em}\pi_{1}( \nonumber  \\
+&\hspace{2em}\pi_{0}(R_{0} * \ldots * R_{N-1} * M) * S_0 \nonumber  \\
+&\hspace{1em}) * S_1 \nonumber \\
+& \ldots ) * S_{N-1} \label{form:PiMRS} \nonumber  \\
+\end{align}
+\vspace{-1em}
+where:
+\begin{itemize}[label=]
+\item $\pi_i$ is the permutation function of node $i$
+\item $R_i$ is the R vector of node $i$
+\item $S_i$ is the S vector of node $i$
+\end{itemize}
+
+The last phase is to remove the R and S vectors from the input. The last node stored decryption of formula \ref{form:EPiRS}. The last node calculates the inverse of this group element and multiplies it with the result of \ref{form:PiMRS}. This will cancel out all permuted R and S values, and the last node wil be left with $M$.
+
+Very critical to see is that during the realtime phase no public-key crypto is being done, only some multiplications. And the clients, outside of the initialization phase, never have to do any public-key crypto. It is also possible for client and servers to update the shared key using the old key as a seed. So in theory a client only needs to do the key agreement once per network.
+
+\subsection{Advantages of CMix}
+
+The fact that CMix minimizes the amount of public-key cryptographic operations for the client, makes it more appealing for low power devices. So devices that cannot draw high amounts of power all the time due to battery constrains or NFC power limits. Also mobile phones of which you want to conserve battery power.
+
+Another advantage is that in theory the latency of the actual messages during the real-time phase should be lower than other mix networks. Again due to the lack of public-key cryptography during this phase.
+
+\section{}
+
+
+
+
+
+
-- 
cgit v1.2.3-70-g09d2

