CS 2950-v: Topics in Applied Cryptography (Fall '16): Encrypted Search

Meeting Time: TTh 10:30-11:50

Location: CIT 316

Instructor: Seny Kamara (seny@brown.edu)

Office hours: Thursdays 1-3PM, CIT 507

Grad TA: Evgenios Kornaropoulos (evgenios_kornaropoulos@brown.edu). Office Hours: Wed 2-4, CIT 411

Undergrad TA: William Barclay (william_barclay@brown.edu)

Description: This course surveys recent developments in applied cryptography. Research in this field is motivated by privacy and security issues that arise in practice from areas like cloud computing, databases, surveillance and finance. Topics will vary each year.

Prerequisites: CSCI 1660 required; CSCI 1510 strongly recommended.

Syllabus: pdf


This fall, we will study the problem of encrypted search; that is, how can we search on encrypted data? In particular, we will be interested in how encrypted search techniques can be used to design encrypted databases.

As the technologies we deploy produce and consume an increasing amount of data, we are witnessing several conflicting trends. On one hand, these massive datasets are becoming more intrusive and privacy-sensitive and on the other they are becoming harder to secure. The latter is well-illustrated by the prevalence of data breaches and by the recent Snowden disclosures. Unfortunately, the standard tools at our disposal for enforcing data privacy and security, like encryption, eliminate the utility of many critical technologies such as databases, cloud computing, cloud storage, machine learning and data analytics. The area of encrypted search aims to solve this dilemma and reconcile these trends by producing a new generation of cryptographic primitives and systems that can secure data without eliminating its utility.

Though the course is motivated by practical/applied problems, some of the works we will study are theoretical in nature. While previous exposure to the foundations of cryptography (including, e.g., provable security, the simulation paradigm, reductions) will be helpful, we will cover the necessary theory in class.

Course Materials

There is no textbook required for this course but students may find Introduction to Modern Cryptography by Katz and Lindell helpful to gain familiarity with cryptography. Other recommended (free) resources include Introduction to Modern Cryptography by Bellare and Rogaway and A Course in Cryptography by Pass and Shelat.

Schedule (tentative)

Lecture Date Topic Notes Reading
1 Th 09/08 Motivation and overview pdf [Rog'15]
2 Tu 09/13 Introduction to provable security pdf [Dam'07]
3 Th 09/15 Introduction to provable security (part 2)
4 Tu 09/20 (In)Security of encrypted search pdf [CGKO'06]
5 Th 09/22 (In)Security of encrypted search (part 2)
6 Tu 09/27 Oblivious RAMs (ORAM) pdf
7 Th 09/29 ORAM-based Search [Nav'15]
8 Tu 10/04 Property Preserving Encryption (PPE) [BBO'06, BCLO'09]
9 Th 10/06 PPE-based EDBs and Attacks [PRZB'11, NKW'15]
Optional:[BBC'16, GSBNT'16]
10 Tu 10/11 Searchable Symmetric Encryption (SSE) [CJJJKRS'14]
11 Th 10/13 Attacks on SSE [IKK'12,GPCR'15]
12 Tu 10/18 Dynamic SSE and Injection Attacks [ZKP'16]
13 Th 10/20 Guest Speakers: Charles Wright and David Pouliot
14 Tu 10/25 Forward Security [Bost'16]
Optional: [SPS'14]
15 Th 10/27 Boolean SSE [CJJKRS'13]
Optional: [PKV+'14]
16 Tu 11/01 Boolean SSE [KM'16a] (by email)
17 Th 11/03 Work in progress
18 Tu 11/08 Relational DBs [KM'16b]
19 Th 11/10 Private information retrieval
20 Tu 11/15 Private bulk collection
21 Th 11/17 Guest speaker: David Cash
22 Tu 11/22 Big Companies
23 Th 11/24 Thanksgiving
24 Tu 11/29 Startups
25 Th 12/01 Evgenios; Luke; Archita and Megumi
26 Tu 12/06 Leah; Martin; Di
27 Th 12/08 Ghous; Joe and Sam