Private Blocklist Lookups with Checklist

This paper presents Checklist, a system for private blocklist lookups. In Checklist, a client can determine whether a particular string appears on a server-held blocklist of strings, without leaking its string to the server. Checklist is the first blocklist-lookup system that (1) leaks no information about the client's string to the server, (2) does not require the client to store the blocklist in its entirety, and (3) allows the server to respond to the client's query in time sublinear in the blocklist size. To make this possible, we construct a new two-server private-information-retrieval protocol that is both asymptotically and concretely faster, in terms of server-side time, than those of prior work. We evaluate Checklist in the context of Google's "Safe Browsing" blocklist, which all major browsers use to prevent web clients from visiting malware-hosting URLs. Today, lookups to this blocklist leak partial hashes of a subset of clients' visited URLs to Google's servers. We have modified Firefox to perform Safe-Browsing blocklist lookups via Checklist servers, which eliminates the leakage of partial URL hashes from the Firefox client to the blocklist servers. This privacy gain comes at the cost of increasing communication by a factor of 3.3×, and the server-side compute costs by 9.8×. Checklist reduces end-to-end server-side costs by 6.7×, compared to what would be possible with prior state-of-the-art two-server private information retrieval. in a blocklist of 𝑛 entries, the amortized server-side cost is 𝑂 ( √ 𝑛) work per query. Concretely, a server can answer client queries to the three-million-entry Safe Browsing blocklist in under half a core-millisecond per query on average. Our new PIR scheme reduces the server-side compute costs by 6.7×, compared with a private-blocklist scheme based on existing PIR protocols. To our knowledge, Checklist is the first blocklist-lookup system that (1) leaks no information about the client's string to the server, (2) does not require the client to store the blocklist in its entirety, and (3) achieves per-query server-side computation that is sublinear in the blocklist size. At the heart of Checklist is a new "offline/online" privateinformation-retrieval scheme [12, 27, 71] . These schemes use client-specific preprocessing in an offline phase to reduce the computation required at query (online) time. On a blocklist with 𝑛 entries and with security parameter 𝜆 ≈ 128, our scheme requires the servers to perform work 𝑂 ( √ 𝑛) per query, on average. This improves the 𝑂 (𝜆 √ 𝑛) per-query cost of schemes from prior work [27] and amounts to a roughly 128fold concrete speedup. In addition, prior offline/online schemes do not perform well when the blocklist/database changes often (since even a single-entry change to the blocklist requires rerunning the preprocessing step). By carefully structuring the blocklist into a cascade of smaller blocklists, we demonstrate that it is possible to reap the benefits of these fast offline/online private-information-retrieval schemes even when the blocklist contents change often. In particular, in a blocklist of 𝑛 entries, our scheme requires server-side computation 𝑂 (log 𝑛) per blocklist update per client, whereas a straightforward use of offline/online private-information-retrieval schemes would yield Ω(𝑛) time per update per client.