How to Search on Encrypted Data: Searchable Symmetric Encryption (Part 5)

This is the fifth part of a series on searching on encrypted data. See parts 1, 2, 3 and 4. In the previous post we covered the most secure way to search on encrypted data: oblivious RAMs (ORAM). I always recommend ORAM-based solutions for encrypted search whenever possible; namely, for small- to moderate-size data 1. Of course, the main limitation of ORAM is efficiency so this motivates us to keep looking for additional approaches.

Read more

Is the NSA Metadata Program Legal?

One of the most interesting aspects of the NSA metadata program is whether it is legal or not. Unlike the questions we usually think about in computer science, this question has no definitive answer. The program is legal in some sense, but the logic needed for the argument to go through is so questionable that you could just as well say that it’s not. Recall that the program requires telephone providers to hand to the NSA (each day) the metadata of every US-to-foreign, foreign-to-US and US-to-US call.

Read more

Restructuring the NSA Metadata Program

I just got back from Barbados where I attended the Financial Cryptography and Data Security conference. It was a great event overall with many interesting talks and two great workshops. One workshop was on Bitcoin and was the most successful Financial Crypto workshop in history! Though I haven’t personally worked on Bitcoin, one of the things I enjoyed most about the conference and workshops was the presence of the Bitcoin community.

Read more

How to Search on Encrypted Data: Oblivious RAMs (Part 4)

This is the fourth part of a series on searching on encrypted data. See parts 1, 2, 3 and 5. In the previous posts we covered two different ways to search on encrypted data. The first was based on property-preserving encryption (in particular, on deterministic encryption), achieved sub-linear search time but had weak security properties. The second was based on functional encryption, achieved linear search time but provided stronger security guarantees.

Read more

How to Search on Encrypted Data: Functional Encryption (Part 3)

This is the third part of a series on searching on encrypted data. See parts 1, 2, 4 and 5. Previously, we covered the simplest solution for encrypted search which consisted of using a deterministic encryption scheme (more generally, using a property-preserving encryption scheme) to encrypt keywords. This resulted in an encrypted search solution with sub-linear (in (n)) search time but that leaked quite a bit of information to the server.

Read more

How to Search on Encrypted Data: Deterministic Encryption (Part 2)

This is the second part of a series on searching on encrypted data. See parts 1, 3, 4 and 5. In this post we’ll cover the simplest way to search on encrypted data. This is usually the solution people come up with when they first think of the problem of encrypted search and, as we’ll see this, this approach has some nice properties but also some limitations. To make this work we’ ll need a special type of encryption scheme called a property-preserving encryption (PPE) scheme.

Read more

How to Search on Encrypted Data: Introduction (Part 1)

This is the first part of a series on searching on encrypted data. See parts 2, 3, 4 and 5. I recently finished giving a series of talks on one of my favorite topics: searching on encrypted data. My slides are available here, but given the current interest in this topic I thought it might be useful to turn the talk into a series of posts. Over the years, the problem of encrypted search has become an important problem in security and cryptography.

Read more

A Note on Crypto Design vs Crypto Engineering

In my previous post, I described a cryptographic protocol that could allow a telecommunications company to keep its data, and the NSA to legally access it (i.e., with authorization from a FISA court) without revealing its queries. In response to the post, a few people have asked me whether the protocol was implemented and, if not, where they could get implementations of the underlying components. My response is that I did not implement it but, for what it’s worth, I added a section to the blog with links to implementations of various cryptographic primitives and protocols (here).

Read more

Are Compliance and Privacy Always at Odds?

Chris Soghoian points to an interesting article in the Wall Street Journal. It describes mounting pressure on the NSA to re-design its phone-data program—the program under which it compels telecommunications companies (telcos) like Verizon to turn over their phone record data. In the article, Timothy Edgar, a former privacy lawyer who served in the Bush and Obama administrations is quoted as saying: Privacy technology under development would allow for anonymous searches of databases, keeping data out of government hands but also preventing phone companies from learning the purpose of NSA searches.

Read more

Applying Fully Homomorphic Encryption (Part 2)

This is the second part of a series on applying fully-homomorphic encryption. In the first post we went over what fully-homomorphic encryption (FHE) and shomewhat-homomorphic encryption (SHE) were and how they relate. In this post we’ ll discuss actual applications. To structure the discussion, I’ ll refer to some applications as direct and others as indirect. Indirect applications will refer to applications where FHE is used as a building block—usually with other components—to construct something else of interest.

Read more