Secure computation on confidential data
How can data from multi-party computation be used in a calculation if this data must be confidential? Danish computer scientists have come a step closer to an answer.
You see a porcelain cat at an online auction and you just have to own it. The highest bid is currently at €12, but you are actually willing to pay up to €20 for the cat, as it fits perfectly into your large collection of porcelain animals.
You start your bidding at €12.01, crossing your fingers that you will get the cat at that price.
The auction runs for another four hours, but you are not intending to sit in front of your computer until that time to see if you are outbid.
Instead, you specify your maximum bid of €20 and instruct the auction system to overbid automatically if necessary.
But what if the auction host is corrupt? What if fake bids are added because the system knows that you will overbid up to €20? That would increase the seller’s earnings, and the auction host would also profit from it.
Method protects against fake bids
It can be difficult to protect oneself from such scenarios, but it is not impossible. Computer scientists from Aarhus University, Denmark, and the University of Bristol, UK, have come up with a method for keeping your maximum bid secret, not only to fellow bidders, but also to the auction host.
The researchers described the method at the ESORICS (European Symposium on Research in Computer Security) symposium, held recently in England.
Here, European researchers were so impressed by the Danish/British work that the project received the Best Paper Award.
No need for trust
With this method it is possible to compute on data from a variety of sources in a way ensuring that the data remains secret at all times, since all calculations are performed efficiently on encrypted data.
We can offer a secure service, which guarantees that you can leave the auction without worrying about anyone knowing your maximum bid before the end of the auction.
Ivan Damgård
”We can offer a secure service, which guarantees that you can leave the auction without worrying about anyone knowing your maximum bid before the end of the auction,” says Professor Ivan Damgård, of Aarhus University’s Department of Computer Science.
"You don’t need to trust any particular party. Instead, we have a distributed service, which is implemented in a variety of computers and where confidentiality is guaranteed.”
Data is encrypted
The method is not restricted to auctions. In a wide variety of contexts, the parties delivering data for some kind of calculation have the option of keeping their own data secret, while still having access to the results of the calculations in which their data, as well as other people’s data, is included.
”With our method, everyone who owns data can take part in the calculation,” says Damgård. “We can ensure that none of the parties have access to the data being calculated, because it is encrypted. Nevertheless, they can still jointly calculate the result.”
Over the past five years, the efficiency of the method has increased about 1,000-fold. It is now possible to calculate on data without having access to it, almost as quickly as if the data was not encrypted.
Ivan Damgård
The method can for instance be used in a secret electronic ballot. Here, everyone can cast a vote, without the possibility of other people finding out what each person voted. Only the end result of the ballot becomes available to all.
Everyone wants the result
Another example is benchmarking, where users want to know where they stand in relation to others, but without disclosing their own data. It can e.g. be interesting for businesses to know how they stack up against the competition, but nobody wants to reveal how things are going for them. The new method solves this problem:
”Rather than having one person looking at all the data, we offer an automated service with full privacy,” says the professor.
”This is a good example of a scenario in which many parties have private data and where all the parties want a result that depends on all the private data.”
The new method is effective
For many decades multi-party computation (MPC) had been a predominantly theoretic endeavour in cryptography but in recent years, interest has arisen on the practical side, explains Damgård.
“Over the past five years, the efficiency of the method has increased about 1,000-fold. It is now possible to calculate on data without having access to it, almost as quickly as if the data was not encrypted.”
The researchers are currently trying to find ways of commercialising the method through the spin-off companies Partisia and Sepior.
-----------------------
Read the Danish version of this article at videnskab.dk
