Sharing Secrets (without Giving Them Away)

Secure multiparty computation enables two or more parties to share sensitive information and process it for a common purpose, without giving up privacy. A fairly simple example is on-line secret balloting, but now, more advanced pilot projects in medicine and genetics are starting up.

Encryption can never solve all privacy issues; in many cases, only sharing data with other parties whom you should not trust unconditionally produces useful results. Sharing data without giving up your privacy sounds like having your cake and eating it too, and that's exactly what secure multiparty computation does.     

This year, Ronald Cramer, cryptographer at the Dutch Centrum voor Wiskunde en Informatica (CWI) research center, received a €2.50-million ($2.95-million) grant from the European Research Council to further develop (among other things) secure multiparty computation. He is now collaborating on several use-cases with electronics giant Philips, technical research hub TNO, and the University of Amsterdam.

Cramer says of secure multiparty computation, "The fundamental ideas have been around since the '80s, but until recently, they were of theoretical interest only." In real-world applications, secure multiparty computation involves large amounts of data and multiple rounds of communication, making heavy demands on computer speed and bandwidth. Improving the runtime of an algorithm by even 15% can be critical. "This is programming on a knife's edge," says Cramer.

Counting the votes

The simplest textbook example of secure multiparty computing consists of three people who want to vote yes/no (1 or 0) on some topic, without revealing their individual votes, and without a trusted authority to count the votes. Surprisingly, this can be accomplished by having each voter choose three random numbers. To every other voter, he then sends the sum (modulo some public number N) of his vote, plus two of the three random numbers (a different pair for each receiver). Every voter then adds the numbers he gets from the others, and makes this number public. The sum of these three numbers, modulo N, is the number of yes-votes.

This kind of privacy protection does not depend on encryption, but on general properties of random numbers, so it cannot be broken (assuming certain limits as to how much the parties involved can eavesdrop and collude). For more than three parties and more than simply counting, the algorithms get much more complex, and can require many more rounds of communication.   

Hospital workflow

The pilot project Cramer is working on with Philips Research and TNO aims to optimize the workflow in Dutch hospitals. Says Supriyo Chatterjea, from Philips Research, "What usually happens is, they call in a lot of consultants who spend weeks on site, interview staff, follow them around, and draw conclusions.' However, understandably, employees don't behave as usual with a consultant looking over their shoulders.

That's why in this project, every employee and patient, and even the equipment, gets a locator tag, reporting its exact position every few seconds. Even knowing about the tag will change employee behavior at first, so the researchers wait a few weeks for things to settle down before recording taking data.

Analyzing this tracking data can reveal bottlenecks in the workflow, but obviously there is a privacy problem, says TNO's Thijs Veugen. "You don't want to get this kind of conversation with employee X: 'we see you spent quite a long time at the coffee machine.'" To avoid that, the data is split between two parties: staff data is only accessible to the workers council, while only the hospital has access to patient data. In this way, secure multiparty computation can protect everybody's privacy, while still distilling useful results on workflow.

Says research scientist Meilof Veeningen of Philips Research, "Tracking in certain hospitals is now ongoing. We are still figuring out what the application will be. It might be a one-off solution for consulting, or a 'dashboard' for continuous monitoring of the workflow at the hospital."

TNO's effort takes the middle ground between theoretical research at universities and practical applications by commercial companies. Says Veugen, "We look at things like, can we process all the data in time, after each shift at the hospital?"

Veugen and Cramer also are working with Emiliano Mancini at the University of Amsterdam to apply secure multiparty computation to the improvement of the treatment of HIV patients. Every patient's virus has different mutations, with different levels of resistance to various medicines. By combining data from multiple patient databases, much can be learned about optimizing the treatment for individual patients.

Safeguarding the privacy of the patients using secure multiparty computation makes it a lot easier for institutes around the world to share data for joint research projects. Observes Veugen, "Without secure multiparty computation, you could derive who slept with whom."

Yao's protocol

In a related development, in August, a group from Stanford University reported in Science how they compared the genomes of small groups of patients to identify genes that are a risk factor for rare inheritable deseases. By using Yao's protocol, such genes were identified, while less than 1% of the genomes of the patients in one group became known to another group.

Yao's protocol involves numerous random keys and heavy computation. Yet the Stanford scientists showed such data could be securely compared in minutes between computers on opposite sides of the U.S. However, Yao's protocol is too cumbersome for comparing the genomes of thousands of people; even for the small groups involved in this research, various shortcuts had to be adopted to optimize speed.

Cramer's mission, to further develop secure multiparty computation and optimize it for large-scale application, has to be done with great care, as he notes, "You can never simply outsource cryptography to software engineers. They always want to make things faster and more efficient. They'll want to send information in one round of communication instead of multiple rounds, but then, security can be compromised.

"Optimization always needs to be done in consultation with cryptographers."

Arnout Jaspers is a freelance science writer based in Leiden, the Netherlands.