Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2007

AUTHORS

Ronen Gradwohl , Moni Naor , Benny Pinkas , Guy N. Rothblum

ABSTRACT

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. More... »

PAGES

166-182

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-540-72914-3_16

DOI

http://dx.doi.org/10.1007/978-3-540-72914-3_16

DIMENSIONS

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


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": "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", 
      "physical protocols", 
      "Sudoku puzzles", 
      "use of computers", 
      "cryptography literature", 
      "computational hardness", 
      "proof system", 
      "exchange messages", 
      "protocol relies", 
      "proof schemes", 
      "combinatorial puzzle", 
      "verifier", 
      "aid of computers", 
      "provers", 
      "common objects", 
      "computer", 
      "cards", 
      "protocol", 
      "playing cards", 
      "security", 
      "Sudoku", 
      "messages", 
      "objects", 
      "solution", 
      "scratch", 
      "scheme", 
      "information", 
      "question of interest", 
      "parties", 
      "model", 
      "relies", 
      "system", 
      "goal", 
      "usual model", 
      "foundation", 
      "method", 
      "interest", 
      "one", 
      "puzzle", 
      "aid", 
      "use", 
      "literature", 
      "humans", 
      "questions", 
      "reduction", 
      "lottery", 
      "hardness", 
      "problem", 
      "paper", 
      "popular combinatorial puzzle", 
      "machines exchange messages", 
      "simple playing cards", 
      "Physical Zero-Knowledge Proof Systems"
    ], 
    "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-01-01T19:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_246.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

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

