Thursday, April 30, 2015

Eurocrypt 2015: When life gives you Fully Homomorphic Encryption...

On Wednesday morning, Kristin Lauter gave an invited talk about the Practical Applications of Homomorphic Encryption. She started by talking about a recent competition on Secure Genome Analysis sponsored by the (American) National Institutes of Health at the iDASH Privacy & Security Workshop, which received a substantial amount of media coverage.

Kristin reasoned that this excitement was caused in part by the fact that with the rise of relatively inexpensive genome sequencing, privacy is becoming a fundamental problem. A person's genome can give information on genetic diseases that the person has, as well as partial information on the genetic make-up of close family members. Leaking this information can lead to genetic discrimination, for example from health insurance providers. Still, this kind of data can be put to good use as well, such as personalized medicine, biomedical research and ancestry or paternity tests, so we would like to give researchers access to this data without breaking the privacy of the data donors.

Therefore, the aim of the competition was to devise ways of performing analysis on genomic data in a secure manner, which was implemented with two different tracks. The first track considered the scenario where one party owns all the data, like a hospital that wants to protect the privacy of its patients, which is an ideal scenario for Homomorphic Encryption. The second track considered the scenario where there are multiple data owners that mutually distrust one another, which is an ideal scenario for Multi-Party Computation. There were teams from both industry and academia. The used data was part real data from donors and part simulated data.

Kristin described a few different tasks: counting the frequency of minor alleles, and computing the Hamming and Edit distances for the alignment of genomes. The frequency count can be performed by purely additive homomorphic solutions, but schemes based on RLWE allowing for more homomorphism were still competitive. On the other end of the spectrum was the Edit distance, which consists of a relatively deep circuit. However, in practice it is often good enough to have an approximation, as it allows for a shallower circuit such that even existing schemes can provide a practical solution. Each task had a different winner, indicating that there is currently no best solution for all applications.

This competition spurred fundamental progress in the field of secure genome analysis through the interaction between computer scientists, mathematicians, bio-informaticians and policy-makers. Kristin therefore also highlighted the importance of communicating the concept and possibilities of Homomorphic Encryption to the general public, in order to find more good applications. One major point of the invited talk was that there are applications out there right now that can be implemented using relatively shallow circuits, such as the aforementioned secure genome analysis, but also the evaluation of private models in the cloud and machine learning. These applications can be solved by the schemes we have today, even with their inefficiency drawbacks.

That is not to say there are no more challenges to be solved. Storage costs are a problem as Fully Homomorphic Encryption schemes suffer from substantial ciphertext expansion. The security is not always as well understood as we would like. The efficiency does not scale very well to deep circuits and large amounts of data. These are but some of the challenges that Kristin outlined at the end of her talk. So let us work together and make some lemonade!

No comments:

Post a Comment