A short introduction to Multiparty Computation (MPC)

Multiparty Computation (MPC) is a technology that allows you to compute on encrypted values. This might sound impossible at first – but in fact, using the right kind of cryptography, it is indeed possible. Using MPC a number of servers can jointly compute any function without learning the inputs to the function. 

A small example is that of a group of people desiring to compute their average salary, without any individual group member revealing her personal salary to the others. Using MPC is is possible for them to jointly compute a function which takes as input the secret salary of each group member and reveal only one piece of information: the average of all these (secret) numbers.

In the case of Sepior, the more interesting functions are encryption and decryption. Using MPC, a set of servers can, for instance, encrypt a value without seeing this value nor the key used to encrypt it!

Secret sharing

One cryptographic tool which allows you to do MPC is secret sharing. Suppose that a secret x=42 is to be shared among two servers. If we choose two random numbers x1 and x2 such that x=x1+x2 (e.g. x1=50 and x2=-8) and give x1 to the first server and x2 to the second, then neither server will know the secret x. Indeed, the first server only learns the number 50, and from its point of view, the other number could be any integer. Of course, 50+"anything" can result in anything. Similarly we might secret share another number y=23 between the two servers (e.g. y1=20 and y2=3). The two servers can now compute x+y and make the result public, without either server learning x nor y. The first server simply computes x1+y1 and sends the result to the second server, which can then compute x1 + y1 + x2 + y2 = x + y, all of this without any server learning anything about x nor y, other than the sum.

The interested reader can use these ideas about secret sharing to design a protocol for computing the average salary (the case mentioned above), assuming that the number of group members is public knowledge.

A central result in cryptography is that secret sharing and similar ideas can be extended to allow the computation of any function that a traditional computer can compute. Of course, due to the complexity and distributed nature of this computation, performance suffers.

A core part of the intellectual property behind Sepior is deep knowhow about implementing MPC protocols, plus patented protocols which allows us to do symmetric encryption with near-realtime performance.

Distributed or Virtual HSM using Threshold Trust

Using MPC it is possible to build a virtual, or distributed, Security Module. Instead of relying on tamper protection of a physical box, we instead rely on strength in numbers, or as we call it: Threshold Trust. This is what Sepior is about. We use MPC to build a virtual HSM, which can safely store and use encryption keys.

The idea is to compose a virtual HSM out of a number, N, of so-called key servers. A cryptographic key is then shared so that each key server will have one share of the key (in the spirit of secret sharing). Furthermore, we use a threshold, T ( 1 ≤ T ≤ N), so that any T (but no less) shares will allow you to re-construct the key. In other words, as long as an attacker cannot successfully compromise at least T (the threshold) servers, the key is secure.

As an example assume that the number of key servers you think are needed before collusion is unrealistic (called the trust threshold) is 2. Assume further that for high-availability, you believe that no more than 1 out of 3 key servers will have outages simultaneously. In threshold trust we would denote this as a 2/3 setup. As long as no two servers are compromised the confidentiality of system is intact, and as long as no more than one server is down the system is available.

Our protocols are designed to work for any T/N setup as long as 1 ≤ T ≤ N. In practice a realistic configuration may be an 8/10 setup, and they may scale to a setup as large as 97/100 with further optimization using tailored algorithms.

In other words, if you use an 8/10 setup, the two core threat actors against the system are mitigated as follows:

  • A malicious insider at 1 key server must work together with insiders at 7 key servers.
  • The outside attacker must compromise 8 different key servers.

With respect to availability, even if two of the 10 key servers are down, the system will still work.

Jakob Illeborg Pagter