158 TRIPLES      23 PREDICATES      82 URIs      74 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 N28e297b950b84d4b91d8d23fe2d65f15
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 Na3b2cb2b63d046f2965f02e56474b10d
9 schema:genre chapter
10 schema:inLanguage en
11 schema:isAccessibleForFree false
12 schema:isPartOf N5114de35030d4a7895979e743a7f1f23
13 schema:keywords Physical Zero-Knowledge Proof Systems
14 Sudoku
15 Sudoku puzzles
16 aid
17 aid of computers
18 cards
19 combinatorial puzzle
20 common objects
21 computational hardness
22 computer
23 cryptographic protocols
24 cryptography literature
25 exchange messages
26 foundation
27 goal
28 hardness
29 humans
30 information
31 interest
32 literature
33 lottery
34 machines exchange messages
35 messages
36 method
37 model
38 objects
39 one
40 paper
41 parties
42 physical protocols
43 playing cards
44 popular combinatorial puzzle
45 problem
46 proof schemes
47 proof system
48 protocol
49 protocol relies
50 provers
51 puzzle
52 question of interest
53 questions
54 reduction
55 relies
56 scheme
57 scratch
58 security
59 simple playing cards
60 solution
61 system
62 use
63 use of computers
64 usual model
65 verifier
66 zero-knowledge proof scheme
67 zero-knowledge proof system
68 schema:name Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles
69 schema:pagination 166-182
70 schema:productId N4a93b3dbb68f45f1883cba68fdb9d141
71 Nd3aad436f2074383a7fba9fa80e76eff
72 schema:publisher N8d0a9b1571864a4781d740293f0017c0
73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014831562
74 https://doi.org/10.1007/978-3-540-72914-3_16
75 schema:sdDatePublished 2022-01-01T19:14
76 schema:sdLicense https://scigraph.springernature.com/explorer/license/
77 schema:sdPublisher N57157e26ac8844d4bd01474a18640a3a
78 schema:url https://doi.org/10.1007/978-3-540-72914-3_16
79 sgo:license sg:explorer/license/
80 sgo:sdDataset chapters
81 rdf:type schema:Chapter
82 N00728751b60b4bd1bb5b57d16f4c765a rdf:first sg:person.07416054235.47
83 rdf:rest Nffec03987958474186a832e0c41b8868
84 N1edcb3da1253453f9f11b3da1c96a8a3 schema:familyName Prencipe
85 schema:givenName Giuseppe
86 rdf:type schema:Person
87 N28e297b950b84d4b91d8d23fe2d65f15 rdf:first sg:person.011266414555.48
88 rdf:rest N669d5926730b477a922363ce41447123
89 N4a93b3dbb68f45f1883cba68fdb9d141 schema:name doi
90 schema:value 10.1007/978-3-540-72914-3_16
91 rdf:type schema:PropertyValue
92 N5114de35030d4a7895979e743a7f1f23 schema:isbn 978-3-540-72913-6
93 978-3-540-72914-3
94 schema:name Fun with Algorithms
95 rdf:type schema:Book
96 N57157e26ac8844d4bd01474a18640a3a schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 N669d5926730b477a922363ce41447123 rdf:first sg:person.07776170271.83
99 rdf:rest N00728751b60b4bd1bb5b57d16f4c765a
100 N8d0a9b1571864a4781d740293f0017c0 schema:name Springer Nature
101 rdf:type schema:Organisation
102 N937a86e618ae45359c4cebb6ac3ff236 rdf:first Ne1938167f365497a9ebe0c848a434a2a
103 rdf:rest rdf:nil
104 Na3b2cb2b63d046f2965f02e56474b10d rdf:first Nc650511b62df46ecbb228a090633379d
105 rdf:rest Nd29725bb45b44827bb1218bb2976c19d
106 Nc650511b62df46ecbb228a090633379d schema:familyName Crescenzi
107 schema:givenName Pierluigi
108 rdf:type schema:Person
109 Nd29725bb45b44827bb1218bb2976c19d rdf:first N1edcb3da1253453f9f11b3da1c96a8a3
110 rdf:rest N937a86e618ae45359c4cebb6ac3ff236
111 Nd3aad436f2074383a7fba9fa80e76eff schema:name dimensions_id
112 schema:value pub.1014831562
113 rdf:type schema:PropertyValue
114 Ne1938167f365497a9ebe0c848a434a2a schema:familyName Pucci
115 schema:givenName Geppino
116 rdf:type schema:Person
117 Nffec03987958474186a832e0c41b8868 rdf:first sg:person.014351474277.34
118 rdf:rest rdf:nil
119 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
120 schema:name Information and Computing Sciences
121 rdf:type schema:DefinedTerm
122 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
123 schema:name Computation Theory and Mathematics
124 rdf:type schema:DefinedTerm
125 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
126 schema:name Data Format
127 rdf:type schema:DefinedTerm
128 sg:person.011266414555.48 schema:affiliation grid-institutes:grid.13992.30
129 schema:familyName Gradwohl
130 schema:givenName Ronen
131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011266414555.48
132 rdf:type schema:Person
133 sg:person.014351474277.34 schema:affiliation grid-institutes:grid.116068.8
134 schema:familyName Rothblum
135 schema:givenName Guy N.
136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351474277.34
137 rdf:type schema:Person
138 sg:person.07416054235.47 schema:affiliation grid-institutes:grid.18098.38
139 schema:familyName Pinkas
140 schema:givenName Benny
141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07416054235.47
142 rdf:type schema:Person
143 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
144 schema:familyName Naor
145 schema:givenName Moni
146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
147 rdf:type schema:Person
148 grid-institutes:grid.116068.8 schema:alternateName CSAIL, MIT, Cambridge, MA 02139, USA
149 schema:name CSAIL, MIT, Cambridge, MA 02139, USA
150 rdf:type schema:Organization
151 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel
152 Incumbent of the Judith Kleeman Professorial Chair, Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel
153 schema:name Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel
154 Incumbent of the Judith Kleeman Professorial Chair, Department of Computer Science and Applied Math, The Weizmann Institute of Science, Rehovot 76100, Israel
155 rdf:type schema:Organization
156 grid-institutes:grid.18098.38 schema:alternateName Department of Computer Science, University of Haifa, Haifa, Israel
157 schema:name Department of Computer Science, University of Haifa, Haifa, Israel
158 rdf:type schema:Organization
 




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


...