{'fraction_non_alphanumeric': 0.022222222222222223, 'fraction_numerical': 0.0015594541910331384, 'mean_word_length': 5.183132530120482, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Agree-and-Prove: Generalized Proofs Of Knowledge and Applications

Proofs of knowledge (PoK) are one of the most fundamental notions in cryptography and have been used as a building block in numerous applications. The appeal of this notion is that it is parameterized by generic relations which an application can suitably instantiate. In contrast, more recent research has unveiled that the gap between the traditional PoK formalism and how applications employ it, is actually quite large. For example, it is well known from the work of Camenisch et al. (Eurocrypt 2009) that extending the formal treatment of PoKs to include an interactive statement derivation process can avoid security issues by giving much more precise security and complexity properties for a proof system. Despite this important progress to generalize the applicability of the PoK notion to cryptographic protocol design, the gap continues to be substantial, due to the fact that all prior works still assume the relation of a PoK to have an explicit representation known to the protocol participants. This creates a mismatch to many natural applications where a static and explicit representation can formally not be guaranteed, which typically are settings where one assumes setup functionalities such as a random oracle, a database, or a blockchain ledger, and where the relation to be proven depends on the setup. In this work, we close this gap by providing the theoretical foundations of a fully generalized notion of PoK that encompasses dynamic and setup-dependent relations. We showcase the new notion by two applications that so far lack a satisfactory cryptographic treatment. The new notion we introduce is called agree-and-prove and provides clear semantics of correctness, soundness, and zero-knowledge in the presence of generic setup, dynamic statement derivation, and setup-dependent relations of all sort. 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 generalized zero-knowledge formalization, we then devise a novel scheme that is provably the privacy-preserving analogon of the wellknown Merkle-Tree based proof-of-ownership protocol. As a second application, we consider entity authentication and two-factor authentication to showcase how the agree-and-prove notion encompasses proofs of possession or ability, such as proving the correct usage of an abstract hardware token.