publications

2025

1. 

   Robust Double Auctions for Resource Allocation

   Arthur Lazzaretti, Charalampos Papamanthou, and Ismael Hishon-Rezaizadeh

   In (to appear) FC’25, Apr 2025

2. 

   Permissionless Verifiable Information Dispersal (Data Availability for Bitcoin Rollups)

   Ben Fisch, Arthur Lazzaretti, Zeyu Liu, and Lei Yang

   In (to appear) IEEE S&P (Oakland) ’25, May 2025

2024

1. 

   Single Pass Client-Preprocessing Private Information Retrieval

   Arthur Lazzaretti, and Charalampos Papamanthou

   In 33rd USENIX Security Symposium (USENIX Security 24), Aug 2024

2. 

   ThorPIR: Single Server PIR via Homomorphic Thorp Shuffles

   Ben Fisch, Arthur Lazzaretti, Zeyu Liu, and Charalampos Papamanthou

   In Proceedings of the 2024 on ACM SIGSAC Conference on Computer and Communications Security, Salt Lake City, UT, USA, Oct 2024

   Abs DOI

   Private Information Retrieval (PIR) is a two player protocol where the client, given some query x ε [N], interacts with the server, which holds a N-bit string DB, in order to privately retrieve DB[x]. In this work, we focus on the single-server client-preprocessing model, initially proposed by Corrigan-Gibbs and Kogan (EUROCRYPT 2020), where the client and server first run a joint preprocessing algorithm, after which the client can retrieve elements from DB privately in time sublinear in N. Most known constructions of single-server client-preprocessing PIR follow one of two paradigms: They feature either (1) a linear-bandwidth offline phase where the client downloads the whole database from the server, or (2) a sublinear-bandwidth offline phase where however the server has to compute a large-depth (Ωλ(N)) circuit under fully-homomorphic encryption (FHE) in order to execute the preprocessing phase.In this paper, we propose ThorPIR, a single-server client preprocessing PIR scheme which achieves both sublinear offline bandwidth (asymptotically and concretely) and a low-depth, highly parallelizable preprocessing circuit. Our main insight is to use and significantly optimize the concrete circuit-depth of a much more efficient shuffling technique needed during preprocessing, called Thorp shuffle. A Thorp shuffle satisfies a weaker security property (e.g., compared to an AES permutation) which is ”just enough” for our construction. We estimate that with a powerful server (e.g., hundreds of thousands of GPUs), ThorPIR’s end-to-end preprocessing time is faster than any prior work. Additionally, compared to prior FHE-based works with sublinear bandwidth, our construction is at least around 10,000 times faster.

3. 

   Multi-Server Doubly Efficient PIR

   Arthur Lazzaretti, Zeyu Liu, Ben Fisch, and Charalampos Papamanthou

   Jun 2024

2023

1. 

   Near-Optimal Private Information Retrieval with Preprocessing

   Arthur Lazzaretti, and Charalampos Papamanthou

   In Theory of Cryptography, Jun 2023

   Abs

   In Private Information Retrieval (PIR), a client wishes to access an index i from a public n-bit database without revealing any information about i. Recently, a series of works starting with the seminal paper of Corrigan-Gibbs and Kogan (EUROCRYPT 2020) considered PIR with client preprocessing and no additional server storage. In this setting, we now have protocols that achieve }}\backslashwidetilde{O}(\backslashsqrt{n})}}O~(n)(amortized) server time and }}\backslashwidetilde{O}(1)}}O~(1)(amortized) bandwidth in the two-server model (Shi et al., CRYPTO 2021) as well as }}\backslashwidetilde{O}(\backslashsqrt{n})}}O~(n)server time and }}\backslashwidetilde{O}(\backslashsqrt{n})}}O~(n)bandwidth in the single-server model (Corrigan-Gibbs et al., EUROCRYPT 2022). Given existing lower bounds, a single-server PIR scheme with }}\backslashwidetilde{O}(\backslashsqrt{n})}}O~(n)(amortized) server time and }}\backslashwidetilde{O}(1)}}O~(1)(amortized) bandwidth is still feasible, however, to date, no known protocol achieves such complexities. In this paper we fill this gap by constructing the first single-server PIR scheme with }}\backslashwidetilde{O}(\backslashsqrt{n})}}O~(n)(amortized) server time and }}\backslashwidetilde{O}(1)}}O~(1)(amortized) bandwidth. Our scheme achieves near-optimal (optimal up to polylogarithmic factors) asymptotics in every relevant dimension. Central to our approach is a new cryptographic primitive that we call an adaptable pseudorandom set: With an adaptable pseudorandom set, one can represent a large pseudorandom set with a succinct fixed-size key k, and can both add to and remove from the set a constant number of elements by manipulating the key k, while maintaining its concise description as well as its pseudorandomness (under a certain security definition).

2. 

   TreePIR: Sublinear-Time and Polylog-Bandwidth Private Information Retrieval from DDH

   Arthur Lazzaretti, and Charalampos Papamanthou

   In Advances in Cryptology – CRYPTO 2023: 43rd Annual International Cryptology Conference, CRYPTO 2023, Santa Barbara, CA, USA, August 20–24, 2023, Proceedings, Part II, Aug 2023

   Abs DOI

   In Private Information Retrieval (PIR), a client wishes to retrieve the value of an index i from a public database of N values without leaking any information about i. In their recent seminal work, Corrigan-Gibbs and Kogan (EUROCRYPT 2020) introduced the first two-server PIR protocol with sublinear amortized server time and sublinear O(NlogN) bandwidth. In a followup work, Shi et al. (CRYPTO 2021) reduced the bandwidth to polylogarithmic by proposing a construction based on privately puncturable pseudorandom functions, a primitive whose only construction known to date is based on heavy cryptographic primitives such as LWE. Partly because of this, their PIR protocol does not achieve concrete efficiency. In this paper we propose TreePIR, a two-server PIR protocol with sublinear amortized server time and polylogarithmic bandwidth whose security can be based on just the DDH assumption. TreePIR can be partitioned in two phases that are both sublinear: The first phase is remarkably simple and only requires pseudorandom generators. The second phase is a single-server PIR protocol on onlyN indices, for which we can use the protocol by Döttling et al. (CRYPTO 2019) based on DDH, or, for practical purposes, the most concretely efficient single-server PIR protocol. Not only does TreePIR achieve better asymptotics than previous approaches while resting on weaker cryptographic assumptions, it also outperforms existing two-server PIR protocols in practice. The crux of our protocol is a new cryptographic primitive that we call weak privately puncturable pseudorandom functions, which we believe can have further applications.