CryptoDB
Generalized Proofs of Knowledge with Fully Dynamic Setup
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Proofs of knowledge (PoK) are one of the most fundamental notions in cryptography. The appeal of this notion is that it provides a general template that an application can suitably instantiate by choosing a specific relation. Nonetheless, several important applications have been brought to light, including proofs-of-ownership of files or two-factor authentication, which do not fit the PoK template but naturally appear to be special cases of a more general notion of proofs of knowledge or possession. One would thus expect that their security properties, in particular privacy and soundness, are simply derived as concrete instantiation of a common generalized PoK concept with well understood security semantics. Unfortunately, such a notion does not exist, resulting in a variety of tailor-made security definitions whose plausibility must be checked on a case-by-case basis. In this work, we close this gap by providing the theoretical foundations of a generalized notion of PoK that encompasses dynamic and setup-dependent relations as well as interactive statement derivations. This novel combination enables an application to directly specify relations that depend on an assumed setup, such as a random oracle, a database or ledger, and to have statements be agreed upon interactively and dynamically between parties based on the state of the setup. Our new notion is called \emph{agree-and-prove} and provides clear semantics of correctness, soundness, and zero-knowledge in the above generalized scenario. As an application, we first consider proofs-of-ownership of files for client-side file deduplication. We cast the problem and some of its prominent schemes in our agree-and-prove framework and formally analyze their security. Leveraging our generic zero-knowledge formalization, we then devise a novel scheme that is provably the privacy-preserving analogue of the well-known Merkle-Tree based protocol. As a second application, we consider two-factor entity authentication to showcase how the agree-and-prove notion encompasses proofs of ability, such as proving the correct usage of an abstract hardware token. |
Video from TCC 2021
BibTeX
@article{tcc-2021-31521,
title={Generalized Proofs of Knowledge with Fully Dynamic Setup},
booktitle={Theory of Cryptography;19th International Conference},
publisher={Springer},
doi={10.1007/978-3-030-90459-3_17},
author={Christian Badertscher and Daniel Jost and Ueli Maurer},
year=2021
}