Streaming, Plaintext Private Information Retrieval Using Regular Expressions on Arbitrary Length Search Strings

摘要

Submitting a query to a plaintext stream can compromise search privacy, revealing the interests and motivations of the submitting party to the data owner. Current research in Private Information Retrieval (PIR) provides computationally private solutions based on partially-homomorphic encryption. These enable Alice to search Bob's data without revealing Alice's search criteria, sacrifice bandwidth (she doesn't have to tap the entire stream), or deploy a trusted device in Bob's domain. Building on two fixed-string retrieval techniques in [3] and [15], we developed a novel private pattern matching method that searches freeform, arbitrary length strings in streaming plaintext and retrieves corresponding elements. We present our design that encodes regular expressions into private queries, uses an obfuscation method to limit frequency and graph quotient attacks by Bob, and we provide experimental evidence to verify the feasibility of the approach. Our pattern matching technique extends the range of applications for plaintext PIR.