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", 
      "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

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.

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
 




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


...