Back to Events

Seminar Series

May 17

Don't be Dense: Efficient Keyword PIR for Sparse Databases

Joon Young Seo
Google

Part Of

4:00P
- 5:00P

Location

RM 32-G882 Hewlett Room
Add to Calendar 2023-05-17 16:00:00 2023-05-17 17:00:00 America/New_York Don't be Dense: Efficient Keyword PIR for Sparse Databases In this paper, we introduce SparsePIR, a single-server keyword private information retrieval (PIR) construction that enables querying over sparse databases. At its core, SparsePIR is based on a novel encoding algorithm that encodes sparse database entries as linear combinations while being compatible with important PIR optimizations including recursion. SparsePIR achieves response overhead that is half of state-of-the art keyword PIR schemes without requiring long term client storage of linear sized mappings. We also introduce two variants, SparsePIRg and SparsePIRc , that further reduces the size of the serving database at the cost of increased encoding time and small additional client storage, respectively. Our frameworks enable performing keyword PIR with, essentially, the same costs as standard PIR. Finally, we also show that SparsePIR may be used to build batch keyword PIR with halved response overhead without any client mappings. RM 32-G882 Hewlett Room

May 11

Authenticated private information retrieval

Simone Colombo
EPFL

Part Of

3:00P
- 4:00P

Location

G-449 Kiva/ Patil
Add to Calendar 2023-05-11 15:00:00 2023-05-11 16:00:00 America/New_York Authenticated private information retrieval Private-information-retrieval (PIR) protocols enable a client to fetch a record from a database while hiding from the server which specific record the client has fetched. Most private-information-retrieval protocols, however, do not ensure data authenticity in the presence of a malicious server.In this talk, we introduce protocols for authenticated private information retrieval. These schemes enable a client to fetch a record from a remote database server such that (a) the server does not learn which record the client has read, and (b) the client either obtains the "authentic" record or detects server misbehavior and safely aborts. Both properties are crucial for many applications. I will present multi-server schemes that protect the security as long as at least one server is honest. Moreover, if the client can obtain a short digest of the database out of band, then our schemes require only a single server. Our authenticated multi-server schemes essentially match the communication and computational complexity of unauthenticated private-information-retrieval schemes, while single-server schemes are 30-100 times more costly than state-of-the-art unauthenticated schemes, though they achieve incomparably stronger integrity properties. I will conclude the talk with a demonstration of Keyd, a PGP public-key directory service that ensures privacy and authenticity.This talk is based on joint work with Kirill Nikitin (Cornell Tech), Henry Corrigan-Gibbs (MIT), David J. Wu (UT Austin), and Bryan Ford (EPFL).Bio:Simone Colombo is a PhD student in the Decentralized Distributed SystemsLaboratory advised by Prof. Bryan Ford at the École polytechnique fédérale de Lausanne (EPFL). His research interests lie at the intersection of computer systems, cryptography, and security. G-449 Kiva/ Patil

May 10

Oblivious Message Retrieval

Zeyu Liu
Yale University

Part Of

4:00P
- 5:00P

Location

32-G449; Kiva Room
Add to Calendar 2023-05-10 16:00:00 2023-05-10 17:00:00 America/New_York Oblivious Message Retrieval Abstract: Anonymous message delivery systems, such as private messaging services and privacy-preserving blockchains, need a mechanism for recipients to retrieve the messages addressed to them, without leaking metadata or letting their messages be linked. Recipients could download all posted messages and scan for those addressed to them, but communication and computation costs are excessive at scale. We show how untrusted servers can detect messages on behalf of recipients, and summarize these into a compact encrypted digest that recipients can easily decrypt. These servers operate obliviously and do not learn anything about which messages are addressed to which recipients. Privacy, soundness, and completeness hold even if everyone but the recipient is adversarial and colluding. Furthermore, the model and constructions generalize to the setting of group messaging or mailing lists: senders can generate messages that would be efficiently detected by multiple recipients of their choice.Our starting point is an asymptotically-efficient approach, using Fully Homomorphic Encryption and homomorphically-encoded Sparse Random Linear Codes. We then address the concrete performance using bespoke tailoring of lattice-based cryptographic components, alongside various algebraic and algorithmic optimizations. This reduces the digest size to a few bits per message scanned. Concretely, the servers’ cost is ~$1 per million messages scanned, and the resulting digests can be decoded by recipients in ~20ms. Our schemes can thus practically attain the strongest form of receiver privacy for current applications such as privacy-preserving cryptocurrencies.We also consider the case of group messaging, where each message may have multiple recipients (e.g., in a group chat or blockchain transaction). We devise new protocols where the servers' cost grows very slowly with the group size, while recipients' cost is low and independent of the group size. 32-G449; Kiva Room

