International Association
for Cryptologic Research

Homomorphic encryption (HE) protects data in-use, but can be computationally expensive. To avoid the costly bootstrapping procedure that refreshes ciphertexts, some works have explored client-aided outsourcing protocols, where the client intermittently refreshes ciphertexts for a server that is performing homomorphic computations. But is this approach secure against malicious servers? We present a CPA-secure encryption scheme that is completely insecure in this setting. We define a new notion of security, called \emph{funcCPA}, that we prove is sufficient. Additionally, we show: - Homomorphic encryption schemes that have a certain type of circuit privacy -- for example, schemes in which ciphertexts can be ``sanitized" -- are funcCPA-secure. - In particular, assuming certain existing HE schemes are CPA-secure, they are also funcCPA-secure. - For certain encryption schemes, like Brakerski-Vaikuntanathan, that have a property that we call oblivious secret key extraction, funcCPA-security implies circular security -- i.e., that it is secure to provide an encryption of the secret key in a form usable for bootstrapping (to construct fully homomorphic encryption). Namely, funcCPA-security lies strictly between CPA-security and CCA2-security (under reasonable assumptions), and has an interesting relationship with circular security, though it is not known to be equivalent.

A distributed computation in which nodes are connected by a partial communication graph is called topology hiding if it does not reveal information about the graph beyond what is revealed by the output of the function. Previous results have shown that topology-hiding computation protocols exist for graphs of constant degree and logarithmic diameter in the number of nodes (Moran–Orlov–Richelson, TCC’15; Hirt et al., Crypto’16) as well as for other graph families, such as cycles, trees, and low circumference graphs (Akavia–Moran, Eurocrypt’17), but the feasibility question for general graphs was open. In this work, we positively resolve the above open problem: we prove that topology-hiding computation is feasible for all graphs under either the decisional Diffie–Hellman or quadratic residuosity assumption. Our techniques employ random or deterministic walks to generate paths covering the graph, upon which we apply the Akavia–Moran topology-hiding broadcast for chain graphs (paths). To prevent topology information revealed by the random walk, we design multiple graph-covering sequences that, together, are locally identical to receiving at each round a message from each neighbor and sending back a processed message from some neighbor (in a randomly permuted order).

Secure report is the problem of a client that retrieves all records matching specified attributes from a database table at the server (e.g. cloud), as in SQL SELECT queries, but where the query and the database are encrypted. Here, only the client has the secret key, but still the server is expected to compute and return the encrypted result. Secure report is theoretically possible with Fully Homomorphic Encryption (FHE). However, the current state-of-the-art solutions are realized by a polynomial of degree that is at least linear in the number m of records, which is too slow in practice even for very small databases. We present the first solution that is realized by a polynomial that attains degree independent of the number of records m, as well as the first implementation of an FHE solution to Secure report. This is by suggesting a novel paradigm that forges a link between cryptography and modern data summarization techniques known as coresets (core-sets), and sketches in particular. The key idea is to compute only a coreset of the desired report. Since the coreset is small, the client can quickly decode the desired report that the server computes after decrypting the coreset. We implemented our main reporting system in an open source library. This is the first implemented system that can answer such database queries when processing only FHE encrypted data and queries. As our analysis promises, the experimental results show that we can run Secure report queries on billions records in minutes on an Amazon EC2 server, compared to less than a hundred-thousands in previous FHE based solutions.