Generalized Proofs of Knowledge with Fully Dynamic Setup View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2021-11-04

AUTHORS

Christian Badertscher , Daniel Jost , 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. More... »

PAGES

499-528

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-90459-3_17

DOI

http://dx.doi.org/10.1007/978-3-030-90459-3_17

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1142414993


Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service: JSON-LD Playground Google SDTT

[
  {
    "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
    "about": [
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "IOHK, Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "IOHK, Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Badertscher", 
        "givenName": "Christian", 
        "id": "sg:person.010232721040.24", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010232721040.24"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "New York University, New York City, USA", 
          "id": "http://www.grid.ac/institutes/grid.137628.9", 
          "name": [
            "New York University, New York City, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Jost", 
        "givenName": "Daniel", 
        "id": "sg:person.013356446515.02", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013356446515.02"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "ETH Zurich, Zurich, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.5801.c", 
          "name": [
            "ETH Zurich, Zurich, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Maurer", 
        "givenName": "Ueli", 
        "id": "sg:person.01316567627.91", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2021-11-04", 
    "datePublishedReg": "2021-11-04", 
    "description": "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.", 
    "editor": [
      {
        "familyName": "Nissim", 
        "givenName": "Kobbi", 
        "type": "Person"
      }, 
      {
        "familyName": "Waters", 
        "givenName": "Brent", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-90459-3_17", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-90458-6", 
        "978-3-030-90459-3"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "two-factor authentication", 
      "proof of knowledge", 
      "hardware token", 
      "security semantics", 
      "proof of ability", 
      "Merkle tree", 
      "security properties", 
      "entity authentication", 
      "security definitions", 
      "zero-knowledge", 
      "clear semantics", 
      "file deduplication", 
      "random oracles", 
      "prominent schemes", 
      "concrete instantiation", 
      "particular privacy", 
      "novel scheme", 
      "authentication", 
      "semantics", 
      "dynamic setup", 
      "important applications", 
      "files", 
      "correct usage", 
      "general template", 
      "new notion", 
      "fundamental notions", 
      "soundness", 
      "cryptography", 
      "theoretical foundation", 
      "scheme", 
      "deduplication", 
      "privacy", 
      "ledger", 
      "applications", 
      "proof", 
      "general notion", 
      "second application", 
      "instantiation", 
      "oracle", 
      "novel combination", 
      "security", 
      "correctness", 
      "formalization", 
      "tokens", 
      "generalized notion", 
      "setup", 
      "scenarios", 
      "knowledge", 
      "framework", 
      "usage", 
      "special case", 
      "database", 
      "notion", 
      "protocol", 
      "template", 
      "POK", 
      "generalized proof", 
      "concept", 
      "parties", 
      "work", 
      "specific relation", 
      "case basis", 
      "definition", 
      "foundation", 
      "ownership", 
      "plausibility", 
      "variety", 
      "state", 
      "ability", 
      "derivation", 
      "gap", 
      "statements", 
      "cases", 
      "basis", 
      "combination", 
      "relation", 
      "possession", 
      "agree", 
      "appeal", 
      "properties", 
      "light", 
      "analogues", 
      "problem"
    ], 
    "name": "Generalized Proofs of Knowledge with Fully Dynamic Setup", 
    "pagination": "499-528", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1142414993"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-90459-3_17"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-90459-3_17", 
      "https://app.dimensions.ai/details/publication/pub.1142414993"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:38", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_139.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-90459-3_17"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-90459-3_17'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-90459-3_17'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-90459-3_17'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-90459-3_17'


 

This table displays all metadata directly associated to this object as RDF triples.

172 TRIPLES      23 PREDICATES      109 URIs      101 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-90459-3_17 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0804
4 schema:author N761c056d8e554173b7c306f3d51cc775
5 schema:datePublished 2021-11-04
6 schema:datePublishedReg 2021-11-04
7 schema:description 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.
8 schema:editor Nf1972a52f96f4cd49caef0e2a5594b13
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N091c9b53ee7040479034f5c4155c53c0
13 schema:keywords Merkle tree
14 POK
15 ability
16 agree
17 analogues
18 appeal
19 applications
20 authentication
21 basis
22 case basis
23 cases
24 clear semantics
25 combination
26 concept
27 concrete instantiation
28 correct usage
29 correctness
30 cryptography
31 database
32 deduplication
33 definition
34 derivation
35 dynamic setup
36 entity authentication
37 file deduplication
38 files
39 formalization
40 foundation
41 framework
42 fundamental notions
43 gap
44 general notion
45 general template
46 generalized notion
47 generalized proof
48 hardware token
49 important applications
50 instantiation
51 knowledge
52 ledger
53 light
54 new notion
55 notion
56 novel combination
57 novel scheme
58 oracle
59 ownership
60 particular privacy
61 parties
62 plausibility
63 possession
64 privacy
65 problem
66 prominent schemes
67 proof
68 proof of ability
69 proof of knowledge
70 properties
71 protocol
72 random oracles
73 relation
74 scenarios
75 scheme
76 second application
77 security
78 security definitions
79 security properties
80 security semantics
81 semantics
82 setup
83 soundness
84 special case
85 specific relation
86 state
87 statements
88 template
89 theoretical foundation
90 tokens
91 two-factor authentication
92 usage
93 variety
94 work
95 zero-knowledge
96 schema:name Generalized Proofs of Knowledge with Fully Dynamic Setup
97 schema:pagination 499-528
98 schema:productId N00fc8c08f61e453ba3f0b3ba6a1b1f53
99 N5a82c82ab5294a16a26ffca5bbf3648d
100 schema:publisher N44f3913446174865b5e0b9f538cb6842
101 schema:sameAs https://app.dimensions.ai/details/publication/pub.1142414993
102 https://doi.org/10.1007/978-3-030-90459-3_17
103 schema:sdDatePublished 2022-05-10T10:38
104 schema:sdLicense https://scigraph.springernature.com/explorer/license/
105 schema:sdPublisher Nddc8d55592884196b2a0756e047c791b
106 schema:url https://doi.org/10.1007/978-3-030-90459-3_17
107 sgo:license sg:explorer/license/
108 sgo:sdDataset chapters
109 rdf:type schema:Chapter
110 N00fc8c08f61e453ba3f0b3ba6a1b1f53 schema:name dimensions_id
111 schema:value pub.1142414993
112 rdf:type schema:PropertyValue
113 N091c9b53ee7040479034f5c4155c53c0 schema:isbn 978-3-030-90458-6
114 978-3-030-90459-3
115 schema:name Theory of Cryptography
116 rdf:type schema:Book
117 N23282c64f6e84506bf24a5e7ad74ba50 schema:familyName Nissim
118 schema:givenName Kobbi
119 rdf:type schema:Person
120 N44f3913446174865b5e0b9f538cb6842 schema:name Springer Nature
121 rdf:type schema:Organisation
122 N5a82c82ab5294a16a26ffca5bbf3648d schema:name doi
123 schema:value 10.1007/978-3-030-90459-3_17
124 rdf:type schema:PropertyValue
125 N6b7a60a7d38a4c47b1821d57662e3f2a rdf:first Nb9a1553fbdb74475878f5efce5a747d8
126 rdf:rest rdf:nil
127 N761c056d8e554173b7c306f3d51cc775 rdf:first sg:person.010232721040.24
128 rdf:rest N8b3546602b1040b1824d2e47cbcac35e
129 N8b3546602b1040b1824d2e47cbcac35e rdf:first sg:person.013356446515.02
130 rdf:rest Ncced5275cab74bee81cd9df50d5d044b
131 Nb9a1553fbdb74475878f5efce5a747d8 schema:familyName Waters
132 schema:givenName Brent
133 rdf:type schema:Person
134 Ncced5275cab74bee81cd9df50d5d044b rdf:first sg:person.01316567627.91
135 rdf:rest rdf:nil
136 Nddc8d55592884196b2a0756e047c791b schema:name Springer Nature - SN SciGraph project
137 rdf:type schema:Organization
138 Nf1972a52f96f4cd49caef0e2a5594b13 rdf:first N23282c64f6e84506bf24a5e7ad74ba50
139 rdf:rest N6b7a60a7d38a4c47b1821d57662e3f2a
140 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
141 schema:name Information and Computing Sciences
142 rdf:type schema:DefinedTerm
143 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
144 schema:name Computation Theory and Mathematics
145 rdf:type schema:DefinedTerm
146 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
147 schema:name Data Format
148 rdf:type schema:DefinedTerm
149 sg:person.010232721040.24 schema:affiliation grid-institutes:None
150 schema:familyName Badertscher
151 schema:givenName Christian
152 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010232721040.24
153 rdf:type schema:Person
154 sg:person.01316567627.91 schema:affiliation grid-institutes:grid.5801.c
155 schema:familyName Maurer
156 schema:givenName Ueli
157 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01316567627.91
158 rdf:type schema:Person
159 sg:person.013356446515.02 schema:affiliation grid-institutes:grid.137628.9
160 schema:familyName Jost
161 schema:givenName Daniel
162 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013356446515.02
163 rdf:type schema:Person
164 grid-institutes:None schema:alternateName IOHK, Zurich, Switzerland
165 schema:name IOHK, Zurich, Switzerland
166 rdf:type schema:Organization
167 grid-institutes:grid.137628.9 schema:alternateName New York University, New York City, USA
168 schema:name New York University, New York City, USA
169 rdf:type schema:Organization
170 grid-institutes:grid.5801.c schema:alternateName ETH Zurich, Zurich, Switzerland
171 schema:name ETH Zurich, Zurich, Switzerland
172 rdf:type schema:Organization
 




Preview window. Press ESC to close (or click here)


...