May 03

Zero-Knowledge Middleboxes: Enforcing Network Policy without Sacrificing Privacy

Zachary DeStefano
New York University (NYU)

Part Of

4:00P
- 5:00P

Location

32-G449 (Kiva)
Add to Calendar 2023-05-03 16:00:00 2023-05-03 17:00:00 America/New_York Zero-Knowledge Middleboxes: Enforcing Network Policy without Sacrificing Privacy Abstract: There is a fundamental conflict between network clients, who want tokeep their traffic private, and administrators, who want to enforce avariety of policies on client traffic, using middleboxes. I'lldescribe a project that resolves this conflict: Zero-KnowledgeMiddleboxes (ZKMB). With ZKMB, clients send middleboxes zero-knowledgeproofs about their encrypted traffic; these proofs reveal nothingabout the underlying plaintext, except that it complies with thepolicy. We show how to make ZKMB work in real-time with unmodifiedencrypted-communication protocols (specifically TLS 1.3), making ZKMBinvisible to servers. Our system gains performance by exploiting thebursty nature of web traffic and by modifying Spartan (CRYPTO '20) toamortize costs. We also show how to efficiently encode DNS filteringand complex DLP policies in zero knowledge in the ZKMB framework.Joint work with Arasu Arun, Joseph Bonneau, Paul Grubbs, MichaelWalfish, Collin Zhang, and Ye Zhang. 32-G449 (Kiva)

April 21

Towards private and accountable online advertising

Ke Zhong
University of Pennsylvania

Part Of

4:00P
- 5:00P

Location

32-G449, Kiva Room
Add to Calendar 2023-04-21 16:00:00 2023-04-21 17:00:00 America/New_York Towards private and accountable online advertising Abstract: Existing online advertising systems are used by billions of users every day. The current systems can be improved with several interesting properties including privacy, accountability, and anti-fraud efforts. I am going to talk about our recent works on improving the ads systems. And specifically, I will present Addax, a fast, verifiable, and private online ad exchange. When a user visits an ad-supported site, Addax runs an auction similar to those of leading exchanges; Addax requests bids, selects the winner, collects payment, and displays the ad to the user. A key distinction is that bids in Addax’s auctions are kept private and the outcome of the auction is publicly verifiable. Addax achieves these properties by adding public verifiability to the affine aggregatable encodings in Prio (NSDI’17) and by building an auction protocol out of them. Our implementation of Addax over WAN with hundreds of bidders can run roughly half the auctions per second as a non-private and non-verifiable exchange, while delivering ads to users in under 600 ms with little additional bandwidth requirements. This efficiency makes Addax the first architecture capable of bringing transparency to this otherwise opaque ecosystem. 32-G449, Kiva Room

April 05

ELSA: Secure Aggregation for Federated Learning with Malicious Actors

Mayank Rathee
UC Berkeley

Part Of

4:00P
- 5:00P

Location

