Matthew Fredrikson and Benjamin Livshits
9 April 2013
Applications increasingly rely on privacy-sensitive user data, but storing user's data in the cloud creates challenges for the application provider, as concerns arise relating to the possibility of data leaks, responding to regulatory pressure, and initiatives such as DoNotTrack. However, storing data in the cloud is not the only option: a recent trend explored in several recent research projects has been to move functionality to the client. Because execution happens on the client, such as a mobile device or even in the browser, this alone provides a degree of privacy in the computation, with only relevant data disclosed to the server. However, in many cases moving functionality to the client conflicts with a need for computational integrity: a malicious client can simply forge the results of a computation.
Traditionally, confidentiality and integrity have been two desirable design goals that are have been difficult to combine. Zero-Knowledge Proofs of Knowledge (ZKPK) offer a rigorous set of cryptographic mechanisms to balance these concerns. However, published uses of ZKPK have been difficult for regular developers to integrate into their code and, on top of that, have not been demonstrated to scale as required by most realistic applications.
This paper presents Z0 (pronounced "zee-not"), a compiler that consumes applications written in C# into code that automatically produces scalable zero-knowledge proofs of knowledge, while automatically splitting them into distributed code. Z0 builds detailed cost models and uses two existing zero-knowledge back-ends with varying performance characteristics to select the most efficient translation. Our case studies have been directly inspired by existing sophisticated widely-deployed commercial products that require both privacy and integrity. The performance delivered by Z0 is as much as 50x faster (about 15x on average) than either of the underlying techniques used in the back-ends can deliver, showing that applications in need of ZKPK which were previously hopelessly slow are now within reach for practical deployment.