Ontology type: schema:Chapter
2007
AUTHORSRonen Gradwohl , Moni Naor , Benny Pinkas , Guy N. Rothblum
ABSTRACTWe consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, without revealing the solution to the verifier. The question of interest is how a prover can show: (i) that there is a solution to the given puzzle, and (ii) that he knows the solution, while not giving away any information about the solution to the verifier.In this paper we consider several protocols that achieve these goals. Broadly speaking, the protocols are either cryptographic or physical. By a cryptographic protocol we mean one in the usual model found in the foundations of cryptography literature. In this model, two machines exchange messages, and the security of the protocol relies on computational hardness. By a physical protocol we mean one that is implementable by humans using common objects, and preferably without the aid of computers. In particular, our physical protocols utilize scratch-off cards, similar to those used in lotteries, or even just simple playing cards.The cryptographic protocols are direct and efficient, and do not involve a reduction to other problems. The physical protocols are meant to be understood by ”lay-people” and implementable without the use of computers. More... »
PAGES166-182
Fun with Algorithms
ISBN
978-3-540-72913-6
978-3-540-72914-3
http://scigraph.springernature.com/pub.10.1007/978-3-540-72914-3_16
DOIhttp://dx.doi.org/10.1007/978-3-540-72914-3_16
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1014831562
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": "Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel"
],
"type": "Organization"
},
"familyName": "Gradwohl",
"givenName": "Ronen",
"id": "sg:person.011266414555.48",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011266414555.48"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Incumbent of the Judith Kleeman Professorial Chair, Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel",
"id": "http://www.grid.ac/institutes/grid.13992.30",
"name": [
"Incumbent of the Judith Kleeman Professorial Chair, Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel"
],
"type": "Organization"
},
"familyName": "Naor",
"givenName": "Moni",
"id": "sg:person.07776170271.83",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Computer Science, University of Haifa, Haifa, Israel",
"id": "http://www.grid.ac/institutes/grid.18098.38",
"name": [
"Department of Computer Science, University of Haifa, Haifa, Israel"
],
"type": "Organization"
},
"familyName": "Pinkas",
"givenName": "Benny",
"id": "sg:person.07416054235.47",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07416054235.47"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "CSAIL, MIT, Cambridge, MA 02139, USA",
"id": "http://www.grid.ac/institutes/grid.116068.8",
"name": [
"CSAIL, MIT, Cambridge, MA 02139, USA"
],
"type": "Organization"
},
"familyName": "Rothblum",
"givenName": "Guy N.",
"id": "sg:person.014351474277.34",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351474277.34"
],
"type": "Person"
}
],
"datePublished": "2007",
"datePublishedReg": "2007-01-01",
"description": "We consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, without revealing the solution to the verifier. The question of interest is how a prover can show: (i) that there is a solution to the given puzzle, and (ii) that he knows the solution, while not giving away any information about the solution to the verifier.In this paper we consider several protocols that achieve these goals. Broadly speaking, the protocols are either cryptographic or physical. By a cryptographic protocol we mean one in the usual model found in the foundations of cryptography literature. In this model, two machines exchange messages, and the security of the protocol relies on computational hardness. By a physical protocol we mean one that is implementable by humans using common objects, and preferably without the aid of computers. In particular, our physical protocols utilize scratch-off cards, similar to those used in lotteries, or even just simple playing cards.The cryptographic protocols are direct and efficient, and do not involve a reduction to other problems. The physical protocols are meant to be understood by \u201dlay-people\u201d and implementable without the use of computers.",
"editor": [
{
"familyName": "Crescenzi",
"givenName": "Pierluigi",
"type": "Person"
},
{
"familyName": "Prencipe",
"givenName": "Giuseppe",
"type": "Person"
},
{
"familyName": "Pucci",
"givenName": "Geppino",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-540-72914-3_16",
"inLanguage": "en",
"isAccessibleForFree": false,
"isPartOf": {
"isbn": [
"978-3-540-72913-6",
"978-3-540-72914-3"
],
"name": "Fun with Algorithms",
"type": "Book"
},
"keywords": [
"cryptographic protocols",
"zero-knowledge proof scheme",
"zero-knowledge proof system",
"Sudoku puzzles",
"physical protocols",
"use of computers",
"cryptography literature",
"exchange messages",
"computational hardness",
"combinatorial puzzle",
"protocol relies",
"proof system",
"proof schemes",
"aid of computers",
"verifier",
"provers",
"common objects",
"computer",
"cards",
"protocol",
"usual model",
"playing cards",
"security",
"Sudoku",
"messages",
"solution",
"scratch",
"objects",
"question of interest",
"scheme",
"information",
"parties",
"model",
"relies",
"system",
"goal",
"problem",
"foundation",
"method",
"puzzle",
"interest",
"one",
"aid",
"use",
"humans",
"literature",
"questions",
"lottery",
"reduction",
"hardness",
"paper"
],
"name": "Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles",
"pagination": "166-182",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1014831562"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-540-72914-3_16"
]
}
],
"publisher": {
"name": "Springer Nature",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-540-72914-3_16",
"https://app.dimensions.ai/details/publication/pub.1014831562"
],
"sdDataset": "chapters",
"sdDatePublished": "2022-05-20T07:41",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220519/entities/gbq_results/chapter/chapter_121.jsonl",
"type": "Chapter",
"url": "https://doi.org/10.1007/978-3-540-72914-3_16"
}
]
Download the RDF metadata as: json-ld nt turtle xml License info
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-540-72914-3_16'
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-540-72914-3_16'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-540-72914-3_16'
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-540-72914-3_16'
This table displays all metadata directly associated to this object as RDF triples.
154 TRIPLES
23 PREDICATES
78 URIs
70 LITERALS
7 BLANK NODES
Subject | Predicate | Object | |
---|---|---|---|
1 | sg:pub.10.1007/978-3-540-72914-3_16 | schema:about | anzsrc-for:08 |
2 | ″ | ″ | anzsrc-for:0802 |
3 | ″ | ″ | anzsrc-for:0804 |
4 | ″ | schema:author | N83ee83584f224d7c8f7daddf9cc467af |
5 | ″ | schema:datePublished | 2007 |
6 | ″ | schema:datePublishedReg | 2007-01-01 |
7 | ″ | schema:description | We consider cryptographic and physical zero-knowledge proof schemes for Sudoku, a popular combinatorial puzzle. We discuss methods that allow one party, the prover, to convince another party, the verifier, that the prover has solved a Sudoku puzzle, without revealing the solution to the verifier. The question of interest is how a prover can show: (i) that there is a solution to the given puzzle, and (ii) that he knows the solution, while not giving away any information about the solution to the verifier.In this paper we consider several protocols that achieve these goals. Broadly speaking, the protocols are either cryptographic or physical. By a cryptographic protocol we mean one in the usual model found in the foundations of cryptography literature. In this model, two machines exchange messages, and the security of the protocol relies on computational hardness. By a physical protocol we mean one that is implementable by humans using common objects, and preferably without the aid of computers. In particular, our physical protocols utilize scratch-off cards, similar to those used in lotteries, or even just simple playing cards.The cryptographic protocols are direct and efficient, and do not involve a reduction to other problems. The physical protocols are meant to be understood by ”lay-people” and implementable without the use of computers. |
8 | ″ | schema:editor | Nd6d21c81918847b6bea3d5bd5f83b79c |
9 | ″ | schema:genre | chapter |
10 | ″ | schema:inLanguage | en |
11 | ″ | schema:isAccessibleForFree | false |
12 | ″ | schema:isPartOf | Ne6a388322e1e46d38bf091dde9d0f738 |
13 | ″ | schema:keywords | Sudoku |
14 | ″ | ″ | Sudoku puzzles |
15 | ″ | ″ | aid |
16 | ″ | ″ | aid of computers |
17 | ″ | ″ | cards |
18 | ″ | ″ | combinatorial puzzle |
19 | ″ | ″ | common objects |
20 | ″ | ″ | computational hardness |
21 | ″ | ″ | computer |
22 | ″ | ″ | cryptographic protocols |
23 | ″ | ″ | cryptography literature |
24 | ″ | ″ | exchange messages |
25 | ″ | ″ | foundation |
26 | ″ | ″ | goal |
27 | ″ | ″ | hardness |
28 | ″ | ″ | humans |
29 | ″ | ″ | information |
30 | ″ | ″ | interest |
31 | ″ | ″ | literature |
32 | ″ | ″ | lottery |
33 | ″ | ″ | messages |
34 | ″ | ″ | method |
35 | ″ | ″ | model |
36 | ″ | ″ | objects |
37 | ″ | ″ | one |
38 | ″ | ″ | paper |
39 | ″ | ″ | parties |
40 | ″ | ″ | physical protocols |
41 | ″ | ″ | playing cards |
42 | ″ | ″ | problem |
43 | ″ | ″ | proof schemes |
44 | ″ | ″ | proof system |
45 | ″ | ″ | protocol |
46 | ″ | ″ | protocol relies |
47 | ″ | ″ | provers |
48 | ″ | ″ | puzzle |
49 | ″ | ″ | question of interest |
50 | ″ | ″ | questions |
51 | ″ | ″ | reduction |
52 | ″ | ″ | relies |
53 | ″ | ″ | scheme |
54 | ″ | ″ | scratch |
55 | ″ | ″ | security |
56 | ″ | ″ | solution |
57 | ″ | ″ | system |
58 | ″ | ″ | use |
59 | ″ | ″ | use of computers |
60 | ″ | ″ | usual model |
61 | ″ | ″ | verifier |
62 | ″ | ″ | zero-knowledge proof scheme |
63 | ″ | ″ | zero-knowledge proof system |
64 | ″ | schema:name | Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles |
65 | ″ | schema:pagination | 166-182 |
66 | ″ | schema:productId | N092bf42de8c44c0c86820f043cc32fd1 |
67 | ″ | ″ | N29f5b4c0cc614f109937ab26b86dee1c |
68 | ″ | schema:publisher | N1fe58af6a8fd47ab8c01ec0ee8213cc5 |
69 | ″ | schema:sameAs | https://app.dimensions.ai/details/publication/pub.1014831562 |
70 | ″ | ″ | https://doi.org/10.1007/978-3-540-72914-3_16 |
71 | ″ | schema:sdDatePublished | 2022-05-20T07:41 |
72 | ″ | schema:sdLicense | https://scigraph.springernature.com/explorer/license/ |
73 | ″ | schema:sdPublisher | N922480f3464e41c28fc873b81c6c10ed |
74 | ″ | schema:url | https://doi.org/10.1007/978-3-540-72914-3_16 |
75 | ″ | sgo:license | sg:explorer/license/ |
76 | ″ | sgo:sdDataset | chapters |
77 | ″ | rdf:type | schema:Chapter |
78 | N092bf42de8c44c0c86820f043cc32fd1 | schema:name | dimensions_id |
79 | ″ | schema:value | pub.1014831562 |
80 | ″ | rdf:type | schema:PropertyValue |
81 | N1fe58af6a8fd47ab8c01ec0ee8213cc5 | schema:name | Springer Nature |
82 | ″ | rdf:type | schema:Organisation |
83 | N23be75ba13db4c78a66cf4de25d03197 | rdf:first | sg:person.07416054235.47 |
84 | ″ | rdf:rest | Na482cfab881f425e8292417072b5c0b6 |
85 | N29f5b4c0cc614f109937ab26b86dee1c | schema:name | doi |
86 | ″ | schema:value | 10.1007/978-3-540-72914-3_16 |
87 | ″ | rdf:type | schema:PropertyValue |
88 | N2ed4afce6ca64f6fa303b56a2a7e33e6 | rdf:first | sg:person.07776170271.83 |
89 | ″ | rdf:rest | N23be75ba13db4c78a66cf4de25d03197 |
90 | N46e40a0c5a6c497092d2412d999ebade | schema:familyName | Pucci |
91 | ″ | schema:givenName | Geppino |
92 | ″ | rdf:type | schema:Person |
93 | N6a2a5ce573e94e2cb5cc2cc12ca6e817 | rdf:first | N46e40a0c5a6c497092d2412d999ebade |
94 | ″ | rdf:rest | rdf:nil |
95 | N7fc12322d6c54a6fb00b8b98685dca81 | rdf:first | Nccbe0c019f2944518de8ac9054c23416 |
96 | ″ | rdf:rest | N6a2a5ce573e94e2cb5cc2cc12ca6e817 |
97 | N83ee83584f224d7c8f7daddf9cc467af | rdf:first | sg:person.011266414555.48 |
98 | ″ | rdf:rest | N2ed4afce6ca64f6fa303b56a2a7e33e6 |
99 | N84d995240aac46599b52d463b61d6825 | schema:familyName | Crescenzi |
100 | ″ | schema:givenName | Pierluigi |
101 | ″ | rdf:type | schema:Person |
102 | N922480f3464e41c28fc873b81c6c10ed | schema:name | Springer Nature - SN SciGraph project |
103 | ″ | rdf:type | schema:Organization |
104 | Na482cfab881f425e8292417072b5c0b6 | rdf:first | sg:person.014351474277.34 |
105 | ″ | rdf:rest | rdf:nil |
106 | Nccbe0c019f2944518de8ac9054c23416 | schema:familyName | Prencipe |
107 | ″ | schema:givenName | Giuseppe |
108 | ″ | rdf:type | schema:Person |
109 | Nd6d21c81918847b6bea3d5bd5f83b79c | rdf:first | N84d995240aac46599b52d463b61d6825 |
110 | ″ | rdf:rest | N7fc12322d6c54a6fb00b8b98685dca81 |
111 | Ne6a388322e1e46d38bf091dde9d0f738 | schema:isbn | 978-3-540-72913-6 |
112 | ″ | ″ | 978-3-540-72914-3 |
113 | ″ | schema:name | Fun with Algorithms |
114 | ″ | rdf:type | schema:Book |
115 | anzsrc-for:08 | schema:inDefinedTermSet | anzsrc-for: |
116 | ″ | schema:name | Information and Computing Sciences |
117 | ″ | rdf:type | schema:DefinedTerm |
118 | anzsrc-for:0802 | schema:inDefinedTermSet | anzsrc-for: |
119 | ″ | schema:name | Computation Theory and Mathematics |
120 | ″ | rdf:type | schema:DefinedTerm |
121 | anzsrc-for:0804 | schema:inDefinedTermSet | anzsrc-for: |
122 | ″ | schema:name | Data Format |
123 | ″ | rdf:type | schema:DefinedTerm |
124 | sg:person.011266414555.48 | schema:affiliation | grid-institutes:grid.13992.30 |
125 | ″ | schema:familyName | Gradwohl |
126 | ″ | schema:givenName | Ronen |
127 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011266414555.48 |
128 | ″ | rdf:type | schema:Person |
129 | sg:person.014351474277.34 | schema:affiliation | grid-institutes:grid.116068.8 |
130 | ″ | schema:familyName | Rothblum |
131 | ″ | schema:givenName | Guy N. |
132 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351474277.34 |
133 | ″ | rdf:type | schema:Person |
134 | sg:person.07416054235.47 | schema:affiliation | grid-institutes:grid.18098.38 |
135 | ″ | schema:familyName | Pinkas |
136 | ″ | schema:givenName | Benny |
137 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07416054235.47 |
138 | ″ | rdf:type | schema:Person |
139 | sg:person.07776170271.83 | schema:affiliation | grid-institutes:grid.13992.30 |
140 | ″ | schema:familyName | Naor |
141 | ″ | schema:givenName | Moni |
142 | ″ | schema:sameAs | https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83 |
143 | ″ | rdf:type | schema:Person |
144 | grid-institutes:grid.116068.8 | schema:alternateName | CSAIL, MIT, Cambridge, MA 02139, USA |
145 | ″ | schema:name | CSAIL, MIT, Cambridge, MA 02139, USA |
146 | ″ | rdf:type | schema:Organization |
147 | grid-institutes:grid.13992.30 | schema:alternateName | Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel |
148 | ″ | ″ | Incumbent of the Judith Kleeman Professorial Chair, Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel |
149 | ″ | schema:name | Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel |
150 | ″ | ″ | Incumbent of the Judith Kleeman Professorial Chair, Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel |
151 | ″ | rdf:type | schema:Organization |
152 | grid-institutes:grid.18098.38 | schema:alternateName | Department of Computer Science, University of Haifa, Haifa, Israel |
153 | ″ | schema:name | Department of Computer Science, University of Haifa, Haifa, Israel |
154 | ″ | rdf:type | schema:Organization |