Arthur K. Lazzaretti

reach me at:

arthur(dot)lazzaretti(at)yale(dot)edu

I’m a PhD student working in cryptography at the Yale Applied Cryptography Lab (YACL), advised by Dr. Charalampos Papamanthou. My research efforts are mainly focused in improving Private Information Retrieval (PIR) algorithms.

The end goal is to have an affordable private search over large databases. This would be extremely useful both to perform lightweight private operations in a decentralized setting, would allow for affordable privacy guarantees in the internet, and would improve many other Privacy Enhancing Technologies which PIR is used as a blackbox for.

Other topics in cryptography that interest me include secure aggregation, differential privacy, secure multiparty computation and homomorphic encryption.

news

Sep 01, 2021	Started my PhD at Yale!
May 02, 2021	Graduated from my M.Sc. in Computer Science at Georgia Tech!

selected publications

2025

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

Single Pass Client-Preprocessing Private Information Retrieval

Arthur Lazzaretti, and Charalampos Papamanthou

In 33rd USENIX Security Symposium (USENIX Security 24), Aug 2024
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.

2023

Near-Optimal Private Information Retrieval with Preprocessing

Arthur Lazzaretti, and Charalampos Papamanthou

In Theory of Cryptography, Oct 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).
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.