Delegation with Updatable Unambiguous Proofs and PPAD-Hardness View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2020-08-10

AUTHORS

Yael Tauman Kalai , Omer Paneth , Lisa Yang

ABSTRACT

In this work, we construct an updatable and unambiguous delegation scheme based on the decisional assumption on bilinear groups introduced by Kalai, Paneth and Yang [STOC 2019]. Using this delegation scheme, we show PPAD-hardness (and hence the hardness of computing Nash equilibria) based on the quasi-polynomial hardness of this bilinear group assumption and any hard language that is decidable in quasi-polynomial time and polynomial space.The delegation scheme is for super-polynomial time deterministic computations and is publicly verifiable and non-interactive in the common reference string (CRS) model. It is updatable meaning that given a proof for the statement that a Turing machine reaches some configuration C in T steps, it is efficient to update it into a proof for the statement that the machine reaches the next configuration \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C'$$\end{document} in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T+1$$\end{document} steps. It is unambiguous meaning that it is hard to find two different proofs for the same statement. More... »

PAGES

652-673

Book

TITLE

Advances in Cryptology – CRYPTO 2020

ISBN

978-3-030-56876-4
978-3-030-56877-1

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-56877-1_23

DOI

http://dx.doi.org/10.1007/978-3-030-56877-1_23

DIMENSIONS

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


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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "MIT, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "Microsoft Research, Cambridge, USA", 
            "MIT, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kalai", 
        "givenName": "Yael Tauman", 
        "id": "sg:person.015074540743.62", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074540743.62"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Tel Aviv University, Tel Aviv, Israel", 
          "id": "http://www.grid.ac/institutes/grid.12136.37", 
          "name": [
            "Tel Aviv University, Tel Aviv, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Paneth", 
        "givenName": "Omer", 
        "id": "sg:person.014073524511.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT, Cambridge, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT, Cambridge, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Yang", 
        "givenName": "Lisa", 
        "id": "sg:person.015330373527.13", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015330373527.13"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2020-08-10", 
    "datePublishedReg": "2020-08-10", 
    "description": "In this work, we construct an updatable and unambiguous delegation scheme based on the decisional assumption on bilinear groups introduced by Kalai, Paneth and Yang [STOC 2019]. Using this delegation scheme, we show PPAD-hardness (and hence the hardness of computing Nash equilibria) based on the quasi-polynomial hardness of this bilinear group assumption and any hard language that is decidable in quasi-polynomial time and polynomial space.The delegation scheme is for super-polynomial time deterministic computations and is publicly verifiable and non-interactive in the common reference string (CRS) model. It is updatable meaning that given a proof for the statement that a Turing machine reaches some configuration C in T steps, it is efficient to update it into a proof for the statement that the machine reaches the next configuration \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$C'$$\\end{document} in \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$T+1$$\\end{document} steps. It is unambiguous meaning that it is hard to find two different proofs for the same statement.", 
    "editor": [
      {
        "familyName": "Micciancio", 
        "givenName": "Daniele", 
        "type": "Person"
      }, 
      {
        "familyName": "Ristenpart", 
        "givenName": "Thomas", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-56877-1_23", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-030-56876-4", 
        "978-3-030-56877-1"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2020", 
      "type": "Book"
    }, 
    "keywords": [
      "delegation scheme", 
      "PPAD hardness", 
      "quasi-polynomial hardness", 
      "common reference string model", 
      "bilinear groups", 
      "quasi-polynomial time", 
      "decisional assumption", 
      "Turing machines", 
      "unambiguous meaning", 
      "next configuration", 
      "deterministic computation", 
      "polynomial space", 
      "machine", 
      "hard languages", 
      "group assumptions", 
      "scheme", 
      "T steps", 
      "proof", 
      "computation", 
      "language", 
      "configuration C", 
      "delegation", 
      "step", 
      "Kalai", 
      "space", 
      "work", 
      "assumption", 
      "model", 
      "statements", 
      "different proof", 
      "configuration", 
      "meaning", 
      "same statement", 
      "string model", 
      "time", 
      "Yang", 
      "group", 
      "hardness", 
      "Paneth", 
      "unambiguous proof"
    ], 
    "name": "Delegation with Updatable Unambiguous Proofs and PPAD-Hardness", 
    "pagination": "652-673", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1130050081"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-56877-1_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-56877-1_23", 
      "https://app.dimensions.ai/details/publication/pub.1130050081"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:29", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/chapter/chapter_22.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-56877-1_23"
  }
]
 

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-030-56877-1_23'

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-030-56877-1_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-56877-1_23'

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-030-56877-1_23'


 

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

