Friday, August 12, 2011

USENIX: Applied Cryptography, Refereed Papers

Differential Privacy Under Fire
Andreas Haeberlen, Benjamin C. Pierce, and Arjun Narayan, University of Pennsylvania.

There is a lot of data out there that is very important that we try to protect. For example, Netflix knows what movies you watch. Users rate movies in Netflix so that Netflix can make recommendations, but they don't necessarily want to share that information with the rest of the world. Simply replacing people's real names with pseudonyms is not enough, because if people know enough about you, then they will still be able to identify you from the available data and learn even more about you.

Even with protections, people can take advantage of timing attacks where they know the data must be in there, just based on how long the system took to reply to the query.

So, how can we avoid leaking information via query completion time? Their suggestion is to make timing predictable - so regardless of how long the query takes, always return at a constant time. That may mean padding on a delay, or aborting part of the query and returning an error.

By aborting the query, that could actually change the result, but the researchers say that's okay, because the default values will be set to what was expected if the lookout had completed (in this case 1, for true).

Their proposed solution, Fuzz, will pad this time in there, which sounds like it will solve the timing attack, but may make your transactions unacceptably slow, in my opinion.

The audio and video of this presentation are now online.

Outsourcing the Decryption of ABE Ciphertexts
Matthew Green and Susan Hohenberger, Johns Hopkins University; Brent Waters, University of Texas at Austin. Presented by Matt Green.

The researchers have been working on protecting medical records. By using cryptographic control on the records, you can encrypt the record for all valid participants, but that is not very flexible - what if you add, or remove, relevant people?

Attribute-based encryption (ABE) is a little more general. For example, you can encrypt data that can be read by "Cardiologist at Johns Hopkins", so if your cardiologist changes, your new doctor can still access your medical record.

The main problem is that the more complex the policy, the larger the ciphertext grows as well as the decryption time. For example, doing a decrypt on a smartphone could take up to 30 seconds - too long for practical use, particularly if you were a doctor that had to do these decrypts all day long.

The naive approach is to leverage the cloud to assist with the decryption, but you really need to trust your cloud....just too many vectors for attack.

Their approach is to have *two* keys - a transform key (TK) and a secure key (SK). The transform key, which can be in the cloud, can't fully decrypt the ciphertext by itself. The cloud would then partially decrypt the data, and the SK on the phone would complete it.

The researchers found that by doing this transform, which allows external assist, the decrypt time on their iPhone went from 28 seconds to under 2 seconds.

This same research can be applied to smartcards, which are very slow little chips.

The audio and video of this presentation are now online.

Faster Secure Two-Party Computation Using Garbled Circuits
Yan Huang and David Evans, University of Virginia; Jonathan Katz, University of Maryland; Lior Malka, Intel. Presented by Yan Huang.

The researches are trying to implement a system for secure 2-party computation using garbled circuits that is much more scalable and significantly faster than prior work.

This is based on prior work by Andrew Yao from the 1980s. While the garbled circuits theory has been around for a long time, prior implementations have been too slow to be used in practice. The researchers used a Yao chaining garbled circuit, and added a method of parallel processing to speed up the processing time.

Their framework doesn't require people to have expert knowledge about cryptography, but users will need to know basic ideas of boolean circuits. You can learn more and try out their Android app at their website,

The audio and video of this presentation are now online.

This article is syndicated from Thoughts on security, beer, theater and biking!