One Server for the Price of Two: Simple and Fast Single-Server Private Information Retrieval

We present SimplePIR, the fastest single-server private information retrieval scheme known to date. Sim-plePIR's security holds under the learning-with-errors assumption. To answer a client's query, the SimplePIR server performs fewer than one 32-bit multiplication and one 32-bit addition per database byte. SimplePIR achieves 10 GB/s/core server throughput, which approaches the memory bandwidth of the machine and the performance of the fastest two-server privateinformation-retrieval schemes (which require non-colluding servers). SimplePIR has relatively large communication costs: to make queries to a 1 GB database, the client must download a 121 MB "hint" about the database contents; thereafter, the client may make an unbounded number of queries, each requiring 242 KB of communication. We present a second single-server scheme, DoublePIR, that shrinks the hint to 16 MB at the cost of slightly higher per-query communication (345 KB) and slightly lower throughput (7.4 GB/s/core). Finally, we apply our new private-information-retrieval schemes, together with a novel data structure for approximate set membership, to the task of private auditing in Certificate Transparency. We achieve a strictly stronger notion of privacy than Google Chrome's current approach with modest communication overheads: 16 MB of download per month, along with 150 bytes per TLS connection. Application to Certificate Transparency. Finally, we evaluate our PIR schemes in the context of the application of signed certificate timestamp (SCT) auditing in Certificate Transparency. In this auditing application, a server holds a set 𝑆 of strings and a client (web browser) wants to test whether a particular string 𝜎, representing an SCT, appears in the set 𝑆, while hiding 𝜎 from the server. (The string 𝜎 reveals information about which websites a client has visited.) Google Chrome currently implements this auditing step using a solution that provides 𝑘-anonymity for 𝑘 = 1000 [35] . Along the way, we construct a new data structure (Section 6) for more efficiently solving this type of private set-membership problem using PIR, when a constant rate of false positives is acceptable (as in our application). In this setting, standard Bloom filters [15] and approaches based on PIR by keywords [26] require the client to perform PIR over a database of 𝜆𝑁 bits (if the set 𝑆 has size 𝑁 and 𝜆 ≈ 128 is a security parameter). In contrast, our data structure requires performing PIR over only 8𝑁 bits-giving a roughly 16× speedup in our application. Google's current solution to SCT auditing, which provides 𝑘-anonymity rather than full cryptographic privacy, requires the client to communicate 24 B on average per TLS connection. Our solution, which provides cryptographic privacy, requires 150 B and 0.0003 core-seconds of server compute on average per TLS connection, along with 16 MB of client download and 150 KB of client storage every month to maintain the hint. Limitations. Our new PIR schemes come with two main downsides. First, our client must download a "hint": on databases gigabytes in size, the hint is tens of megabytes. If a client makes only one query, this hint download dominates the overall communication. Second, our schemes' online communication is on the order of hundreds of kilobytes, which is 10× larger than in some prior work. Nevertheless, we believe that SimplePIR and DoublePIR represent an exciting new point in the PIR design space: large computation savings, along with a conceptually simple design and small, stand-alone codebase, at the cost of modest communication and storage overheads. Our contributions. In summary, our contributions are: • two new high-throughput single-server private information retrieval protocols (Sections 4 and 5), • a new data structure for private set membership using PIR (Section 6) and its application to private auditing in Certificate Transparency (Section 7), and • the evaluation of these schemes, using a new open-source implementation (Section 8). Related work and comparison Chor, Goldreich, Kushilevitz and Sudan [27] introduced PIR in the multi-server setting and Kushilevitz and Ostrovsky [62] gave the first construction of single-server PIR. Their scheme uses a linearly homomorphic encryption scheme that expands