Succinct Non-interactive Arguments via Linear Interactive Proofs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Nir Bitansky , Alessandro Chiesa , Yuval Ishai , Omer Paneth , Rafail Ostrovsky

ABSTRACT

Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays researches have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation.A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O(1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have “escaped the hegemony” of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments. More... »

PAGES

315-333

Book

TITLE

Theory of Cryptography

ISBN

978-3-642-36593-5
978-3-642-36594-2

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-36594-2_18

DOI

http://dx.doi.org/10.1007/978-3-642-36594-2_18

DIMENSIONS

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


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": "Tel Aviv University, Israel", 
          "id": "http://www.grid.ac/institutes/grid.12136.37", 
          "name": [
            "Tel Aviv University, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bitansky", 
        "givenName": "Nir", 
        "id": "sg:person.016302552357.74", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016302552357.74"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "MIT, USA", 
          "id": "http://www.grid.ac/institutes/grid.116068.8", 
          "name": [
            "MIT, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Chiesa", 
        "givenName": "Alessandro", 
        "id": "sg:person.014135776027.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014135776027.95"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Technion, Israel", 
          "id": "http://www.grid.ac/institutes/grid.6451.6", 
          "name": [
            "Technion, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ishai", 
        "givenName": "Yuval", 
        "id": "sg:person.010434442160.49", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010434442160.49"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Boston University, USA", 
          "id": "http://www.grid.ac/institutes/grid.189504.1", 
          "name": [
            "Boston University, USA"
          ], 
          "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": "UCLA, USA", 
          "id": "http://www.grid.ac/institutes/grid.19006.3e", 
          "name": [
            "UCLA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ostrovsky", 
        "givenName": "Rafail", 
        "id": "sg:person.015474716573.95", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015474716573.95"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays researches have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation.A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O(1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have \u201cescaped the hegemony\u201d of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments.", 
    "editor": [
      {
        "familyName": "Sahai", 
        "givenName": "Amit", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-36594-2_18", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-36593-5", 
        "978-3-642-36594-2"
      ], 
      "name": "Theory of Cryptography", 
      "type": "Book"
    }, 
    "keywords": [
      "succinct non-interactive arguments", 
      "non-interactive arguments", 
      "NP statements", 
      "expensive offline phase", 
      "interactive proofs", 
      "verification time", 
      "offline phase", 
      "succinct arguments", 
      "checkable proofs", 
      "low complexity", 
      "basic building blocks", 
      "size linear", 
      "field elements", 
      "arithmetic circuits", 
      "verification", 
      "verifier", 
      "attractive features", 
      "building blocks", 
      "common relaxation", 
      "computation", 
      "proof", 
      "complexity", 
      "construction", 
      "features", 
      "recent construction", 
      "block", 
      "statements", 
      "research", 
      "motivation", 
      "consist", 
      "time", 
      "focus", 
      "elements", 
      "circuit", 
      "linear", 
      "argument", 
      "such arguments", 
      "phase", 
      "relaxation", 
      "length", 
      "hegemony", 
      "problem"
    ], 
    "name": "Succinct Non-interactive Arguments via Linear Interactive Proofs", 
    "pagination": "315-333", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1016151540"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-36594-2_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-36594-2_18", 
      "https://app.dimensions.ai/details/publication/pub.1016151540"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-06-01T22:34", 
    "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_428.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-36594-2_18"
  }
]
 

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-642-36594-2_18'

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-642-36594-2_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-36594-2_18'

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-642-36594-2_18'


 

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

142 TRIPLES      23 PREDICATES      68 URIs      61 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-36594-2_18 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd2c964c25f494906afb22f8c6d1fdb14
4 schema:datePublished 2013
5 schema:datePublishedReg 2013-01-01
6 schema:description Succinct non-interactive arguments (SNARGs) enable verifying NP statements with lower complexity than required for classical NP verification. Traditionally, the focus has been on minimizing the length of such arguments; nowadays researches have focused also on minimizing verification time, by drawing motivation from the problem of delegating computation.A common relaxation is a preprocessing SNARG, which allows the verifier to conduct an expensive offline phase that is independent of the statement to be proven later. Recent constructions of preprocessing SNARGs have achieved attractive features: they are publicly-verifiable, proofs consist of only O(1) encrypted (or encoded) field elements, and verification is via arithmetic circuits of size linear in the NP statement. Additionally, these constructions seem to have “escaped the hegemony” of probabilistically-checkable proofs (PCPs) as a basic building block of succinct arguments.
7 schema:editor Nf16c83dcb07b45f48e9f10e743a6e154
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Ncfebb3fd17834b9386482fcc42158ce7
12 schema:keywords NP statements
13 argument
14 arithmetic circuits
15 attractive features
16 basic building blocks
17 block
18 building blocks
19 checkable proofs
20 circuit
21 common relaxation
22 complexity
23 computation
24 consist
25 construction
26 elements
27 expensive offline phase
28 features
29 field elements
30 focus
31 hegemony
32 interactive proofs
33 length
34 linear
35 low complexity
36 motivation
37 non-interactive arguments
38 offline phase
39 phase
40 problem
41 proof
42 recent construction
43 relaxation
44 research
45 size linear
46 statements
47 succinct arguments
48 succinct non-interactive arguments
49 such arguments
50 time
51 verification
52 verification time
53 verifier
54 schema:name Succinct Non-interactive Arguments via Linear Interactive Proofs
55 schema:pagination 315-333
56 schema:productId N09a4c276777c4473ab1c67733aaffc79
57 Nef5ccfaba86a4d119af186e32b64a2e3
58 schema:publisher N94d0e304d14d41339f43f8332a61400e
59 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016151540
60 https://doi.org/10.1007/978-3-642-36594-2_18
61 schema:sdDatePublished 2022-06-01T22:34
62 schema:sdLicense https://scigraph.springernature.com/explorer/license/
63 schema:sdPublisher N7b4aa09d0ea14524b71abb60fee343c3
64 schema:url https://doi.org/10.1007/978-3-642-36594-2_18
65 sgo:license sg:explorer/license/
66 sgo:sdDataset chapters
67 rdf:type schema:Chapter
68 N09a4c276777c4473ab1c67733aaffc79 schema:name dimensions_id
69 schema:value pub.1016151540
70 rdf:type schema:PropertyValue
71 N2137dde72ece40b6ac7769f03db7b25a rdf:first sg:person.015474716573.95
72 rdf:rest rdf:nil
73 N277316167f3d48dfb4c4bd265b15107e rdf:first sg:person.010434442160.49
74 rdf:rest N4a994b7b881549f7b8fbc1a7be7b7ea3
75 N4a994b7b881549f7b8fbc1a7be7b7ea3 rdf:first sg:person.014073524511.68
76 rdf:rest N2137dde72ece40b6ac7769f03db7b25a
77 N571248d637754ecfb5c0ed871fcf71cc rdf:first sg:person.014135776027.95
78 rdf:rest N277316167f3d48dfb4c4bd265b15107e
79 N7b4aa09d0ea14524b71abb60fee343c3 schema:name Springer Nature - SN SciGraph project
80 rdf:type schema:Organization
81 N94d0e304d14d41339f43f8332a61400e schema:name Springer Nature
82 rdf:type schema:Organisation
83 N9c77ed040f5b46388d42396cb8179249 schema:familyName Sahai
84 schema:givenName Amit
85 rdf:type schema:Person
86 Ncfebb3fd17834b9386482fcc42158ce7 schema:isbn 978-3-642-36593-5
87 978-3-642-36594-2
88 schema:name Theory of Cryptography
89 rdf:type schema:Book
90 Nd2c964c25f494906afb22f8c6d1fdb14 rdf:first sg:person.016302552357.74
91 rdf:rest N571248d637754ecfb5c0ed871fcf71cc
92 Nef5ccfaba86a4d119af186e32b64a2e3 schema:name doi
93 schema:value 10.1007/978-3-642-36594-2_18
94 rdf:type schema:PropertyValue
95 Nf16c83dcb07b45f48e9f10e743a6e154 rdf:first N9c77ed040f5b46388d42396cb8179249
96 rdf:rest rdf:nil
97 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
98 schema:name Information and Computing Sciences
99 rdf:type schema:DefinedTerm
100 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
101 schema:name Computation Theory and Mathematics
102 rdf:type schema:DefinedTerm
103 sg:person.010434442160.49 schema:affiliation grid-institutes:grid.6451.6
104 schema:familyName Ishai
105 schema:givenName Yuval
106 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010434442160.49
107 rdf:type schema:Person
108 sg:person.014073524511.68 schema:affiliation grid-institutes:grid.189504.1
109 schema:familyName Paneth
110 schema:givenName Omer
111 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014073524511.68
112 rdf:type schema:Person
113 sg:person.014135776027.95 schema:affiliation grid-institutes:grid.116068.8
114 schema:familyName Chiesa
115 schema:givenName Alessandro
116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014135776027.95
117 rdf:type schema:Person
118 sg:person.015474716573.95 schema:affiliation grid-institutes:grid.19006.3e
119 schema:familyName Ostrovsky
120 schema:givenName Rafail
121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015474716573.95
122 rdf:type schema:Person
123 sg:person.016302552357.74 schema:affiliation grid-institutes:grid.12136.37
124 schema:familyName Bitansky
125 schema:givenName Nir
126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016302552357.74
127 rdf:type schema:Person
128 grid-institutes:grid.116068.8 schema:alternateName MIT, USA
129 schema:name MIT, USA
130 rdf:type schema:Organization
131 grid-institutes:grid.12136.37 schema:alternateName Tel Aviv University, Israel
132 schema:name Tel Aviv University, Israel
133 rdf:type schema:Organization
134 grid-institutes:grid.189504.1 schema:alternateName Boston University, USA
135 schema:name Boston University, USA
136 rdf:type schema:Organization
137 grid-institutes:grid.19006.3e schema:alternateName UCLA, USA
138 schema:name UCLA, USA
139 rdf:type schema:Organization
140 grid-institutes:grid.6451.6 schema:alternateName Technion, Israel
141 schema:name Technion, Israel
142 rdf:type schema:Organization
 




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


...