Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2016-07-21

AUTHORS

Cynthia Dwork , Moni Naor , Guy N. Rothblum

ABSTRACT

We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of NP. These have proved elusive, despite extensive efforts. Our work builds on the compiler of Kalai and Raz, which takes as input an interactive proof system consisting of several rounds and produces a two-message argument system. The proof of soundness of their compiler relies on superpolynomial hardness assumptions.In this work we obtain a succinct two-message argument system for any language in NC, where the verifier’s work is linear (or even polylogarithmic). Soundness relies on any standard (polynomially hard) private information retrieval scheme or fully homomorphic encryption scheme. This is the first non trivial two-message succinct argument system that is based on a standard polynomial-time hardness assumption. We obtain this result by proving that the compiler is sound (under standard polynomial hardness assumptions) if the verifier in the original protocol runs in logarithmic space and public coins. We obtain our two-message argument by applying the compiler to an interactive proof protocol of Goldwasser, Kalai and Rothblum. On the other hand, we prove that under standard assumptions there is a sound interactive proof protocol that, when run through the compiler, results in a protocol that is not sound. More... »

PAGES

123-145

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-53015-3_5

DOI

http://dx.doi.org/10.1007/978-3-662-53015-3_5

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Microsoft Research, Mountain View, USA", 
          "id": "http://www.grid.ac/institutes/grid.419815.0", 
          "name": [
            "Microsoft Research, Mountain View, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dwork", 
        "givenName": "Cynthia", 
        "id": "sg:person.016065712157.59", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016065712157.59"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Applied Math, Weizmann Institute of Science, Rehovot, Israel", 
          "id": "http://www.grid.ac/institutes/grid.13992.30", 
          "name": [
            "Department of Computer Science and Applied Math, Weizmann Institute of Science, 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": "Samsung Research America, Mountain View, USA", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Samsung Research America, Mountain View, 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": "2016-07-21", 
    "datePublishedReg": "2016-07-21", 
    "description": "We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of NP. These have proved elusive, despite extensive efforts. Our work builds on the compiler of Kalai and Raz, which takes as input an interactive proof system consisting of several rounds and produces a two-message argument system. The proof of soundness of their compiler relies on superpolynomial hardness assumptions.In this work we obtain a succinct two-message argument system for any language in NC, where the verifier\u2019s work is linear (or even polylogarithmic). Soundness relies on any standard (polynomially hard) private information retrieval scheme or fully homomorphic encryption scheme. This is the first non trivial two-message succinct argument system that is based on a standard polynomial-time hardness assumption. We obtain this result by proving that the compiler is sound (under standard polynomial hardness assumptions) if the verifier in the original protocol runs in logarithmic space and public coins. We obtain our two-message argument by applying the compiler to an interactive proof protocol of Goldwasser, Kalai and Rothblum. On the other hand, we prove that under standard assumptions there is a sound interactive proof protocol that, when run through the compiler, results in a protocol that is not sound.", 
    "editor": [
      {
        "familyName": "Robshaw", 
        "givenName": "Matthew", 
        "type": "Person"
      }, 
      {
        "familyName": "Katz", 
        "givenName": "Jonathan", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-53015-3_5", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-662-53014-6", 
        "978-3-662-53015-3"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2016", 
      "type": "Book"
    }, 
    "keywords": [
      "interactive proof protocol", 
      "argument system", 
      "proof protocol", 
      "hardness assumptions", 
      "private information retrieval scheme", 
      "standard polynomial-time hardness assumptions", 
      "information retrieval scheme", 
      "homomorphic encryption scheme", 
      "interactive proof systems", 
      "proof of soundness", 
      "encryption scheme", 
      "protocol run", 
      "proof system", 
      "Aiello et al", 
      "compiler", 
      "retrieval scheme", 
      "verifier", 
      "public coins", 
      "logarithmic space", 
      "language", 
      "soundness", 
      "scheme", 
      "protocol", 
      "standard assumptions", 
      "Goldwasser", 
      "system", 
      "succinct", 
      "Kalai", 
      "complexity", 
      "work", 
      "NP", 
      "Rothblum", 
      "proof", 
      "input", 
      "relies", 
      "space", 
      "extensive efforts", 
      "tantalizing possibility", 
      "assumption", 
      "efforts", 
      "et al", 
      "sound", 
      "rounds", 
      "run", 
      "hand", 
      "coins", 
      "results", 
      "possibility", 
      "interaction", 
      "Raz", 
      "argument", 
      "NC", 
      "such arguments", 
      "al", 
      "discontent", 
      "two-message arguments", 
      "compiler of Kalai", 
      "two-message argument system", 
      "compiler relies", 
      "superpolynomial hardness assumptions", 
      "verifier\u2019s work", 
      "standard (polynomially hard) private information retrieval scheme", 
      "two-message succinct argument system", 
      "succinct argument system", 
      "polynomial-time hardness assumption", 
      "original protocol runs", 
      "sound interactive proof protocol"
    ], 
    "name": "Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems", 
    "pagination": "123-145", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1031340607"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-53015-3_5"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-53015-3_5", 
      "https://app.dimensions.ai/details/publication/pub.1031340607"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:18", 
    "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_309.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-53015-3_5"
  }
]
 

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-662-53015-3_5'

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-662-53015-3_5'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-53015-3_5'

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-662-53015-3_5'


 

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

152 TRIPLES      23 PREDICATES      92 URIs      85 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-53015-3_5 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nc19ad77d2ad64459accad2bdd7063d9c
4 schema:datePublished 2016-07-21
5 schema:datePublishedReg 2016-07-21
6 schema:description We are interested in constructing short two-message arguments for various languages, where the complexity of the verifier is small (e.g. linear in the input size, or even sublinear if the input is coded appropriately).In 2000 Aiello et al. suggested the tantalizing possibility of obtaining such arguments for all of NP. These have proved elusive, despite extensive efforts. Our work builds on the compiler of Kalai and Raz, which takes as input an interactive proof system consisting of several rounds and produces a two-message argument system. The proof of soundness of their compiler relies on superpolynomial hardness assumptions.In this work we obtain a succinct two-message argument system for any language in NC, where the verifier’s work is linear (or even polylogarithmic). Soundness relies on any standard (polynomially hard) private information retrieval scheme or fully homomorphic encryption scheme. This is the first non trivial two-message succinct argument system that is based on a standard polynomial-time hardness assumption. We obtain this result by proving that the compiler is sound (under standard polynomial hardness assumptions) if the verifier in the original protocol runs in logarithmic space and public coins. We obtain our two-message argument by applying the compiler to an interactive proof protocol of Goldwasser, Kalai and Rothblum. On the other hand, we prove that under standard assumptions there is a sound interactive proof protocol that, when run through the compiler, results in a protocol that is not sound.
7 schema:editor N9e4fb43b1f0d4763a0c1c02c3ff71726
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N33eff58a4039499c8184754b1f419bfb
12 schema:keywords Aiello et al
13 Goldwasser
14 Kalai
15 NC
16 NP
17 Raz
18 Rothblum
19 al
20 argument
21 argument system
22 assumption
23 coins
24 compiler
25 compiler of Kalai
26 compiler relies
27 complexity
28 discontent
29 efforts
30 encryption scheme
31 et al
32 extensive efforts
33 hand
34 hardness assumptions
35 homomorphic encryption scheme
36 information retrieval scheme
37 input
38 interaction
39 interactive proof protocol
40 interactive proof systems
41 language
42 logarithmic space
43 original protocol runs
44 polynomial-time hardness assumption
45 possibility
46 private information retrieval scheme
47 proof
48 proof of soundness
49 proof protocol
50 proof system
51 protocol
52 protocol run
53 public coins
54 relies
55 results
56 retrieval scheme
57 rounds
58 run
59 scheme
60 sound
61 sound interactive proof protocol
62 soundness
63 space
64 standard (polynomially hard) private information retrieval scheme
65 standard assumptions
66 standard polynomial-time hardness assumptions
67 succinct
68 succinct argument system
69 such arguments
70 superpolynomial hardness assumptions
71 system
72 tantalizing possibility
73 two-message argument system
74 two-message arguments
75 two-message succinct argument system
76 verifier
77 verifier’s work
78 work
79 schema:name Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems
80 schema:pagination 123-145
81 schema:productId N509df0f76f414d188e0c257292314f75
82 N5183deddbe6e498bb70fe0fd4712ce6f
83 schema:publisher N4ce57b5b75b24a5782526eb1c6406dd5
84 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031340607
85 https://doi.org/10.1007/978-3-662-53015-3_5
86 schema:sdDatePublished 2022-01-01T19:18
87 schema:sdLicense https://scigraph.springernature.com/explorer/license/
88 schema:sdPublisher N901b2b2d0e3a4a739e19d818cc5bf959
89 schema:url https://doi.org/10.1007/978-3-662-53015-3_5
90 sgo:license sg:explorer/license/
91 sgo:sdDataset chapters
92 rdf:type schema:Chapter
93 N13f6ae60843e4db3abf04da31d92dc18 rdf:first sg:person.014351474277.34
94 rdf:rest rdf:nil
95 N33eff58a4039499c8184754b1f419bfb schema:isbn 978-3-662-53014-6
96 978-3-662-53015-3
97 schema:name Advances in Cryptology – CRYPTO 2016
98 rdf:type schema:Book
99 N4ce57b5b75b24a5782526eb1c6406dd5 schema:name Springer Nature
100 rdf:type schema:Organisation
101 N509df0f76f414d188e0c257292314f75 schema:name dimensions_id
102 schema:value pub.1031340607
103 rdf:type schema:PropertyValue
104 N5183deddbe6e498bb70fe0fd4712ce6f schema:name doi
105 schema:value 10.1007/978-3-662-53015-3_5
106 rdf:type schema:PropertyValue
107 N5f0c799d1e544dfdac8e114cfec80ebd schema:familyName Robshaw
108 schema:givenName Matthew
109 rdf:type schema:Person
110 N6c72a0ceb76b4b619a34962e8ecd798c rdf:first sg:person.07776170271.83
111 rdf:rest N13f6ae60843e4db3abf04da31d92dc18
112 N901b2b2d0e3a4a739e19d818cc5bf959 schema:name Springer Nature - SN SciGraph project
113 rdf:type schema:Organization
114 N9e4fb43b1f0d4763a0c1c02c3ff71726 rdf:first N5f0c799d1e544dfdac8e114cfec80ebd
115 rdf:rest Ne514ad4e47af42ea9410beaaa2030968
116 Nc19ad77d2ad64459accad2bdd7063d9c rdf:first sg:person.016065712157.59
117 rdf:rest N6c72a0ceb76b4b619a34962e8ecd798c
118 Nd6150c8237e24eddb6e57dd6d2112d9d schema:familyName Katz
119 schema:givenName Jonathan
120 rdf:type schema:Person
121 Ne514ad4e47af42ea9410beaaa2030968 rdf:first Nd6150c8237e24eddb6e57dd6d2112d9d
122 rdf:rest rdf:nil
123 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
124 schema:name Information and Computing Sciences
125 rdf:type schema:DefinedTerm
126 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
127 schema:name Data Format
128 rdf:type schema:DefinedTerm
129 sg:person.014351474277.34 schema:affiliation grid-institutes:None
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.016065712157.59 schema:affiliation grid-institutes:grid.419815.0
135 schema:familyName Dwork
136 schema:givenName Cynthia
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016065712157.59
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:None schema:alternateName Samsung Research America, Mountain View, USA
145 schema:name Samsung Research America, Mountain View, USA
146 rdf:type schema:Organization
147 grid-institutes:grid.13992.30 schema:alternateName Department of Computer Science and Applied Math, Weizmann Institute of Science, Rehovot, Israel
148 schema:name Department of Computer Science and Applied Math, Weizmann Institute of Science, Rehovot, Israel
149 rdf:type schema:Organization
150 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research, Mountain View, USA
151 schema:name Microsoft Research, Mountain View, USA
152 rdf:type schema:Organization
 




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


...