U.S. flag   An official website of the United States government
Dot gov

Official websites use .gov
A .gov website belongs to an official government organization in the United States.


Secure .gov websites use HTTPS
A lock (Dot gov) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.

Special Topics on Privacy And Public Auditability — Event 3

STPPA Event #3:

Featured topics: private information retrieval (PIR); searchable encryption; fully homomorphic encryption (FHE).

Structure: welcome; three invited talks; panel conversation.

Date, time, location/format: July 06, 2021, 13:30–16:30 EDT @ virtual event over Webex video conference

Attendance: open and free to the public, upon registration

  • 13:30--13:40: STPPA#3 intro
  • 13:40--14:20: Private Information Retrieval with Near-Optimal Online Bandwidth and Time, by Elaine Shi (Carnegie Mellon University)
  • 14:20--15:00: An Overview of Encrypted Databases, by Seny Kamara (Brown University)
  • 15:00--15:10: Break
  • 15:10--15:50: Private AI: Machine Learning on Encrypted Data, by Kristin Lauter (Facebook AI Research)
  • 15:50--16:30: Panel conversation (with the three invited speakers)

List of invited speakers: Seny Kamara (Brown University); Elaine Shi (Carnegie Mellon University); Kristin Lauter (Facebook AI Research).

List of bios (provided by the speakers):

Seny Kamara is an associate professor of computer science at Brown University. His research is in cryptography and is driven by real-world problems from privacy, security and surveillance. He has worked extensively on the design and cryptanalysis of encrypted search algorithms, which are efficient algorithms to search on end-to-end encrypted data.

Elaine Shi is an Associate Professor at Carnegie Mellon University. Her research interests include cryptography, algorithms, distributed systems, foundations of blockchains, and language-based security. She is a recipient of the Packard Fellowship, the Sloan Fellowship, the ONR YIP award, the NSF CAREER award, the NSA Best Scientific Security paper, and various other best-paper and research awards. Elaine obtained her Ph.D. from Carnegie Mellon University.

Dr. Kristin Lauter is currently West Coast Director of Research Science for Facebook AI Research, and Affiliate Professor at the University of Washington.  She was the President of the Association for Women in Mathematics (AWM) from 2015-2017.  She is a Fellow of the American Association for the Advancement of Science (AAAS), Society for Industrial and Applied Mathematics (SIAM), American Mathematical Society (AMS), and the AWM.  She was the Polya Lecturer for the Mathematical Association of America (MAA) from 2018-2020.  She co-won the Selfridge Prize in computational number theory in 2008 and was elected as an honorary member of the Royal Spanish Mathematical Society in 2021.  She co-founded the HomomorphicEncryption.org open standardization community in 2017.  Her team at Microsoft Research built and released SEAL, an open source library for Homomorphic Encryption.

About STPPA: In the "Special Topics on Privacy and Public Auditability" series, the NIST privacy-enhancing cryptography (PEC) project hosts talks on various interconnected topics related to privacy and public auditability. The goal is to convey basic technical background, incite curiosity, suggest research questions and discuss applications, with an emphasis on the role of cryptographic tools.

Selected Presentations
July 6, 2021 Type
1:30 PM STPPA#3 Welcome
Luís T. A. N. Brandão - NIST/Strativia

A few slides to introduce the STPPA #3 event, including the context of the Privacy-Enhancing Cryptography (PEC) project, and the schedule of this particular event with three invited talks and one panel, which will cover the topics of private information retrieval, encrypted search and fully homomorphic encryption.

1:40 PM Private Information Retrieval with Near-Optimal Online Bandwidth and Time
Elaine Shi - Carnegie Mellon University

Abstract: Imagine one or more non-colluding servers each holding a large public database, e.g., the repository of DNS entries. Clients would like to access entries in this database without disclosing their queries to the servers. Classical private information retrieval (PIR) schemes achieve polylogarithmic bandwidth per query, but require the server to perform linear computation per query, which is a deal breaker towards deployment. Several recent works showed, however, that by introducing a one-time, per-client, off-line preprocessing phase, an unbounded number of client queries can be subsequently served with sublinear online computation time per query (and the cost of the preprocessing can be amortized over the unboundedly many queries). Existing preprocessing PIR schemes (supporting unbounded queries), unfortunately, make undesirable tradeoffs to achieve sublinear online computation: they are either significantly non-optimal in online time or bandwidth, or require the servers to store a linear amount of state per client or even per query, or require polylogarithmically many non-colluding servers.

We propose a novel 2-server preprocessing PIR scheme that achieves ~sqrt(n) online computation per query and ~sqrt(n) client storage, while preserving the polylogarithmic online bandwidth of classical PIR schemes. Both the online bandwidth and computation are optimal up to a polylogarithmic factor. In our construction, each server stores only the original database and nothing extra, and each online query is served within a single round trip. Our construction relies on the standard LWE assumption. As an important stepping stone, we propose new, more generalized definitions for a cryptographic object called a Privately Puncturable Pseudorandom Set, and give novel constructions that depart significantly from prior approaches.

Joint work with Waqar Aqeel, Balakrishnan Chandrasekaran and Bruce Maggs. A more recent presentation (Youtube link) appears at Crypto 2021.


2:25 PM Encrypted Search
Seny Kamara - Brown University

Abstract: End-to-end encrypted databases store and process data without ever being able to decrypt it. The widespread availability of practical encrypted databases would greatly improve the security and privacy of our data and would enable a wide array of other privacy-enhancing technologies. In this talk, I will describe the state-of-the-art in encrypted databases in both industry and research.

3:15 PM Private AI: Machine Learning on Encrypted Data
Kristin Lauter - Facebook AI Research

Abstract: As the world adopts Artificial Intelligence, the privacy risks are many. AI can improve our lives, but may leak our private data. Private AI is based on Homomorphic Encryption (HE), a new encryption paradigm which allows the cloud to operate on private data in encrypted form, without ever decrypting it, enabling private training and private prediction. Our 2016 ICML CryptoNets paper showed for the first time that it was possible to evaluate neural nets on homomorphically encrypted data and opened new research directions combining machine learning and cryptography. The security of Homomorphic Encryption is based on hard problems in mathematics involving lattices, a candidate for post-quantum cryptography. This talk will explain Homomorphic Encryption, Private AI, and explain HE in action.

4:10 PM STPPA#3 Panel: PEC for Privacy and Public Auditability
Seny Kamara - Brown University
Kristin Lauter - Facebook AI Research
Elaine Shi - Carnegie Mellon University
Luís T. A. N. Brandão - NIST/Strativia
Angela Robinson - NIST
René Peralta - NIST

Panel conversation with the speakers of the STPPA#3 event.


Event Details

Starts: July 06, 2021 - 01:30 PM EST
Ends: July 06, 2021 - 04:30 PM EST

Format: Virtual Type: Webinar

Attendance Type: Open to public
Audience Type: Industry,Government,Academia,Other


Virtual event via Webex

Parent Project

See: Privacy-Enhancing Cryptography

Related Topics

Security and Privacy: cryptography, privacy

Created April 23, 2021, Updated October 13, 2021