When we talk about security, we frequently mention features that wrap existing applications like a protective cloak. For many, these additional layers are primarily associated with additional hassle, which is accepted to protect one’s own company and clients. What we hardly ever consider is the creative potential of products from security research. There are products that allow us to create applications that were previously almost unimaginable due to privacy concerns and astronomical costs. This article aims to provide a new perspective on cybersecurity through an example, where it is not an obstacle but an open door for new applications.

To make this idea a little more tangible, let’s start with a concrete thought experiment. Two physicians, Dr. Alice and Dr. Bob, from different institutions have a hypothesis that individuals with a particular pre-existing condition X are particularly susceptible to another condition, Y. They would like to test their hypothesis, but each alone has too little data to obtain statistically significant results. As physicians, they are bound by the strictest data and patient protection laws, and at the same time are required to keep their research costs as low as possible. They would be allowed to use and share their data if they anonymize them. However, this would most likely result in the loss of important details and decrease the accuracy of their research results.

Our two doctors are overjoyed when they come across a modern solution to their problems: Secure Multi-Party Computation. That’s what this article will be about.

What is Secure Multi-Party Computation?

The general term Secure Computation covers all computation methods, with which the data, on which is computed, remain secret. Secure Multi-Party Computation, in the following called MPC, is nothing else than a computation method, with which several parties can perform a computation jointly, without ever revealing their own input values. This includes the fact that one party cannot infer the input of other parties from the result of the computation. One of the great advantages of MPC is that not only do the parties not have to trust each other with their data, but also no additional third party receives data.

In the early days of MPC in the 1980s, the existing protocols were considered a purely theoretical construct. After the improvement of existing algorithms and the inexpensive, strongly increased computational power of the 2000s, the protocols became practical and nowadays the first companies already offer MPC software solutions.

The protocols of today can be roughly divided into two groups: Garbled-Circuit Protocols are often used in systems where only two parties interact. These protocols are based on the so-called Oblivious Transfer and Boolean Circuits. If more parties are involved, Secret Sharing-based Protocols are used. While Boolean Circuits should be familiar to most, the two building blocks Oblivious Transfer and Secret Sharing are briefly introduced here to give an intuition why something like MPC can work at all. We also look at possible threat models and their powers.

Oblivious Transfer

The goal of Oblivious Transfer (OT) is to deliver a message to a recipient without the sender knowing the final content of the message. This is realized by the sender sending several secrets to the recipient, and the recipient selecting from them. The sender does not know which secret the recipient has selected. The recipient, on the other hand, only learns the secret that he himself has selected.

This allows one party, e.g. Dr. Alice, to perform her part of the calculation while respecting all possible input values of Dr. Bob. For simplicity, let’s assume Bob’s input values are either 0 or 1. She sends only her results m₀, m₁ encrypted to Dr. Bob, who can now select and decrypt a result m_b. He selects thereby the result, which corresponds also to his input into the computation. Since Dr. Alice already included all possible input values of Dr. Bob, the computation is thereby complete, without one of the two having learned something about the input values of the other.

Secret Sharing

Secret Sharing is a method of dividing a secret among n parties in such a way that only when a certain number of parties t combine their shares of the secret can the entire secret be recovered. Such a method is called a (t, n)-threshold scheme. Thereby, in a secure secret sharing protocol, a combination of less than t shares reveals nothing about the entire secret. This property is known as Perfect Privacy and is essential in an MPC protocol. A commonly used approach to share a secret among multiple parties is to use a so-called Trusted Dealer. It generates the secret and the shares, but is otherwise not involved in the protocol, i.e. does not receive any data from the parties.

While secure (t, n)-Secret-Sharing protocols for general t can get very complicated, there is a procedure for (n, n)-Secret-Sharing that is very simple to explain. It requires all shares from all parties to reconstruct the secret.

⊕ is the XOR operator. We take a binary string s of arbitrary length. Then we generate n-1 random binary strings p_i of the same length. We distribute these to n-1 parties. The last party gets the string resulting from the following operation:

p_n = s ⊕ p₁ ⊕ p₂ ⊕ … ⊕ p_n-1

The secret can thus be reconstructed from the XOR of all shares, with fewer than n shares revealing nothing about the secret s.

p₁ ⊕ p₂ ⊕ … ⊕ p_n-1 ⊕ p_n = p₁ ⊕ p₂ ⊕ … ⊕ p_n-1 ⊕ (s ⊕ p₁ ⊕ p₂ ⊕ … ⊕ p_n-1) = s ⊕ (p₁ ⊕ p₂ ⊕ … ⊕ p_n-1) ⊕ (p₁ ⊕ p₂ ⊕ … ⊕ p_n-1) = s

