International Association
for Cryptologic Research

We construct somewhat homomorphic encryption from the sparse learning-parities-with-noise problem, along with an assumption that implies linearly homomorphic encryption (e.g., the decisional Diffie-Hellman or decisional composite residuosity assumptions). Our resulting schemes support an a-priori bounded number of homomorphic operations: O(log \lambda/ log log \lambda) multiplications followed by poly(\lambda) additions, where \lambda \in \N is a security parameter. These schemes have compact ciphertexts: before and after homomorphic evaluation, the bit length of each ciphertext is a fixed polynomial in the security parameter \lambda, independent of the number of homomorphic operations that the scheme supports. This gives the first constructions of somewhat homomorphic encryption that can evaluate the class of bounded-degree polynomials without relying on lattice assumptions or bilinear maps. Our new encryption schemes are conceptually simple: much as in Gentry, Sahai, and Waters’ fully homomorphic encryption scheme, ciphertexts in our scheme are matrices, homomorphic addition is matrix addition, and homomorphic multiplication is matrix multiplication. Moreover, when encrypting many messages at once and performing many homomorphic evaluations at once, the bit length of the ciphertexts in (some of) our schemes can be made arbitrarily close to the bit length of the plaintexts. The main limitation of our schemes is that they require a large evaluation key, whose size scales with the complexity of the homomorphic computation performed, though this key can be re-used across any polynomial number of encryptions and evaluations.

Our web search queries reveal sensitive information about us: where we are (“Hikes in Toronto”), how we are feeling (“Causes of neck pain”), what we are doing (“How to find a lawyer”), and much more. Even if we use privacy-conscious search engines, such as DuckDuckGo, the search engine’s servers see our query strings in plaintext. As a result, search engines today accumulate a trove of sensitive data about us; this data is an attractive target for theft in a data breach, abuse by an authoritarian government, or sale to a third party. This talk will present Tiptoe, a search engine that learns nothing about what its users are searching for. With Tiptoe, a client sends only the encryption of its search query to the search engine’s servers. The search engine then executes a cryptographic protocol to identify the web pages that best answer the user’s query—without ever decrypting the query, without learning what the user is searching for, and without learning what search results it is sending back. Tiptoe’s privacy guarantee is based on cryptography alone; it does not require any trusted hardware or non-colluding servers. The Tiptoe search engine answers these queries in the span of seconds: searching over a public web crawl (360 million pages) incurs 57 MiB of client-server communication and 2.7 seconds of client-perceived latency.

We construct new private-information-retrieval protocols in the single-server setting. Our schemes allow a client to privately fetch a sequence of database records from a server, while the server answers each query in average time sublinear in the database size. Specifically, we introduce the first single-server private-information-retrieval schemes that have sublinear amortized server time, require sublinear additional storage, and allow the client to make her queries adaptively. Our protocols rely only on standard cryptographic assumptions (decision Diffie-Hellman, quadratic residuosity, learning with errors, etc.). They work by having the client first fetch a small "hint" about the database contents from the server. Generating this hint requires server time linear in the database size. Thereafter, the client can use the hint to make a bounded number of adaptive queries to the server, which the server answers in sublinear time--yielding sublinear amortized cost. Finally, we give lower bounds proving that our most efficient scheme is optimal with respect to the trade-off it achieves between server online time and client storage.