123 TRIPLES      23 PREDICATES      65 URIs      58 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-56877-1_23 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nc6dd51aacc5a4f419e612daf7ac06e74
4 schema:datePublished 2020-08-10
5 schema:datePublishedReg 2020-08-10
6 schema:description In this work, we construct an updatable and unambiguous delegation scheme based on the decisional assumption on bilinear groups introduced by Kalai, Paneth and Yang [STOC 2019]. Using this delegation scheme, we show PPAD-hardness (and hence the hardness of computing Nash equilibria) based on the quasi-polynomial hardness of this bilinear group assumption and any hard language that is decidable in quasi-polynomial time and polynomial space.The delegation scheme is for super-polynomial time deterministic computations and is publicly verifiable and non-interactive in the common reference string (CRS) model. It is updatable meaning that given a proof for the statement that a Turing machine reaches some configuration C in T steps, it is efficient to update it into a proof for the statement that the machine reaches the next configuration \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C'$$\end{document} in \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$T+1$$\end{document} steps. It is unambiguous meaning that it is hard to find two different proofs for the same statement.
7 schema:editor Nd2000c8d31734b40840c5e4f36dc5b94
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N071f322ad70d4b3fbc85f118e7cdb47b
12 schema:keywords Kalai
13 PPAD hardness
14 Paneth
15 T steps
16 Turing machines
17 Yang
18 assumption
19 bilinear groups
20 common reference string model
21 computation
22 configuration
23 configuration C
24 decisional assumption
25 delegation
26 delegation scheme
27 deterministic computation
28 different proof
29 group
30 group assumptions
31 hard languages
32 hardness
33 language
34 machine
35 meaning
36 model
37 next configuration
38 polynomial space
39 proof
40 quasi-polynomial hardness
41 quasi-polynomial time
42 same statement
43 scheme
44 space
45 statements
46 step
47 string model
48 time
49 unambiguous meaning
50 unambiguous proof
51 work
52 schema:name Delegation with Updatable Unambiguous Proofs and PPAD-Hardness
53 schema:pagination 652-673
54 schema:productId N447cfbce30f2478180d2e5ca08ee3edc
55 N58add775d1744cd08e978379c28b914e
56 schema:publisher N856b47ee9e134a6a994cb95deea01931
57 schema:sameAs https://app.dimensions.ai/details/publication/pub.1130050081
58 https://doi.org/10.1007/978-3-030-56877-1_23
59 schema:sdDatePublished 2022-06-01T22:29
60 schema:sdLicense https://scigraph.springernature.com/explorer/license/
61 schema:sdPublisher N6a20da0473304f848d749e2a4f155f44
62 schema:url https://doi.org/10.1007/978-3-030-56877-1_23
63 sgo:license sg:explorer/license/
64 sgo:sdDataset chapters
65 rdf:type schema:Chapter
66 N071f322ad70d4b3fbc85f118e7cdb47b schema:isbn 978-3-030-56876-4
67 978-3-030-56877-1
68 schema:name Advances in Cryptology – CRYPTO 2020
69 rdf:type schema:Book
70 N09b096006e964dd5a6b3a3252f4907d1 rdf:first sg:person.014073524511.68
71 rdf:rest N70915f3ed86244e0b56a3070161e7b83
72 N447cfbce30f2478180d2e5ca08ee3edc schema:name dimensions_id
73 schema:value pub.1130050081
74 rdf:type schema:PropertyValue
75 N548a7ea4896c437b820ef72bbb3a0754 schema:familyName Ristenpart
76 schema:givenName Thomas
77 rdf:type schema:Person
78 N58add775d1744cd08e978379c28b914e schema:name doi
79 schema:value 10.1007/978-3-030-56877-1_23
80 rdf:type schema:PropertyValue
81 N5c1f1b0ed0f24617afd8beb726e5de49 rdf:first N548a7ea4896c437b820ef72bbb3a0754
82 rdf:rest rdf:nil
83 N60455f3e2faf4f5393d8937045ddf9bb schema:familyName Micciancio
84 schema:givenName Daniele
85 rdf:type schema:Person
86 N6a20da0473304f848d749e2a4f155f44 schema:name Springer Nature - SN SciGraph project
87 rdf:type schema:Organization
88 N70915f3ed86244e0b56a3070161e7b83 rdf:first sg:person.015330373527.13
89 rdf:rest rdf:nil
90 N856b47ee9e134a6a994cb95deea01931 schema:name Springer Nature
91 rdf:type schema:Organisation
92 Nc6dd51aacc5a4f419e612daf7ac06e74 rdf:first sg:person.015074540743.62
93 rdf:rest N09b096006e964dd5a6b3a3252f4907d1
94 Nd2000c8d31734b40840c5e4f36dc5b94 rdf:first N60455f3e2faf4f5393d8937045ddf9bb
95 rdf:rest N5c1f1b0ed0f24617afd8beb726e5de49
96 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
97 schema:name Information and Computing Sciences
98 rdf:type schema:DefinedTerm
99 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
100 schema:name Computation Theory and Mathematics
101 rdf:type schema:DefinedTerm
102 sg:person.014073524511.68 schema:affiliation grid-institutes:grid.12136.37
103 schema:familyName Paneth
104 schema:givenName Omer
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68
106 rdf:type schema:Person
107 sg:person.015074540743.62 schema:affiliation grid-institutes:grid.116068.8
108 schema:familyName Kalai
109 schema:givenName Yael Tauman
110 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015074540743.62
111 rdf:type schema:Person
112 sg:person.015330373527.13 schema:affiliation grid-institutes:grid.116068.8
113 schema:familyName Yang
114 schema:givenName Lisa
115 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015330373527.13
116 rdf:type schema:Person
117 grid-institutes:grid.116068.8 schema:alternateName MIT, Cambridge, USA
118 schema:name MIT, Cambridge, USA
119 Microsoft Research, Cambridge, USA
120 rdf:type schema:Organization
121 grid-institutes:grid.12136.37 schema:alternateName Tel Aviv University, Tel Aviv, Israel
122 schema:name Tel Aviv University, Tel Aviv, Israel
123 rdf:type schema:Organization
 




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


...