Stanford Security Lunch
Fall 2016

Get announcements:

September 28, 2016 Splinter: Practical Private Queries on Public Data

Speaker:  Matei Zaharia

Abstract:  Many online services let users query public datasets such as maps, flight prices, or restaurant reviews. Unfortunately, the queries to these services reveal highly sensitive information that can compromise users' privacy. We present Splinter, a system to protect users' queries on public data that can scale to realistic applications. A user splits her query into multiple parts and sends each part to a different provider that holds a copy of the data. As long as any one of the providers is honest and does not collude with the others, the providers cannot determine the query. Splinter uses and extends a cryptographic primitive called Function Secret Sharing (FSS) that makes it significantly more efficient than prior systems based on Private Information Retrieval and garbled circuits. We develop protocols that extend FSS to new types of queries, such as maximum and top-K queries, as well as an optimized implementation of FSS using AES-NI instructions and multicores. Splinter achieves latencies below 1.2 seconds for realistic workloads including a Yelp clone, flight search, and map routing.

Note:  Since this is our first meeting of the quarter, we will have a three-minute organizational meeting before the talk begins.

October 5, 2016 Moved to Law School

Note:  Henry Corrigan-Gibbs is giving a lunch-time talk at the law school on October 5 at 12:45pm, so we are moving Security Lunch to the law school for the week. Lunch will be served at the talk—please register below.

RSVP using:  this link

October 12, 2016 Order-Revealing Encryption: New Constructions, Applications, and Lower Bounds

Speaker:  David Wu

Abstract:  In the last few years, there has been significant interest in developing methods to search over encrypted data. In the case of range queries, a simple solution is to encrypt the contents of the database using an order-preserving encryption (OPE) or order-revealing encryption (ORE) scheme (i.e., an encryption scheme that enables comparisons on encrypted values). While these encryption schemes have the advantage of being legacy-friendly (i.e., easy to integrate with existing database management systems), a recent line of work beginning with Naveed et al. (CCS 2015) showed that these legacy-friendly solutions are extremely vulnerable to “inference attacks.” Naveed et al. (and subsequently, Durak et al. (CCS 2016) as well as Grubbs et al.) show that an attacker who just obtains a static dump (e.g., offline access) to a database encrypted under an OPE/ORE scheme can actually recover nearly all of the data contained in the database.

In this work, we introduce a new paradigm for constructing order-revealing encryption that can be used to achieve stronger security in the offline setting. When using our new ORE candidate to perform range queries over an encrypted database, the ciphertexts in the database provide semantic security, and thus, provably reveal no information about the underlying contents. In this way, our new ORE scheme is the first practically-viable scheme that is robust against all offline inference attacks. In the online setting, we show that our ORE scheme is more secure than existing (stateless and non-interactive) OPE and ORE schemes which are practical. All of our constructions rely only on symmetric primitives (e.g., AES). Finally, we give a full implementation of our new ORE scheme, and show that not only is our scheme more secure than existing OPE schemes (the current standard that has been deployed in several industry applications), it is also faster: encrypting a 32-bit integer requires just 55 microseconds, which is more than 65 times faster than existing OPE schemes.

Joint work with:  Kevin Lewi

To appear at:  CCS 2016

October 19, 2016 Blind Seer — Using Bloom filter trees for Searchable Encryption

Speaker:  Ben Fisch

Abstract:  Blind Seer is a system that supports private querying of an outsourced encrypted database. In contrast to standard searchable symmetric encryption (SSE) schemes, the goal of Blind Seer is to protect both the privacy of a client’s queries and the database itself. In particular, it provides the ability to enforce authorization policies on client queries while maintaining the privacy of both the queries and the policies. Blind Seer’s main achievements are its rich query functionality (arbitrary boolean formulas) and efficiency. On a 100M-record census database with roughly 7B indexed keywords, test queries on Blind Seer completed within 3x of a MySQL baseline. The system is provably secure (for a semi-honest server and malicious client) up to limited leakage in the form of data access patterns, which could be prevented with more expensive techniques like ORAM. An important open line of work is understanding the impact of this leakage.

In this talk we will discuss Blind Seer's core data structure, an encrypted Bloom filter tree that indexes database keywords. In Blind Seer, client queries are evaluated through an interactive search in the Bloom filter tree using Yao’s garbled circuits to maintain privacy. The communication and computation required for the garbled circuits is a major bottleneck in Blind Seer’s performance. We show how Bloom filter trees can be used in the SSE setting without any need for garbled circuits. Furthermore, we can achieve security against a malicious server. This is a work in progress and its performance will be measured against existing SSE schemes that support boolean (conjunctive/disjunctive) queries.

October 26, 2016 Privately Finding Common Friends of Friends in Social Networks

Speaker:  Yan Michalevsky

Abstract:  We present solutions to a fundamental problem affecting distributed social networks where every user knows his direct friends, but knows nothing about his friends of friends. Since the social graph is distributed, how can the system recommend that a user befriend a common friend of friends? Concretely, suppose three of Alice’s friends are friends with some user Charlie. A centralized social network would suggest to Alice that she might also want to befriend Charlie. We show that the same can be done with a distributed social graph and without leaking any other information about friend relations.

We cast the problem as a secure multi-party computation with a strict communication pattern. We first show that when the common friends threshold is two — that is, Alice should be told about Charlie if Charlie is friends with two of her friends — the problem can be solved efficiently using a direct secret sharing mechanism. When the threshold is three or greater, solving this problem without leaking additional information is much harder. We introduce two notions of security offering different levels of privacy. For the weaker notion, we propose three algorithms with different performance characteristics by exploiting the fact that Reed-Solomon codewords also have secret sharing properties. We experiment with these algorithms and show that they can be used successfully even when all users have hundreds of direct friends. For the stronger security notion, we describe a solution based on decentralized attribute-based encryption.

November 2, 2016 Cancelled due to Law School Event

November 9, 2016 TBA

Speaker:  Sergio Benitez

Abstract:  TBA

November 16, 2016 TBA

Speaker:  Fraser Brown

Abstract:  TBA

November 24, 2016 Thanksgiving Week

November 30, 2016 Deploying TLS 1.3

Speaker:  Nick Sullivan (CloudFlare)

Abstract:  A deep dive into the design and implementation of the latest version of the transport layer security protocol.

December 7, 2016 TBA

Speaker:  Todd Warszawski

Abstract:  TBA

December 14, 2016 TBA

Speaker:  Riad Wahby

Abstract:  TBA