A beginner’s guide to Secure Multiparty Computation

A quick look into the function of secure multiparty computation (sMPC) and how we are using it to transform digital authentication and identity management.

Of all the problems to have, trying to prove you are richer than someone without revealing your net worth may be one of the most trivial. Yet the millionaires problem is an important problem in cryptography — and the solution has the potential to transform the way that data is stored and shared on the internet for good.

A game of who is richer

Three millionaires are out at a dinner party. They’ve never met before, and therefore, they don’t trust each other. The first millionaire, Jane, wants to prove that they have a higher net worth than James and Janet, the other two millionaires; however neither Jane, James or Janet want to reveal their net worths to each other, nor to anyone else.

How do three millionaires prove who is the richest without revealing each other’s net-worth?

Using an iPhone calculator, Jane chooses a random number to add to her salary. Once the random number is added, Jane passes her phone to James. James then adds on his net worth, and passes the phone to Janet, who then adds her net worth.

Once everyone has added their salaries to the calculator, the phone is passed back to Jane, who subtracts the random number she originally added. Then Jane can calculate their average net worth and share that, without learning net worth of any one individual. If one millionaire’s net-worth is lower than the average, then they will know they are not the richest.

While this example works if all the players are honest, there is some potential for players to cheat. For example, Jane has more power than the other millionaires. Since she knows the random number, Jane could potentially leverage this to try to learn more about the others. It is also possible for James or Janet to lie about their net worth, to try and learn more about the others.

This basic example illustrates how Secure Multiparty Computation, one of the underlying cryptographic techniques used by Keyless, works.

What is Secure Multiparty Computation?

Secure Multiparty Computation (sMPC), is at the core of Keyless. It is what allows us to be distributed, while simultaneously privacy-preserving. By merging sMPC with other cryptographic techniques, we can compare the encrypted biometric features of a user with those that they previously provided us — in complete privacy.

sMPC works by enabling different parties, each with private data, or “inputs”, to carry out a joint computation (for example, computing who is the richest millionaire, or, as we do in Keyless, measuring the distance between their inputs) without needing to reveal their private inputs to each other.

The millionaire example provides a simple use case to demonstrate how sMPC works, however this technology allows for all kinds of complex computation, which can be applied to many use-cases. Although theoretically possible for decades, the computational power needed to efficiently carry out sMPC has only recently become available.

sMPC opens up unlimited possibilities for privately sharing data between competing parties so that they are able to cooperate and gain mutually beneficial insights from that data, providing a solution to the growing debate around privacy and data collection.

Why is it called privacy-preserving computation?

The world today is driven by data — some of the greatest advancements in technology and breakthroughs in medicine can be attributed to data sharing. Adoption of sMPC could help shape a new era of online privacy, as it allows independent parties to gain insights into data without putting that data at risk of being compromised.

sMPC makes it possible for competing parties to learn things from their combined data without actually sharing it with each other. No party can learn anything about the other parties data, instead all they learn is the result of the computation is, allowing them to still make important decisions based on that result.

We are leveraging this technology to make online authentication, identification, and key management more private and secure.

How Keyless combines Secure Multiparty Computation with Shamir’s Secret Sharing algorithm

Keyless allows for seamless authentication, as well as the secure management of private cryptographic keys. To enroll and authenticate users in a way that preserves privacy and increases security, Keyless combines sMPC with another important cryptographic algorithm called Shamir’s Secret Sharing (SSS) scheme.

SSS allows for private data to be split into unrecognisable pieces and distributed across a decentralized network, while requiring just a fraction of those shares to reconstruct the private data.

When a user initially enrolls for an account with Keyless, we securely distribute their encrypted biometric template to the nodes in the Keyless network. Then, if that user has private cryptographic keys, we use SSS to securely split these private keys into encrypted shares and send them to the Keyless network.

When a user authenticates with Keyless, we use sMPC to verify that the information sample provided by the user matches the biometric templates that are stored across our distributed network. Once the network verifies that the templates are a match, the user is authenticated. If the user stores their private keys with Keyless, each node independently sends back encrypted shares of the private key to the user.

Since the original template is encrypted, members in the Keyless network never see the actual biometric template, instead they measure the distance between the new sample and the stored template. If the distance is close enough to be a match, the user is authenticated and granted access to their accounts.

At no time, does anyone in the Keyless network have access to personal data — whether that’s someone’s biometric template or private keys. This allows us to securely identify and authenticate users without needing to learn anything about them.

Preventing malicious takeovers

In cryptography, a malicious adversary is a cheater or an attacker whose goal is to prevent a system from working as intended. Adversaries may attempt to discover or corrupt private data, attack the Keyless network, or impersonate a user.

Keyless combines a variety of cryptographic techniques to prevent malicious adversaries from succeeding, and to prevent data from being lost or mishandled.

Keyless always encrypts a user’s biometric sample and cryptographic keys before sending them to the Keyless network. For a malicious adversary to gain access to private data stored in the Keyless network, they would first need to compromise a majority of our nodes that held a user’s shares.

However, even if an attacker were to accomplish this and gain access to a majority of the shares, they still wouldn’t learn anything about the original information, as it is encrypted during the initial enrollment stage — and the decryption key is permanently stored in the user’s devices.

A private future

sMPC and SSS challenge the way we think about data sharing and identity management. With this technology it’s possible to have a future where everyone can benefit from sharing private data to gain important insights and learnings, without needing to worry about security and privacy risks.

While this technology is the backbone of Keyless, it is not exclusive to us — any company or organisation can leverage these techniques in order to share and learn from data in a way that is secure, and that does not jeopardise the privacy, safety and livelihood of others.

We believe that the widespread adoption of these technologies is key to building a better world — one where one where security and privacy are not traded for convenience, and one where users are empowered and in control of their personal data.