### Generalized Proofs of Knowledge with Fully Dynamic Setup

Christian Badertscher, Daniel Jost, and Ueli Maurer

##### 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 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.

Available format(s)
Category
Foundations
Publication info
A major revision of an IACR publication in TCC 2021
Contact author(s)
daniel jost @ cs nyu edu
History
2021-09-17: last of 4 revisions
See all versions
Short URL
https://ia.cr/2019/662

CC BY

BibTeX

@misc{cryptoeprint:2019/662,
author = {Christian Badertscher and Daniel Jost and Ueli Maurer},
title = {Generalized Proofs of Knowledge with Fully Dynamic Setup},
howpublished = {Cryptology ePrint Archive, Paper 2019/662},
year = {2019},
note = {\url{https://eprint.iacr.org/2019/662}},
url = {https://eprint.iacr.org/2019/662}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.