Submitted Abstract
We will define, construct and analyse protocols for stateful zero-knowledge (SZK). SZK is defined as the task of keeping state information between prover and verifier in a zero-knowledge (ZK) proof system. The state information allows the verifier to enforce that the witnesses that the prover can use to compute a ZK proof are related in some way to witnesses or instances used in previous ZK proofs.In existing protocols, commitment schemes are frequently used to keep state information. In the design of those protocols, the task of keeping state information, reading data from it and writing data into it has so far been intertwined with ZK proofs that prove statements about data in the state. We think that, to improve modularity in protocol design, it is advisable to separate them. Our first objective is to define SZK. We view the state as a data structure where the prover stores each piece of data at a certain position. Our definitions must ensure the following: (1) data in the state is hidden from the verifier, (2) the prover can read and write data at positions while hiding both the data and the positions, and (3) a piece of data read from the state at a position equals the last piece of data stored at that position. We will define SZK as an ideal protocol in a composable security framework, such as the UC framework. Our definitions for SZK will allow modular protocol design. Our definitions must be suitable for settings where the prover uses a pseudonym or where proofs computed by a prover must remain unlinkable. Our definitions must also support a wide variety of data structures and must permit public verifiability. Our second objective is to construct protocols for SZK. We will provide constructions for different data structures, e.g. arrays, lists, trees and graphs. We will construct SZK protocols that offer pseudonymity or unlinkability to provers, and protocols that offer public verifiability. Unlike most existing protocols that implicitly keep state, ours provide the prover with the ability to hide positions read or written and to prove statements about the positions.Our third objective is to use SZK as building block in the construction of protocols that use ZK proofs to minimize personal data disclosure. In particular, we will provide protocols for data collection and analysis, which are useful to protect privacy while allowing the release of statistics about data. These protocols are of interest in a lot of settings, e.g. e-commerce, location-based services and smart metering and billing. We will also provide protocols for privacy-preserving authentication and access control, which should provide the prover with pseudonymity or unlikability. Thanks to the strong privacy properties offered by SZK, we will be able to design protocols for tasks that before could not be realized while fully protecting user privacy. Additionally, our protocols can be more efficient. By writing data related to statements already proven into the state information, we avoid the need of reproving statements, which currently is a source of inefficiency in settings that require unlinkability.Our fourth objective is to provide a notation for ZK proofs with support for SZK and a ZK compiler with support for SZK. Our notation must allow you to specify a data structure to keep state. To represent a ZK proof, the notation must allow the use of operations over the data structure, such as read and write. We will also design and implement a compiler that takes as input a ZK proof represented by using the notation and outputs a secure protocol for that ZK proof.