Bloom Swizzlers for Efficient Keyword-based Private Information Retrieval
Date
2024-10-15
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Private Information Retrieval (PIR) is a cryptographic primitive that allows clients to fetch information from remote databases without revealing anything about which information they are fetching to the database operators. While PIR can solve numerous privacy problems arising in our increasingly electronic society, it is a decidedly heavyweight tool whose prohibitively high latency and low throughput, coupled with its lack of expressiveness, makes it challenging to apply in real-world applications. Consequently, despite significant attention from the research community, in-the-wild deployments of PIR to date have been few and far between. This dissertation takes an important step toward making PIR more agile by introducing a novel data structure called the Bloom Swizzler. In the three decades since Chor, Goldreich, Kushilevitz, and Sudan's seminal paper on PIR (FOCS 1995), dozens of PIR constructions, proven secure under nearly as many cryptographic assumptions, have appeared in the literature. Despite the sheer number of constructions, almost all known PIR designs share a common trait: clients query for items by specifying those items' physical offsets within the database. Such a tight coupling between query construction and the underlying database's physical layout makes such PIR cumbersome for privacy practitioners and developers to use safely and correctly. Bloom Swizzlers address this by acting upon (i.e., "swizzling") clients' queries before passing them to some underlying PIR protocol, endowing almost any of the most performant PIR schemes from the literature with an efficient and intuitive key-value store interface. To accomplish this, Bloom Swizzlers synthesize ideas from two seemingly disparate constructs: Bloom Filters and Swizzlers. A Bloom Filter is a compact, probabilistic data structure that permits constant-time probable-set-membership inquiries; meanwhile, Swizzlers are a class of unary operators (represented as special 0/1-matrices) that transform vectors by rearranging, duplicating, and discarding their components. By acting as a layer of indirection between the querier and the database, Bloom Swizzlers enables a large class of PIR schemes to perform expressive, single-round keyword-based look-ups - or even query for prepared statements consisting of k-way conjunctions for relational data with multi-column keys. Moreover, with some additional effort, Bloom Swizzlers enable disjunctive queries for the value associated with any from a list of keys. Wherever a query yields more than one match, the Bloom Swizzler dictates what result gets returned; for example, one Bloom Swizzler might select a canonical representative to return (using some arbitrary, server-dictated convention) while another might return the sum or count of the matching records. We also present a proof-of-concept implementation of Bloom Swizzlers in Python and report findings from experiments designed to study the performance implications of using Bloom Swizzlers atop state-of-the-art single-server and multi-server PIR schemes.
Description
Keywords
Private Information Retrieval, Bloom Swizzlers, Bloom Filters, Swizzlers, Keyword-based Private Information Retrieval, Privacy Enhancing Technologies
Citation
Pandya, A. M. (2024). Bloom Swizzlers for efficient keyword-based private information retrieval (Master's thesis, University of Calgary, Calgary, Canada). Retrieved from https://prism.ucalgary.ca.