32-G449 (Kiva)
Add to Calendar 2023-04-05 16:00:00 2023-04-05 17:00:00 America/New_York ELSA: Secure Aggregation for Federated Learning with Malicious Actors Federated learning (FL) is an increasingly popular approach for machine learning (ML) when the training dataset is highly distributed. Clients perform local training on their datasets and the updates are then aggregated into the global model. Existing protocols for aggregation are either inefficient or don’t consider the case of malicious actors in the system. This is a major barrier to making FL an ideal solution for privacy-sensitive ML applications.In this talk, I will present ELSA, a secure aggregation protocol for FL that breaks this barrier - it is efficient and addresses the existence of malicious actors (clients + servers) at the core of its design. Similar to prior work Prio and Prio+, ELSA provides a novel secure aggregation protocol built out of distributed trust across two servers that keeps individual client updates private as long as one server is honest, defends against malicious clients, and is efficient end-to-end. Compared to prior works, the distinguishing theme in ELSA is that instead of the servers generating cryptographic correlations interactively, the clients act as untrusted dealers of these correlations without compromising the protocol’s security. This leads to a much faster protocol while also achieving stronger security at that efficiency compared to prior work. We introduce new techniques that retain privacy even when a server is malicious at a small added cost of 7-25% in runtime with a negligible increase in communication over the case of a semi-honest server.ELSA improves end-to-end runtime over prior work with similar security guarantees by big margins - single-aggregator RoFL by up to 305x (for the models we consider), and distributed-trust Prio by up to 8x (with up to 16x faster server-side protocol). Additionally, ELSA can be run in a bandwidth-saver mode for clients who are geographically bandwidth-constrained - an important property that is missing from prior works. Based on joint work with Conghao Shen, Sameer Wagh, and Raluca Ada Popa. 32-G449 (Kiva)

March 15

What can cryptography do for decentralized mechanism design?

Ke Wu
CMU

Part Of

4:00P
- 5:00P

Location

32-G449 (Kiva)
Add to Calendar 2023-03-15 16:00:00 2023-03-15 17:00:00 America/New_York What can cryptography do for decentralized mechanism design? Recent works of Roughgarden (EC’21) and Chung and Shi (SODA’23) initiate the study of a new decentralized mechanism design problem called transaction fee mechanism design (TFM). Unlike the classical mechanism design literature, in the decentralized environment, even the auctioneer (i.e., the miner) can be a strategic player, and it can even collude with a subset of the users facilitated by binding side contracts. Chung and Shi showed two main impossibility results that rule out the existence of a dream TFM. Besides today’s model that does not employ cryptography, we introduce a new MPC-assisted model where the TFM is implemented by a joint multi-party computation (MPC) protocol among the miners. While we show that cryptography allows us to overcome some impossibility results pertaining to the plain model, leading to non-trivial mechanisms with useful guarantees that are otherwise impossible in the plain model, it is not a panacea. We still have a zero-miner revenue limitation. To overcome this impossibility, we introduce a mildly stronger reasonable-world assumption, under which we can design mechanisms that achieve optimal miner revenue. We also systematically explore the mathematical landscape of transaction fee mechanism design under the new MPC-assisted model and demonstrate how the reasonable-world assumptions can alter the feasibility and infeasibility landscape.Based on joint work with Elaine Shi and Hao Chung. 32-G449 (Kiva)

March 10

March 08

A More Complete Analysis of the Signal Double Ratchet Algorithm

Alexander Bienstock
NYU

Part Of

4:00P
- 5:30P

Location

32-G449 Kiva
Add to Calendar 2023-03-08 16:00:00 2023-03-08 17:30:00 America/New_York A More Complete Analysis of the Signal Double Ratchet Algorithm Seminal works by Cohn-Gordon, Cremers, Dowling, Garratt, and Stebila [EuroS&P 2017] and Alwen, Coretti and Dodis [EUROCRYPT 2019] provided the first formal frameworks for studying the widely-used Signal Double Ratchet (DR for short) algorithm.In this work, we develop a new Universally Composable (UC) definition F_DR that we show is provably achieved by the DR protocol. Our definition captures not only the security and correctness guarantees of the DR already identified in the prior state-of-the-art analyses of Cohn-Gordon et al. and Alwen et al., but also more guarantees that are absent from one or both of these works. In particular, we construct six different modified versions of the DR protocol, all of which are insecure according to our definition F_DR, but remain secure according to one (or both) of their definitions. For example, our definition is the first to fully capture CCA-style attacks possible immediately after a compromise — attacks that, as we show, the DR protocol provably resists, but were not fully captured by prior definitions.We additionally show that multiple compromises of a party in a short time interval, which the DR is expected to be able to withstand, as we understand from its whitepaper, nonetheless introduce a new non-trivial (albeit minor) weakness of the DR. Since the definitions in the literature (including our F_DR above) do not capture security against this more nuanced scenario, we define a new stronger definition F_TR that does.Finally, we provide a minimalistic modification to the DR (that we call the Triple Ratchet, or TR for short) and show that the resulting protocol securely realizes the stronger functionality F_TR. Remarkably, the modification incurs no additional communication cost and virtually no additional computational cost. We also show that these techniques can be used to improve communication costs in other scenarios, e.g. practical Updatable Public Key Encryption schemes and the re-randomized TreeKEM protocol of Alwen et al. [CRYPTO 2020] for Secure Group Messaging.Joint work with Jaiden Fairoze, Sanjam Garg, Pratyay Mukherjee, and Srinivasan Raghurama. 32-G449 Kiva

