Encrypting Distributed Databases with Provable Security

by Archita Agarwal As people worldwide continue to generate massive amounts of data, distributed storage systems or distributed databases have become a necessity. Much of this data is sensitive, and it’s been the subject of breaches (Facebook in 2019, Marriott in 2018) that have affected hundreds of millions of users. Encryption is often proposed as a security solution, but when misapplied, it can lead to systems that fail to provide satisfactory privacy guarantees.

Clusion v0.2.0

by Seny Kamara and Tarik Moataz Over the last two years, we have been working on an open source encrypted search library called Clusion. We are using it in several ESL projects, including the Signal Search project we recently released. We are also excited that other groups are experimenting with it. In this post, we wanted to give an overview of Clusion and answer some of the most frequently asked questions we have received about it.

Signal Search

by Joe Engelman, Seny Kamara, Tarik Moataz and Sam Zhao. Overview Signal is an end-to-end encrypted messaging app made by Open Whisper Systems. It is based on the Signal protocol which was designed by Trevor Perrin and Moxie Marlinspike. In addition to underlying the Signal App, the Signal protocol is also used by WhatsApp, Facebook Messenger and Google Allo. Why is Signal important? Together with PGP-encrypted email and OTR-based messaging, the Signal App is one of the most secure ways to communicate.

Graph Encryption: Going Beyond Encrypted Keyword Search

This is a guest post by Xianrui Meng from Boston University about a paper he presented at CCS 2015, written in collaboration with Kobbi Nissim, George Kollios and myself. Note that Xianrui is on the job market. Encrypted search has attracted a lot of attention from practitioners and researchers in academia and industry. In previous posts, Seny already described different ways one can search on encrypted data. Here, I would like to discuss search on encrypted graph databases which are gaining a lot of popularity.

Attacking Encrypted Database Systems

Muhammad Naveed, Charles Wright and I recently posted a paper that describes inference attacks on encrypted database (EDB) systems like CryptDB, Cipherbase, Google's Encrypted BigQuery demo and Microsoft SQL Server 2016 Always Encrypted. These systems are based on property-preserving encryption (PPE) schemes which are a class of encryptions schemes that leak certain properties of their plaintexts. Examples include deterministic encryption (DTE) and order-preserving encryption (OPE). The paper is here and will be presented in October at the ACM Conference on Computer and Communication Security.

Workshop on Encryption for Secure Search and Other Algorithms

I just got back from the Workshop on Encryption for Secure Search and other Algorithms (ESSA) which was held in Bertinoro, Italy, and was organized by Sasha Boldyreva and Bogdan Warinschi. It was a great event and I'd like to thank the organizers for putting this together and doing such a great job. It was really nice to see all the excitement and enthusiasm behind this topic; both from the research community and from industry.

Applied Crypto Highlights: Searchable Encryption with Ranked Results

This is the second in a series of guest posts highlighting new research in applied cryptography. This post is written by Foteini Baldimtsi who is a postdoc at Boston University and Olya Ohrimenko who is a postdoc at Microsoft Research. Note that Olya is on the job market this year. Modern cloud services let their users outsource data as well as request computations on it. Due to potentially sensitive content of users' data and distrust in cloud services, it is natural for users to outsource their data encrypted.

Applied Crypto Highlights: Restricted Oblivious RAMs and Hidden Volume Encryption

This is the first in a series of guest posts highlighting new research in applied cryptography. This post is written by Travis Mayberry from Northeastern University. Note that Travis is graduating this year and will be on the job market. ORAM Background Oblivious RAM is a very hot research topic right now. As Seny has written about here, it can be used to perform searches over outsourced encrypted data while maintaining the highest possible levels of security against a malicious storage provider.

Thoughts on Applied Cryptography Research

If you follow me on Twitter you have no doubt heard my occasional outbursts and rants on what I perceive to be biases in the current publication model in cryptography. In short, I think that top cryptography conferences are heavily biased against certain areas of cryptography and for others. Some of the areas that I think have a much harder time getting into top-tier crypto conferences include Applied Cryptography. I don' t think this is particularly controversial and, from what I hear, CRYPTO has even tried to rectify this recently (e.

Workshop on Surveillance and Technology

This is an announcement for a workshop that I am organizing in conjunction with the Privacy Enhancing Technologies Symposium (PETS). Due to the Snowden disclosures, mass surveillance has become one of the most highly-discussed and controversial issues in politics, policy, technology and international affairs. Modern surveillance, however, relies heavily on technology and, therefore, our community has a unique role to play in not only understanding surveillance but in mitigating it when excessive and restraining/limiting it when appropriate.

Microsoft Research Internships

One of the best things about working at MSR is the internship program. For a sense of what an MSR internship is like, I recommend this essay by Philip Guo. In this post, I want to personally reflect on the MSR internship program and provide some context about how things have worked for me in the past. Let me stress that this reflects only my personal experience and may not be representative of other MSR researchers' experiences.

How Not to Learn Cryptography

People often ask me how to get started in cryptography. What's interesting is that most of the time they also want to know how I personally got started. This is interesting to me because it suggests that people are looking for more than a list of books or papers to read or set of exercises to solve; they're really looking for a broader strategy on how to learn the subject. In this post I'll discuss some possible strategies.

Microsoft Research SVC and Applied Theory

Most people have heard by now about the closing of the Microsoft Research Silicon Valley Campus (SVC) Lab. It definitely came as a shock to everyone (including other MSR researchers) and many people have commented online about what the lab meant to them and about all the great research that came out of it. There is something else about MSR SVC, however, that I have always appreciated besides it's great contributions in distributed systems and privacy.

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

This is the fifth part of a series on searching on encrypted data. 1, 2, 3, 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.

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.

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.

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, 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.

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, 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.

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, 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.

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, 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.

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.

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.

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.

Applying Fully Homomorphic Encryption (Part 1)

This is the first part of a series on applying fully-homomorphic encryption (FHE). In this post we describe fully-homomorphic and somewhat-homomorphic encryption and the second post we see some applications In 2009, Craig Gentry published a paper showing---for the first time---how to construct a fully-homomorphic encryption (FHE) scheme. This was a landmark event in cryptographic research that will eventually have huge practical implications for security and privacy. An often cited (especially by the press) application of FHE is cloud computing.

Cloud Adversarial Models

Last April I attended a workshop organized by the NSF on cloud security (see here for an overview from the Computing Community Consortium blog). The goal was to get a few people to think about the most interesting and important future research directions in cloud security. The attendees came from a wide range of backgrounds: operating systems, networking, computer architecture, security and cryptography. It was really interesting to see how people from different communities think about and approach the same issues.

A Key to the Cloud

At this point most people would agree that cloud computing represents a major shift in computing. Consider, for example, that many tech companies are entirely cloud-based. This includes the more established like Netflix and startups like Instagram and Pinterest. Instead of building and maintaining their own computing infrastructure, they can scale on-demand, save money and focus on improving their services. Scientists and engineers whose research was limited by the computing resources they had at their disposal (usually whatever their departments could afford) can now use the cloud to process huge amounts of data and run large-scale simulations cheaply 1.