from GeneWatch 27-1 | Jan-Apr 2014
Kristin Lauter, PhD, is a Principal Researcher and Research Manager for the Cryptography group at Microsoft Research. She has been working on practical homomorphic encryption for several years and was a coauthor of the breakthrough paper "Can Homomorphic Encryption be Practical?"
GeneWatch: How is homomorphic encryption different from other encryption technologies?
Kristin Lauter: The primary new functionality enabled with homomorphic encryption is the ability to compute on encrypted data. This is very important for things like outsourcing storage and computation of data. The idea is that when using homomorphic encryption, the data owner - let's say it's a consumer or an enterprise - could encrypt the data locally and keep the key. Then they can upload that data to the cloud, and if they used homomorphic encryption, that data can still be operated on by the cloud and the encrypted results are available from the cloud to the data owner or anyone the data owner trusts to share the encryption key with. So it really allows a whole new functionality on encrypted data.
The problem with many other types of encryption is that it makes data secure at the expense of making it unusable. Can you say anything more about what that means?
With standard encryption systems, after you encrypt the data there is very little ability to do anything with it. For example, AES is the government's standardized block cipher. When you encrypt something with AES, you should not be able to distinguish anything about the original data or operate on it in any way which gives meaningful results. In the last ten years or so there has been a push in the field of cryptographic research to invent techniques that allow you to encrypt data and maintain its privacy but still get some functionality out of it. Homomorphic encryption is a very general and powerful tool to allow computation on encrypted data.
Did you have encryption of genetic information in mind while working on this, or did that come up later?
Going back a couple of years, when we started on this work, my main focus was practical homomorphic encryption, as opposed to what people call fully homomorphic encryption. Practical homomorphic encryption focuses on computing certain high-value functions, ones that are more commonly used in practice. So we started with basic functions, statistical tools that people often want to compute on data, and our first goal was to show that if you restricted the functionality - if you decided ahead of time what kind of functions you wanted to compute on the data - you could do computation on encrypted data much more efficiently. Some of the original functions that we computed were just things like averages and linear regressions. As soon as we started to get into those tools, we thought about where they would be valuable, and genetics and genomics was one of the first areas that we thought about. In fact, Bill Gates had a long standing interest in computation on encrypted data and he asked us about that, so it was a high value target from the beginning.
So what are you working on now?
We've been looking at some of the basic genomics algorithms for pattern matching and substring matching. We looked at some of the queries that are made on genomic databases - basic functions, like genotype counts - and started working on using the ability to do those counts on homomorphically encrypted data, and on some more complex algorithms. These are all basic algorithms - not the most cutting-edge research in genomics, but the most basic algorithms, the ones which would most frequently be performed. And what we found is that when you take algorithms that have a low degree of complexity, practical homomorphic encryption can often be suitable for genomic data.
It sounds like you've been working with researchers or practitioners in genomics to see what would be most useful - or have you been focusing first on what's most challenging?
No, we're starting with what is the most useful. We started working with Yaniv Erlich at the Whitehead Institute, whose group was looking into issues of genetic privacy, but from the other direction, exploiting databases where genomic data is supposedly "de-identified" and re-identifying the data. Within Microsoft Research we've also been working with David Heckerman's eScience research group at UCLA.
Have you been thinking about other applications for practical homomorphic encryptions?
Absolutely. In our first paper we focused on the issue of medical records being hosted in the cloud. There's a lot of value in medical records being hosted in a cloud - for example, if someone moves, they can still have access to their medical records without having to go back to their original doctor. However, the privacy issues are tremendous, and also the liability issues for health care providers. So the idea of having an encrypted medical record system is very attractive - the idea that the patient and the doctor could control access to different parts of this record and selectively share it with others, be it family members, other doctors, or lab technicians. One of the things that we incorporated early on was the ability to search the medical records, and using homomorphic encryption, the ability to do basic computation on that data without sacrificing its security.
For example, as health monitors become more prevalent - imagine you have health monitors uploading encrypted data to a medical record hosted in a cloud. And as the data is continually uploaded, that's potentially a lot of data for a health care professional to have to look at for each patient. So you could have a synopsis of the data - averages, alerts, or other computations - so that periodic digests could be made available to the doctor.
It seems like a very high-value scenario. It's an area where people care about their privacy, and it's an area where having a service hosted in the cloud could be very valuable both for patients and for doctors.
What work is left to be done on practical homomorphic encryption?
Homomorphic encryption is just one of the techniques that we're focusing on, but we have put a tremendous amount of energy into it the past few years because we see it as high value, and it's just on the verge of becoming practical - it's already practical on small data sets and relatively low complexity functions. When you look into the future, what we'll be pushing on is making this type of homomorphic encryption more and more practical, adding functionality and researching ways we can take the highest-value functions and make them scalable and practical.