Privacy and Trust in Adversarial Data Retrieval - Verifiable Computation Techniques for Private Queries on Malicious Servers

Kurzfassung

The task of secure data retrieval from remote entities is subject to ongoing research and of growing relevance in the context of outsourced computation. Cryptographic primitives like Private Information Retrieval (PIR) and Fully Homomorphic Encryption (FHE) are designed to protect a client’s privacy when querying databases or delegating expensive computations to external servers. Yet, many schemes assume the semi-honest threat model, where computing parties may only behave in a curious manner but otherwise have to adhere to the specified protocol. Hence, their security guarantees might be insufficient for arbitrary deviations from the protocol. Moreover, malicious parties might deliberately manipulate data to mislead clients into accepting false results. To defend against these attacks on correctness, methods of verifying responses are integrated into existing primitives. Our first main contribution is therefore to provide formal definitions of general blueprints for verifiable PIR (vPIR) and verifiable FHE (vFHE). We also present overviews of existing work to show different techniques of establishing the property of verifiability. The second part of the thesis focuses on the connection between PIR and FHE. It is known that PIR can be constructed from FHE. We examine if verifiability is preserved under one concrete construction. That is, starting from a verifiable FHE scheme, we are interested in whether the PIR scheme derived from it still exhibits this property. As we show, under a certain set of assumptions, vFHE schemes can indeed serve as basis for building vPIR schemes. In particular, vPIR protocols obtained in this way offer strong guarantees for both data privacy and correctness and are therefore well-suited for settings where malicious adversaries may be present.