Real Cryptography, Real Time: Precomputations in Elixxir
Elixxir was created to provide speed, privacy, and security on a global consumer scale. One of the building-block concepts of the Elixxir platform is the idea of precomputation. Let’s talk about why this is the case, and how precomputations represent an exciting breakthrough in providing real-time encryption to Elixxir users.
First, we need to know a little bit about cryptography. In its most basic form, cryptography is the art of writing and breaking codes. In cryptography, we assume a system is secure if it takes an unreasonable amount of time, money, or computation for an unauthorized third party to break the code. A very popular way to achieve this cryptographic security is through the use of public key cryptography. By using public key cryptography, and a sequence of relay/mix nodes, users can maintain both security and anonymity in sending data such as messages or payments.
Traditional cryptography takes time
While public key cryptography provides users with the benefits of security, up to now that security comes at a cost. Using public key cryptography to securely encrypt messages takes time. Common approaches to achieving both security and anonymity take even more time.
For example, mixing services provide anonymity by using a sequence of mixnodes to shuffle and relay messages to a destination, and typically require time-consuming public key calculations. The result has been services too slow to be used by consumers for real-time messaging or payments.
Precomputation offers a shortcut
How does Elixxir compress the time-consuming work of public key cryptography? By building a system that allows for precomputations, where the mathematical calculations are done in advance. To get us started thinking about what this looks like, consider this simple example:
Alice gave Bob a public key one week ago, and today Alice sends Bob a message encrypted with the shared key that results from that key agreement.
Since Bob has had the past week as a waiting period, he can spend part of that time calculating (or precomputing) the shared key in advance. When he receives Alice’s encrypted payload, he simply needs to do a simple multiplication in order to decrypt the message.
This example illustrates the concept of precomputation. In the real world, we need to add a few more layers of complexity. First, it’s unrealistic to give Bob a full week of precomputation time, so we will need nodes with the processing power to get the calculations done quickly. Second, in the Elixxir platform our nodes work as a team to process a batch of encrypted messages.
[Click here to read more about what makes Elixxir nodes special]
Elixxir nodes precompute the cryptography for the upcoming message paths and routes so that when it’s their turn to process a new batch, they can do so extremely quickly. Since nodes have open time scheduled between batches, they can spend that time interval running precomputations so that they will have a head start on the next batch.
The time savings for a system using precomputations are substantial. A mixing service using ElGamal decryption that precomputes the exponentiation can be 1000 times faster than a service without precomputations.
The Elixxir precomputation cycle
Now that we understand why Elixxir uses precomputations, let’s go into greater detail on the work done during precomputation. Each Elixxir node performs the following operations for precomputation:
Step 0 — Setup: A user who wants to send messages or payments using the Elixxir platform only interacts with precomputations once. When registering, users establish shared keys with the Elixxir mixnodes. Nothing else is then required from the user.
Mixnodes, which are responsible for shuffling messages and transactions, will collectively establish shared values for every round. Therefore, a team of nodes collectively establishes a global public key and individual secret shares, to be used in the multi-party homomorphic encryption system, a process that allows computers to run calculations on secure data while it remains encrypted.
Step 1 — Preprocessing: Group-homomorphic encryption allows the team of nodes to securely and collectively precompute the encryption values they want to use in the real-time phase. To do so, nodes operate on the ciphertext they received from the previous mix node in the team.
Step 2 — Mixing: The mixnodes multiply a new fresh value and apply a permutation to each slot. These individual permutations are used by each mixnode in the real-time phase and serve as a shuffle mechanism that masks the origin of the messages.
Step 3 — Postprocessing: To complete the precomputation, the nodes in the team finish the multiparty computation, by collectively decrypting the resulting values. Since this work was done under homomorphic encryption, this final step allows the team to collectively remove the masking factors and obtain the product of the encryption factors.
[Note that this is a highly simplified description of the precomputation cycle. For more details, please see the full cMix paper.]
Real cryptography, in real time, for everyone
The Elixxir team is excited to be working on a platform that delivers gold-standard cryptography at real-time speed. Although that combination may sound like magic, in reality we achieve these results through precomputations. This means that on the Elixxir platform users can use extremely secure cryptography to send a private message or payment without experiencing a noticeable delay. By harnessing precomputations the Elixxir platform also has an unprecedented capacity to grow to consumer scale.
[Interested in getting involved in Elixxir? We are currently accepting applications to run nodes on the Elixxir BetaNet. Learn more and apply today here!]
