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


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2008-05-30

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 items such as 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

245-268

References to SciGraph publications

  • 2005. Basing Cryptographic Protocols on Tamper-Evident Seals in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1991-01. Bit commitment using pseudorandomness in JOURNAL OF CRYPTOLOGY
  • 1994. Discreet Solitary Games in ADVANCES IN CRYPTOLOGY — CRYPTO’ 93
  • 2006. Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2006
  • 1990. How to Explain Zero-Knowledge Protocols to Your Children in ADVANCES IN CRYPTOLOGY — CRYPTO’ 89 PROCEEDINGS
  • 2007-01-01. Security Against Covert Adversaries: Efficient Protocols for Realistic Adversaries in THEORY OF CRYPTOGRAPHY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00224-008-9119-9

    DOI

    http://dx.doi.org/10.1007/s00224-008-9119-9

    DIMENSIONS

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


    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, 76100, Rehovot, Israel", 
              "id": "http://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Department of Computer Science and Applied Math, The Weizmann Institute of Science, 76100, Rehovot, 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": "Department of Computer Science and Applied Math, The Weizmann Institute of Science, 76100, Rehovot, Israel", 
              "id": "http://www.grid.ac/institutes/grid.13992.30", 
              "name": [
                "Department of Computer Science and Applied Math, The Weizmann Institute of Science, 76100, Rehovot, 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, 02139, Cambridge, MA, USA", 
              "id": "http://www.grid.ac/institutes/grid.116068.8", 
              "name": [
                "CSAIL, MIT, 02139, Cambridge, MA, 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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/11523468_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015897667", 
              "https://doi.org/10.1007/11523468_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48329-2_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031001941", 
              "https://doi.org/10.1007/3-540-48329-2_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11761679_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019270268", 
              "https://doi.org/10.1007/11761679_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/0-387-34805-0_60", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014500120", 
              "https://doi.org/10.1007/0-387-34805-0_60"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf00196774", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1003773885", 
              "https://doi.org/10.1007/bf00196774"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-70936-7_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038693759", 
              "https://doi.org/10.1007/978-3-540-70936-7_8"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2008-05-30", 
        "datePublishedReg": "2008-05-30", 
        "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)\u00a0that there is a solution to the given puzzle, and (ii)\u00a0that 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 items such as 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 \u201clay-people\u201d and implementable without the use of computers.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00224-008-9119-9", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1052098", 
            "issn": [
              "1432-4350", 
              "1433-0490"
            ], 
            "name": "Theory of Computing Systems", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "44"
          }
        ], 
        "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", 
          "items", 
          "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": "245-268", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1038358838"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00224-008-9119-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00224-008-9119-9", 
          "https://app.dimensions.ai/details/publication/pub.1038358838"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-01-01T18:19", 
        "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/article/article_467.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00224-008-9119-9"
      }
    ]
     

    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/s00224-008-9119-9'

    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/s00224-008-9119-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00224-008-9119-9'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00224-008-9119-9'


     

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

    169 TRIPLES      22 PREDICATES      88 URIs      73 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00224-008-9119-9 schema:about anzsrc-for:08
    2 anzsrc-for:0802
    3 anzsrc-for:0804
    4 schema:author N8e01f9189a604e968bd5f79328b5fe14
    5 schema:citation sg:pub.10.1007/0-387-34805-0_60
    6 sg:pub.10.1007/11523468_24
    7 sg:pub.10.1007/11761679_7
    8 sg:pub.10.1007/3-540-48329-2_27
    9 sg:pub.10.1007/978-3-540-70936-7_8
    10 sg:pub.10.1007/bf00196774
    11 schema:datePublished 2008-05-30
    12 schema:datePublishedReg 2008-05-30
    13 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 items such as 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.
    14 schema:genre article
    15 schema:inLanguage en
    16 schema:isAccessibleForFree false
    17 schema:isPartOf N57d7c4f23b2c415eb1af9dd8fd51aab8
    18 Nee5dd6f3545c4438a30ce0ebbf3e8f7b
    19 sg:journal.1052098
    20 schema:keywords Physical Zero-Knowledge Proof Systems
    21 Sudoku
    22 Sudoku puzzles
    23 aid
    24 aid of computers
    25 cards
    26 combinatorial puzzle
    27 common objects
    28 computational hardness
    29 computer
    30 cryptographic protocols
    31 cryptography literature
    32 exchange messages
    33 foundation
    34 goal
    35 hardness
    36 humans
    37 information
    38 interest
    39 items
    40 literature
    41 lottery
    42 machines exchange messages
    43 messages
    44 method
    45 model
    46 objects
    47 one
    48 paper
    49 parties
    50 physical protocols
    51 playing cards
    52 popular combinatorial puzzle
    53 problem
    54 proof schemes
    55 proof system
    56 protocol
    57 protocol relies
    58 provers
    59 puzzle
    60 question of interest
    61 questions
    62 reduction
    63 relies
    64 scheme
    65 scratch
    66 security
    67 simple playing cards
    68 solution
    69 system
    70 use
    71 use of computers
    72 usual model
    73 verifier
    74 zero-knowledge proof scheme
    75 zero-knowledge proof system
    76 schema:name Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles
    77 schema:pagination 245-268
    78 schema:productId N32b187fbba354cd38faacb633129ab8b
    79 Nfb0869f2d92547a99c2f4d7f41ffe9d1
    80 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038358838
    81 https://doi.org/10.1007/s00224-008-9119-9
    82 schema:sdDatePublished 2022-01-01T18:19
    83 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    84 schema:sdPublisher N424f3b9771e94b4da960f3f5b0527b00
    85 schema:url https://doi.org/10.1007/s00224-008-9119-9
    86 sgo:license sg:explorer/license/
    87 sgo:sdDataset articles
    88 rdf:type schema:ScholarlyArticle
    89 N32b187fbba354cd38faacb633129ab8b schema:name dimensions_id
    90 schema:value pub.1038358838
    91 rdf:type schema:PropertyValue
    92 N424f3b9771e94b4da960f3f5b0527b00 schema:name Springer Nature - SN SciGraph project
    93 rdf:type schema:Organization
    94 N57d7c4f23b2c415eb1af9dd8fd51aab8 schema:issueNumber 2
    95 rdf:type schema:PublicationIssue
    96 N7cbf88d288454e37bcd1ca729d28347c rdf:first sg:person.014351474277.34
    97 rdf:rest rdf:nil
    98 N8e01f9189a604e968bd5f79328b5fe14 rdf:first sg:person.011266414555.48
    99 rdf:rest Nb48518617e764e388a394796880603b5
    100 Nb0831dca815841b1861c52ba70b80dbe rdf:first sg:person.07416054235.47
    101 rdf:rest N7cbf88d288454e37bcd1ca729d28347c
    102 Nb48518617e764e388a394796880603b5 rdf:first sg:person.07776170271.83
    103 rdf:rest Nb0831dca815841b1861c52ba70b80dbe
    104 Nee5dd6f3545c4438a30ce0ebbf3e8f7b schema:volumeNumber 44
    105 rdf:type schema:PublicationVolume
    106 Nfb0869f2d92547a99c2f4d7f41ffe9d1 schema:name doi
    107 schema:value 10.1007/s00224-008-9119-9
    108 rdf:type schema:PropertyValue
    109 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    110 schema:name Information and Computing Sciences
    111 rdf:type schema:DefinedTerm
    112 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    113 schema:name Computation Theory and Mathematics
    114 rdf:type schema:DefinedTerm
    115 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    116 schema:name Data Format
    117 rdf:type schema:DefinedTerm
    118 sg:journal.1052098 schema:issn 1432-4350
    119 1433-0490
    120 schema:name Theory of Computing Systems
    121 schema:publisher Springer Nature
    122 rdf:type schema:Periodical
    123 sg:person.011266414555.48 schema:affiliation grid-institutes:grid.13992.30
    124 schema:familyName Gradwohl
    125 schema:givenName Ronen
    126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011266414555.48
    127 rdf:type schema:Person
    128 sg:person.014351474277.34 schema:affiliation grid-institutes:grid.116068.8
    129 schema:familyName Rothblum
    130 schema:givenName Guy N.
    131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014351474277.34
    132 rdf:type schema:Person
    133 sg:person.07416054235.47 schema:affiliation grid-institutes:grid.18098.38
    134 schema:familyName Pinkas
    135 schema:givenName Benny
    136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07416054235.47
    137 rdf:type schema:Person
    138 sg:person.07776170271.83 schema:affiliation grid-institutes:grid.13992.30
    139 schema:familyName Naor
    140 schema:givenName Moni
    141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07776170271.83
    142 rdf:type schema:Person
    143 sg:pub.10.1007/0-387-34805-0_60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014500120
    144 https://doi.org/10.1007/0-387-34805-0_60
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/11523468_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015897667
    147 https://doi.org/10.1007/11523468_24
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/11761679_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019270268
    150 https://doi.org/10.1007/11761679_7
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/3-540-48329-2_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031001941
    153 https://doi.org/10.1007/3-540-48329-2_27
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/978-3-540-70936-7_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038693759
    156 https://doi.org/10.1007/978-3-540-70936-7_8
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/bf00196774 schema:sameAs https://app.dimensions.ai/details/publication/pub.1003773885
    159 https://doi.org/10.1007/bf00196774
    160 rdf:type schema:CreativeWork
    161 grid-institutes:grid.116068.8 schema:alternateName CSAIL, MIT, 02139, Cambridge, MA, USA
    162 schema:name CSAIL, MIT, 02139, Cambridge, MA, USA
    163 rdf:type schema:Organization
    164 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Math, The Weizmann Institute of Science, 76100, Rehovot, Israel
    165 schema:name Department of Computer Science and Applied Math, The Weizmann Institute of Science, 76100, Rehovot, Israel
    166 rdf:type schema:Organization
    167 grid-institutes:grid.18098.38 schema:alternateName Department of Computer Science, University of Haifa, Haifa, Israel
    168 schema:name Department of Computer Science, University of Haifa, Haifa, Israel
    169 rdf:type schema:Organization
     




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


    ...