Protocols for Stateful Zero-Knowledge

Privacy preserving protocols typically involve the use of Zero Knowledge (ZK) proofs, which allow a prover to prove that a certain statement holds true, to a verifier, without revealing the witness (secret information that allows one to verify whether said statement holds true) to the verifier. This mechanism allows for the participation of users in such protocols whilst preserving the privacy of sensitive personal information. In some protocols, the need arises for the reuse of the information (or witnesses) used in a proof. In other words, the witnesses used in a proof must be related to those used in previous proofs. We propose Stateful Zero Knowledge (SZK) data structures, which are primitives that allow a user to store state information related to witnesses used in proofs, and then prove subsequent facts about this information. Our primitives also decouple state information from the proofs themselves, allowing for modular protocol design. We provide formal definitions for these primitives using a composable security framework, and go on to describe constructions that securely realize these definitions.

These primitives can be used as modular building blocks to attenuate the security guarantees of existing protocols in literature, to construct privacy preserving protocols that allow for the collection of statistics about secret information, and to build protocols for other schemes that may benefit from this technique, such as those that involve access control and oblivious transfer. We describe several such protocols in this thesis. We also provide computational cost measurements for our primitives and protocols by way of implementations, in order to show that they are practical for large data structure sizes. We finally provide a notation and a compiler that takes as input a ZK proof represented by said notation and outputs a secure SZK protocol, allowing for a layer of abstraction so that practitioners may specify the security properties and the data structures they wish to use, and be presented with a ready to use implementation without needing to deal with the theoretical aspects of these primitives, essentially bridging the gap between theoretical cryptographic constructions and their implementation.

This thesis conveys the results of FNR CORE Junior project, Stateful Zero Knowledge.