PGP CTO Blog

Security & Privacy: Striking the Right Balance
08 Mar 2006

In the world of cryptography in 2005, hash functions got most of the press; however, there were other advances that haven't been in the limelight, but are going to be more significant in the long run.

There is a common myth that you can't have both privacy and security. The problem with this myth is that it's true enough that refuting it takes a bit of work. Certainly, it's easy to make a security system that takes away privacy. It's even easier to make a system that takes away privacy while not actually providing any security, either. It's also easy to make a privacy system that makes it easier for bad people to act badly, and even easier not to deliver on privacy or security.

It isn't impossible to combine security and privacy: it just requires thought and work as well as balance. There are also new technologies and systems being developed that help create security while preserving privacy. Furthermore, privacy-preserving technologies can improve security because they improve privacy.

At the 2005 CRYPTO conference, my pick for best paper was on such a new system. The paper, "Privacy-Preserving Set Operations," is by Lea Kissner and Dawn Song. This concept may sound abstruse, but sets are commonly used; for example, databases are sets. There are a number of immediate uses for this approach.

• Consider the U.S. government's "No Fly" list and the list of people flying on airlines today. The names on both those lists is the intersection of two sets. If you can perform that intersection without requiring either party to reveal the set itself, then you can know who is flying today who is on the No Fly list without handing over the passenger list to the government. Of course, this process still doesn't answer the question of whether this information is actually useful. Nor does it deal with false positives (people who happen to have the same name as someone on the No Fly list) or false negatives (people flying with fake names or people who should be on the No Fly list).
• Suppose you wanted to know how many people being treated for cancer are on welfare. Or how many of them checked out books from the library, belong to a social networking website, or even are on the No Fly list.

Privacy-preserving set operations allow you to do research that would otherwise be impossible or require some trusted intermediary to do. Even more interesting, they handle multiple sets and some interesting provisions that guard against a number of different types of cheating.

Kissner"s and Song's work is significant because it creates new possibilities. It opens up opportunities to look at populations in new ways because it preserves the privacy of the members of those populations. As always, new possibilities are scary, and there are going to be results that are a bit unsettling.

Let's take the No Fly list example, which was the first one Ms. Kissner gave in her presentation at CRYPTO 2005. Being the sort of person I am, I sneer at it. To me, it seems that the No Fly list's security relies on the assurance that terrorists do not have the sort of access to fake ID technology that exists in most U.S. universities. Because there are no export controls on fake IDs, we have to worry about the privacy considerations of the government collecting all flight information. If we remove the privacy considerations from the equation, we are then left with nothing but practicality.

Similarly, if we can conduct medical research, marketing research, or create more social networking websites without privacy concerns, of course there will be more such research and use of personal data. The prospect of even more widespread use of personal data is a bit unnerving, even if it's good news to protect privacy. Existing issues, such as who gets access to the data and where it might wander to are still concerns, but I am getting close to giving a gift horse a periodontal exam.

I'll write another article soon on another new, exciting technology that preserves privacy.

Background Reading

“Advances in Cryptology - CRYPTO 2005: 25th Annual International Cryptology Conference,” Springer-Verlag GmbH, Volume 3621 / 2005

CRYPTO 2005

Kissner, Lea and Dawn Song, “Privacy-Preserving Set Operations,” CMU-CS-05-113, June 2005

Kissner, Lea and Dawn Song, “Privacy-Preserving Set Operations” (Presentation), Carnegie Mellon University