Challenges and the Future of 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

7. Open challenges and future directions

Our classification shows a diverse range of solutions, but more importantly we observed a number of challenges. In this section we answer RQ4, by discussing the observed open challenges, i.e., C1–C4, in more detail, and presenting new ideas for future research directions.

Publicly verifiable 6 homomorphic encryption (C1 & C2). HE has rapidly become more practical in recent years, and improving efficiency further is a topic of active research. Verifiable homomorphic encryption solutions have only started to appear more recently. Because of this, the number of solutions is still rather limited and most solutions are not yet suitable for practical use cases.

Many solutions, especially those based on MACs, only provide non-public verifiability rather than the stronger notion of public verifiability, due to requiring use of a secret key for verification. There may be approaches to circumvent these limitations, e.g., by verifying the MAC without knowledge of the full secret key, similar to [40], [82].

We also observed that MAC-based approaches are often not general enough to support every type of computation. Especially ciphertext-maintenance operations do often not agree with the homomorphic MAC used and can therefore not be performed.

ZKP-based solutions do have general applicability, however are still far too inefficient to be applied for practical, let alone large-scale, computations. This is mainly due to the conflicting requirements between ZKP constructions and HE schemes. Solutions such as Rinocchio [86] are a step in the right direction, but are very novel and require improvements to become practical.

It is currently unclear which solution approach is most suitable for verifiable HE, as they all have different pros and cons. More research is needed to answer that question.

Efficient public verifiability 6 from standard assumptions 7 (C3). Many efficient solutions rely on non-standard security assumptions, or require trust in and access to specific hardware. This especially concerns solutions that use zk-SNARKs or TEEs. Solutions that rely on non-succinct ZKPs provide better security guarantees, but have significantly larger proof sizes and verification times. Alternatively, almost all constructions using MACs do not provide public verifiability, which is often desirable in practice.

Even though all zk-SNARK constructions rely on (nonstandard) knowledge assumptions, we do see improvements in other security aspects such as the removal of trusted setups in transparent zk-SNARKs, e.g., Fractal [49] and SuperSonic [50]. Improving the efficiency of these transparent constructions is still a topic of active research.

Similarly, we see new efficient ZKPs from standard assumptions, such as compressed Σ-protocols [27] or Σbullets [26]. These schemes are already being applied in novel constructions for verifiable PETs. Due to the active research into ZKP schemes with more favorable properties, we project novel developments there to influence verifiable PETs as well.

Post-quantum security 8 (C4). In a world where the threat of quantum computers on classical cryptography is increasing rapidly, post-quantum secure solutions will become more and more important [101]. Especially in cases with public verifiability, that make ciphertexts and/or commitments publicly available, forward security (i.e., protection against store-now-decrypt-later attacks) should be guaranteed with post-quantum secure solutions [66].

Most, recent FHE schemes are believed to be postquantum secure, and information-theoretically secure MPC protocols have been around for a long time. However, many other primitives used to create schemes for verifiable privacy-preserving processing solutions as described in this work do not satisfy such properties. Most ZKP constructions and commitment schemes that are currently being used are not secure against a quantum adversary.

The majority of works we found in our systematization did not discuss the post-quantum secure properties of their solutions. And indeed for most solutions this also did not hold. [72] does use many post-quantum secure primitives, and they also expect it to be feasible to make their protocol completely post-quantum secure, without going into detail.

Authenticated inputs (future direction). Verifiability of a privacy-preserving computation guarantees that the (public) output is computed correctly from the secret input. In other words, no corrupted party has meddled with the results. However, corrupted parties could still produce incorrect or malicious outputs by providing false inputs.

In most real-world use cases, computation correctness alone will not be sufficient, and input authentication will be required. One would protect the entire data pipeline from authenticated input to result, by combining the two. Moreover, such solutions can be used to guarantee reproducibility, i.e., it can be guaranteed that computations were verifiably executed on the same data. This implies that different computations on the same data will give comparable, and therefore more useful, results.

In our analysis we have seen one recent solution [76] that focused on both verifiability and input authentication. However, correctness of computations was not publicly verifiable and was more restricted regarding corruption of honest parties than other solutions. We note that the idea of ZKPs for authenticated data has been researched by, e.g., [102], and project input authentication for verifiable PETs to become a relevant research topic.

Reusability (future direction). In practice, we often run different algorithms on the same data, or the same algorithms on different data. Logically, the question can be raised whether reusing, e.g., commitments to inputs/results can improve efficiency, reduce communication, or provide guarantees for reproducibility. The solutions we found in our analysis had little to no attention for such reusability.

However, we have seen a number of non-verifiable solutions for reusable MPC [103] or reusable GC [104] appear in recent years. With increased efficiency and less communication, reusability is especially beneficial in decentralized settings with large amounts of data or many participants. Benefits become even more clear, when considering verifiable PETs, e.g., using costly ZKPs.