Introducing Verifiable Privacy-Preserving Computing

Table of Links

Abstract & Introduction

Preliminaries

Zero-knowledge proofs and verifiable computing

Privacy-preserving computations

Requirements: an application’s perspective

Verifiable, privacy-preserving computing

Open challenges and future directions

Conclusion & References

Abstract

Privacy-enhancing technologies (PETs), such as secure multi-party computation (MPC) and homomorphic encryption (HE), are deployed increasingly often to guarantee data confidentiality in computations over private, distributed data. Similarly, we observe a steep increase in the adoption of zero-knowledge proofs (ZKPs) to guarantee (public) verifiability of locally executed computations. We project that applications that are data intensive and require strong privacy guarantees, are also likely to require correctness guarantees. While the combination of methods for (public) verifiability and privacy protection has clear significance, many attempts are far from practical adoption.

In this work, we analyze existing solutions that add (public) verifiability to privacy-preserving computations over distributed data, in order to preserve confidentiality and guarantee correctness. To determine the required security and usability properties and whether these are satisfied, we look at various application areas including verifiable outsourcing, distributed ledger technology (DLT), and genomics. We then classify the solutions and describe frequently used approaches as well as efficiency metrics. Last but not least, we identify open challenges and discuss directions for future research that make verifiable, privacy-preserving computations more secure, efficient, and applicable in the real world.

1. Introduction

In recent years, PETs have played a significant role in enabling the privacy-preserving computation of a function by two or more mutually distrusting parties over their respective private datasets. They can be used to (effectively) enrich, diversify, or enlarge the available dataset and thereby obtain improved, more representative, or otherwise impossible results from a wide range of computations (e.g., statistics, machine learning, or risk modeling).

Due to their potential to allow for such collaborations without losing confidentiality, PETs have been adopted in many domains, ranging from healthcare [1] to auctions [2] and finance [3]. Due to wide-spread interest, various PETs have been adopted and deployed in practice, even for dataintensive applications such as neural network inference [4].

Similarly, message authentication codes (MACs) and ZKPs allow honest parties to verify computations executed by other untrusted parties. These verification approaches are often applied when parties are mutually distrusting, or auditability by external parties or the general public is required. Most notably, the introduction of efficient ZKPs led to a wide range of applications for verifiable computing, ranging from verifiable outsourcing [5], [6] to anonymous payment systems [7], and publicly verifiable voting [8], [9].

Whilst PETs always provide clear guarantees for privacy of data or computation within a certain security model, they often do not, by themselves, guarantee data authenticity or — more importantly — offer verifiability. Recent advances in both fields have led to schemes that combine a specific PET with a certain verifiability approach to enable verifiable, privacy-preserving computations between distrusting parties. These solutions are particularly relevant when not only data privacy, but also the correctness of computation and result are at stake, e.g., computation outsourcing, decentralized settings, or e-voting.

The combination of privacy-preserving and verifiable computations is needed in a wide range of settings. In the situation where a group of parties want to collaboratively perform a computation over their private data, but do not have sufficient computational resources to do so, outsourcing of the computation (to the cloud) has become the common practice. However, in addition to concerns around the privacy of data, the parties have no guarantee whether the computational results are actually correct. By using verifiable PETs, all parties can be sure that their data remains private and their results are correct, thereby increasing trust in outsourced computations.

An even more prolific setting these days, is where an external party or the general public needs to be able to verify the results of a privacy-preserving computation. In electronic voting, auctions, and many blockchain/DLT applications, the public, i.e., a group of people that may or may not be known a priori, needs to be able to verify correctness to ascertain honest election results, auction outcomes and so on. Extending this setting further on the data authenticity side, some external parties may want to verify that a computation was executed correctly on some authenticated data.

Contributions. In this paper, we systematically analyze recent academic advances on the combination of PETs with verifiable computing technologies by categorizing existing works based on their construction approach. We then compare the different works and approaches based on requirements derived from frequently observed use cases, as well as their respective efficiency and security. The main focus lies on the enrichment of MPC and/or HE with ZKPs, MACs, or other verifiability approaches in (decentralized) computations over distributed data. Thus our contributions are as follows:

• Review and classification of existing schemes from academic literature. We specifically discuss the different building blocks that were used from both a privacy and a verifiability perspective.

• Extraction of the requirements/properties a verifiable privacy-preserving computing scheme should have from the perspective of four application scenarios.

• Systematic analysis of the identified properties and efficiency metrics of existing schemes.

• Discussion of open challenges and possible future directions in the field of (publicly) verifiable and privacypreserving computations. Specifically, we discuss directions for input authenticity, reusabilty, public verifiability for HE, and improved efficiency and security.

Research Questions. Our systematic analysis is driven by a set of four questions. We derive intuitive answers to the first two questions from existing literature on this topic. The latter two questions are answered using a thorough analysis of the state-of-the-art.

RQ1 Why should we verify MPC and HE?

RQ2 What properties should a scheme for verifiable, privacy-preserving computations have?

RQ3 How do existing solutions compare with regards to these properties (RQ2)?

RQ4 What are the open challenges and directions for future research in this mix?

Organization. The remainder of the paper is structured as follows. We present the necessary preliminaries in Section 2, and Section 3 discusses ZKPs and verifiable computing in general. Section 4 describes non-verifiable PETs and discusses why and in which settings verifiability is desirable.

We discuss various application domains in order to motivate and collect requirements for verifiable, privacypreserving computation methods in Section 5. Our main results are presented in Section 6, where we classify the state-of-the-art solutions for verifiable, privacy-preserving computations and discuss efficiency metrics. We also compare the solutions based on the identified properties and note what challenges we currently observe.

Open questions based on these challenges and other future research directions are presented in Section 7, followed by a conclusion.