Threat Model

Anyone who regularly deals with security may now wonder what attackers these protocols can actually withstand. The answer is a general one: It depends on the protocol used. There are protocols that deal with active attackers, so-called “malicious adversaries”. Such attackers are able to deviate arbitrarily from the protocol’s predicted course.

Most common and relevant, however, is the semi-honest adversary, also called honest-but-curious or simply passive attacker. A passive attacker tries to learn as much as possible about the other parties in order to obtain private information. However, he does not deviate from the protocol, but participates properly. It is important to consider that a passive attacker can compromise multiple parties and could thus combine the views and data of multiple participants.

This also makes sense with regard to our example: Neither of our physicians is interested in completely sabotaging their research. But it could be that one of them would like to learn a bit more about the other’s patients, even though he is not allowed to do so. The job of the protocol is to make sure that this is impossible.

Applications

In the following, we will look at several application areas of MPC to get a more holistic picture of the technology’s potential.

Medicine

In medicine, MPC is mainly considered to make research more accurate and scalable despite strong patient protection laws. Especially the ability to share data so that others can use but not read it is important. In recent years, interest in this area has grown strongly and the first products have already been commercialized on the market. In Switzerland, especially MedCo is worth mentioning, which has emerged from a collaboration with the EPFL and is dedicated to sharing and analyzing data with MPC and similar technologies.

Privacy-Preserving Genomics

A particularly highly regulated field in human research is research with biological material. Research on the human genome in particular frequently faces obstacles, some of which MPC can help alleviate. A competition called iDash has research teams compete in different tracks of their “Secure Genome Analysis Competition” every year, where promising solutions in MPC, homomorphic encryption, and other security technologies are regularly awarded prizes.

Auctions

A common requirement for auctions is that bids remain sealed and cannot be manipulated. Examples of this are first and second price auctions, where all bids must be submitted covertly. These features can be offered by MPC, as they only need to be embedded in the jointly performed calculation. This is also why one of the most popular examples of commercial MPC projects is the famous Danish Sugar Beet Auction.

In the 2000s, reduced subsidies for sugar beet production meant that sugar beet prices had to be renegotiated. Sugar beet farmers were concerned that their bids revealed much about their own financial situation and therefore demanded privacy in front of the processing company Danisco, which was a monopoly in Denmark. The Danish government, together with researchers, therefore developed the first MPC-based auction with three parties (the processing company, the farmers, and the researchers). This allowed an efficient secret-sharing protocol to be used, and the auction is regarded as a great success. The project led to the creation of the company Partisia, which continues to provide support to companies for secure auctions.

Studies

Two other projects that are very often mentioned as successful MPC projects are the Estonian Student Study and the Boston Wage Equality Study.

In Estonia, universities were concerned about the fact that many IT students were dropping out of their studies early. In 2015, a study was therefore conducted to determine whether working students were more likely to drop out of their studies than students who did not work. University data and tax data were to be analyzed to determine this. The various government bodies were not allowed to share their data for privacy reasons unless it was aggregated, which would have resulted in a loss of accuracy (though the opportunity was still used for a comparative study). The company Cybernetica offered their framework Sharemind for a MPC solution, and the study was successfully conducted with three parties. No correlation between work activity and dropout was found.

Several years ago, in the Boston wage equity study, the city and the Boston Women’s Workforce Council wanted to examine inequities in wage payments, but privacy concerns prevented direct sharing of wage data. Boston University researchers then developed a web-based MPC application where employees could securely and secretly report their wages. The analysis was then successfully conducted.

Research with Personal Data

In our thought experiment, the two doctors Dr. Alice and Dr. Bob want to conduct research with patient data. We now look at why this is so elaborate as to make the use of MPC worthwhile. Generally, any kind of human research requires the approval of an ethics committee, and this is no exception.

We know that the data on disease X were not collected in the context of a clinical trial, but during the usual treatment of patients. The study by Dr. Alice and Dr. Bob is a so-called retrospective study. Furthermore, we assume that the data does not consist of biological material. Research on biological material is even more tightly regulated, but MPC can help here as well, and research in this direction has attracted increasing interest in recent years.

If Dr. Alice and Dr. Bob were to conduct research only for themselves and did not want to contact each individual patient (scalability), they would need to convince an ethics committee that the public interest (through better therapies, for example) outweighed the patient’s interest. This is usually the case in medical research, provided that no conclusions can be drawn about individual patients in a publication of the research.