March 01

Adaptive Risk-Limiting Audits

Abigail Harrison
University of Connecticut

Part Of

4:00P
- 5:30P

Location

32-G882
Add to Calendar 2023-03-01 16:00:00 2023-03-01 17:30:00 America/New_York Adaptive Risk-Limiting Audits Risk-limiting audits (RLAs) are rigorous statistical procedures meant to detect invalid election results. RLAs examine paper ballots cast during the election to statistically assess the possibility of a disagreement between the winner determined by the ballots and the winner reported by tabulation. The design of an RLA must balance risk against efficiency: “risk” refers to a bound on the chance that the audit fails to detect such a disagreement when one occurs; “efficiency” refers to the total effort to conduct the audit.The most efficient approaches—when measured in terms of the number of ballots that must be inspected—proceed by “ballot comparison.” However, ballot comparison requires an (untrusted) declaration of the contents of each cast ballot, rather than a simple tabulation of vote totals. This “cast-vote record table” (CVR) is then spot-checked against ballots for consistency. In many practical settings, the cost of generating a suitable CVR dominates the cost of conducting the audit which has prevented widespread adoption of these sample-efficient techniques.We introduce a new RLA procedure: an “adaptive ballot comparison” audit. In this audit, a global CVR is never produced; instead, a three-stage procedure is iterated: 1) a batch is selected, 2) a CVR is produced for that batch, and 3) a ballot within the batch is sampled, inspected by auditors, and compared with the CVR. We prove that such an audit can achieve risk commensurate with standard comparison audits while generating a fraction of the CVR. We present three main contributions: (1) a formal adversarial model for RLAs; (2) definition and analysis of an adaptive audit procedure with rigorous risk limits and an associated correctness analysis accounting for the incidental errors arising in typical audits; and (3) an analysis of efficiency. 32-G882

February 08

A World Wide View of the World Wide Web

Kimberly Ruth
Stanford University

Part Of

4:00P
- 6:00P
Add to Calendar 2023-02-08 16:00:00 2023-02-08 18:00:00 America/New_York A World Wide View of the World Wide Web Despite the pervasiveness of the modern web, we know surprisingly little about how people use it. In this talk, I’ll discuss two recent works aimed at understanding what web browsing looks like today, both appearing at IMC 2022. First, I’ll analyze lists of most popular websites, such as the Alexa Top Million, that are widely used in security and networking research but are not well vetted for accuracy. I’ll show that most top website lists capture web popularity poorly, with the exception of the Chrome User Experience Report dataset. Second, I’ll describe the first large-scale study of how people spend time on the web, using data from Chrome browser telemetry spanning hundreds of millions of users. I’ll explore how traffic is distributed among top websites, where people spend time on the web, and what differences we see in web browsing geographically. Finally, I’ll conclude with recommendations for how the research community can more accurately analyze the web in the future.Join Zoom Meetinghttps://mit.zoom.us/j/97527284254Password: <3securityOne tap mobile+16465588656,,97527284254# US (New York)+16699006833,,97527284254# US (San Jose)Meeting ID: 975 2728 4254US : +1 646 558 8656 or +1 669 900 6833International Numbers: https://mit.zoom.us/u/auBvg4NEVJoin by SIP97527284254@zoomcrc.comJoin by Skype for Businesshttps://mit.zoom.us/skype/97527284254