Since the physicians want to conduct research together, they would, under normal circumstances, access each other’s data that they have not collected themselves. They would therefore have to be particularly careful not to breach medical confidentiality. There are three ways to do this: Patients give their consent, the data is anonymized, or they adhere to the special protocol for sharing non-anonymized data for research purposes, which, however, may only be used under very specific conditions.

This is where MPC comes into play. We recall that the data is shared only in encrypted form, so the other person cannot read it at all. Sufficient encryption makes the effort of re-identifying the patients disproportionate and from the point of view of a party without a key, the data must be considered anonymized. Since this is not biological material, this means that the patient’s consent is no longer necessary, as long as care is also taken to ensure that the patients cannot be identified if the research is published. Since we did not have to resort to any possibly aggregation-based anonymization mechanisms, we do not face any loss of accuracy.

In Switzerland, anonymized, pseudonymized and thus also sufficiently encrypted data are overall no longer considered personal data. However, the most common anonymization and pseudonymization procedures are very complex and often lossy, provided they are performed with the appropriate care. Therefore, MPC is also relevant for non-medical studies with high demands for accuracy.

However, for all the enthusiasm, it should not be forgotten that, as with classical studies, much statistical power depends on the format and accuracy in which the data were originally collected. MPC can primarily perform calculations, which helps in finding commonalities, correlations, and comparisons. MPC is not able to interpret free text or import data from different formats. This type of work is part of preparing a study with MPC and, depending on the data, the effort required should not be underestimated. However, it is reasonable to assume that a similar amount of work would be involved in any high-quality, statistically meaningful study.

Digitization in Switzerland and International Comparison

Switzerland’s federal, multilingual healthcare sector presents no small number of obstacles, and many of the goals of the Federal eHealth Strategy are far from being achieved. However, it is worth looking at the various promising research projects of the Swiss Personalized Health Network, many of which are closely linked to security technologies.

Estonia is usually cited as a shining example of the “digitization of public services. What is interesting here is not only the technology thanks to which the various sectors can interact with each other, but also how the public acceptance of these technologies has been addressed.

Conclusion

Secure Multi-Party Computation is a technology that makes research possible while respecting strong privacy laws. It allows data sets to be linked and correlations to be established where accurate analysis was previously impossible. Different parties are no longer forced to trust each other with their data. This feature is of great importance for many research fields, but also for industry, and can provide a significant digitalization advantage.

However, most projects carried out to date have involved increased technical effort, as they had to be specifically tailored to the project in question. The necessary development is therefore moving in the direction of more general frameworks that are sold commercially. However, it is likely to be a while before MPC becomes truly easy and quick to use.

Last but not least, Dr. Alice and Dr. Bob have been able to analyze and evaluate the suffering of their patients across institutions and in compliance with Swiss data protection and human research laws, and have found that disease X does not lead to a susceptibility for disease Y.

Further Material

• Semester Thesis Why Johnny Can’t Compute Securely: Exploring the Gap between Threat Models and Stakeholder Concerns
• Book A Pragmatic Introduction to Secure Multi-Party Computation

About the Author

Lena Csomor is working on her master’s degree in computer science at ETH Zürich with a major in secure and reliable systems. She had two internships as a security consultant and in the R&D department of an IoT vendor. Her main focus is privacy-preserving technologies (MPC, FHE, differential privacy). (ORCID 0000-0002-9537-4253)

Links

• http://www.humangenomeprivacy.org/2021/
• http://www.ilo.org/wcmsp5/groups/public/—-ed_emp/—-emp_policy/documents/publication/wcms_781500.pdf
• https://cyber.ee/
• https://eprint.iacr.org/2008/068.pdf
• https://eprint.iacr.org/2019/734.pdf
• https://ethz.ch/content/dam/ethz/special-interest/infk/inst-infsec/appliedcrypto/education/theses/Lena_Semester_Project_Hand_In.pdf
• https://medco.epfl.ch/
• https://partisia.com/about-partisia/
• https://smw.ch/article/doi/smw.2010.13041
• https://sphn.ch/de/home/
• https://www.bag.admin.ch/bag/de/home/strategie-und-politik/nationale-gesundheitsstrategien/strategie-ehealth-schweiz.html
• https://www.fedlex.admin.ch/eli/cc/2013/642/de#a26
• https://www.sciendo.com/article/10.1515/popets-2016-0019
• https://www.zh.ch/de/gesundheit/ethik-humanforschung/daten-proben-datenschutz.html