Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2019-08-01

AUTHORS

Tiacheng Xie , Jiaheng Zhang , Yupeng Zhang , Charalampos Papamanthou , Dawn Song

ABSTRACT

We present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if C is the size of the circuit being proved (i) the prover time is O(C) irrespective of the circuit type; (ii) the proof size and verification time are both \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(d\log C)$$\end{document} for d-depth log-space uniform circuits (such as RAM programs). In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200 s to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive. More... »

PAGES

733-764

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-26954-8_24

DOI

http://dx.doi.org/10.1007/978-3-030-26954-8_24

DIMENSIONS

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


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": "University of California, Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Xie", 
        "givenName": "Tiacheng", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of California, Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Jiaheng", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Texas A&M University, College Station, USA", 
          "id": "http://www.grid.ac/institutes/grid.264756.4", 
          "name": [
            "University of California, Berkeley, USA", 
            "Texas A&M University, College Station, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zhang", 
        "givenName": "Yupeng", 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Maryland, College Park, USA", 
          "id": "http://www.grid.ac/institutes/grid.164295.d", 
          "name": [
            "University of Maryland, College Park, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Papamanthou", 
        "givenName": "Charalampos", 
        "id": "sg:person.010450677547.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450677547.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of California, Berkeley, USA", 
          "id": "http://www.grid.ac/institutes/grid.47840.3f", 
          "name": [
            "University of California, Berkeley, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Song", 
        "givenName": "Dawn", 
        "id": "sg:person.01143152610.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01143152610.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2019-08-01", 
    "datePublishedReg": "2019-08-01", 
    "description": "We present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if C is the size of the circuit being proved (i) the prover time is O(C) irrespective of the circuit type; (ii) the proof size and verification time are both \\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}$$O(d\\log C)$$\\end{document} for d-depth log-space uniform circuits (such as RAM programs). In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200\u00a0s to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive.", 
    "editor": [
      {
        "familyName": "Boldyreva", 
        "givenName": "Alexandra", 
        "type": "Person"
      }, 
      {
        "familyName": "Micciancio", 
        "givenName": "Daniele", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-26954-8_24", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-26953-1", 
        "978-3-030-26954-8"
      ], 
      "name": "Advances in Cryptology \u2013 CRYPTO 2019", 
      "type": "Book"
    }, 
    "keywords": [
      "zero-knowledge proof system", 
      "verification time", 
      "proof size", 
      "proof system", 
      "zero-knowledge proofs", 
      "interactive proof protocol", 
      "prover time", 
      "prover computation", 
      "proof protocol", 
      "zero-knowledge", 
      "linear time algorithm", 
      "new linear time algorithm", 
      "efficient approach", 
      "circuit logic", 
      "Libra", 
      "one-time", 
      "provers", 
      "Goldwasser", 
      "algorithm", 
      "protocol", 
      "computation", 
      "proof", 
      "system", 
      "logic", 
      "implementation", 
      "Rothblum", 
      "Kalai", 
      "input", 
      "time", 
      "setup", 
      "example", 
      "circuit", 
      "uniform circuits", 
      "size", 
      "polynomials", 
      "practice", 
      "types", 
      "tree roots", 
      "circuit types", 
      "roots", 
      "irrespective", 
      "asymptotics", 
      "leaves", 
      "approach"
    ], 
    "name": "Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation", 
    "pagination": "733-764", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1120206954"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-26954-8_24"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-26954-8_24", 
      "https://app.dimensions.ai/details/publication/pub.1120206954"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:43", 
    "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_208.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-26954-8_24"
  }
]
 

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-26954-8_24'

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-26954-8_24'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-26954-8_24'

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-26954-8_24'


 

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

141 TRIPLES      23 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-26954-8_24 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Ndc12a9a7001d4e1cbf052040858b4cf4
4 schema:datePublished 2019-08-01
5 schema:datePublishedReg 2019-08-01
6 schema:description We present Libra, the first zero-knowledge proof system that has both optimal prover time and succinct proof size/verification time. In particular, if C is the size of the circuit being proved (i) the prover time is O(C) irrespective of the circuit type; (ii) the proof size and verification time are both \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$O(d\log C)$$\end{document} for d-depth log-space uniform circuits (such as RAM programs). In addition Libra features an one-time trusted setup that depends only on the size of the input to the circuit and not on the circuit logic. Underlying Libra is a new linear-time algorithm for the prover of the interactive proof protocol by Goldwasser, Kalai and Rothblum (also known as GKR protocol), as well as an efficient approach to turn the GKR protocol to zero-knowledge using small masking polynomials. Not only does Libra have excellent asymptotics, but it is also efficient in practice. For example, our implementation shows that it takes 200 s to generate a proof for constructing a SHA2-based Merkle tree root on 256 leaves, outperforming all existing zero-knowledge proof systems. Proof size and verification time of Libra are also competitive.
7 schema:editor N0d33519fcea84378b35fb3e3f9626cee
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf Nec9f50151fa2496aa85a3642c43124aa
12 schema:keywords Goldwasser
13 Kalai
14 Libra
15 Rothblum
16 algorithm
17 approach
18 asymptotics
19 circuit
20 circuit logic
21 circuit types
22 computation
23 efficient approach
24 example
25 implementation
26 input
27 interactive proof protocol
28 irrespective
29 leaves
30 linear time algorithm
31 logic
32 new linear time algorithm
33 one-time
34 polynomials
35 practice
36 proof
37 proof protocol
38 proof size
39 proof system
40 protocol
41 prover computation
42 prover time
43 provers
44 roots
45 setup
46 size
47 system
48 time
49 tree roots
50 types
51 uniform circuits
52 verification time
53 zero-knowledge
54 zero-knowledge proof system
55 zero-knowledge proofs
56 schema:name Libra: Succinct Zero-Knowledge Proofs with Optimal Prover Computation
57 schema:pagination 733-764
58 schema:productId N93cd9bd140a443e595c0890f5d5d676d
59 Nf41b44c65ba14b8f9699e32a46e9faa1
60 schema:publisher Nbb13854a331f42b0a622b42a845fbc00
61 schema:sameAs https://app.dimensions.ai/details/publication/pub.1120206954
62 https://doi.org/10.1007/978-3-030-26954-8_24
63 schema:sdDatePublished 2022-05-20T07:43
64 schema:sdLicense https://scigraph.springernature.com/explorer/license/
65 schema:sdPublisher Ne304163cfcc94b0096909e760d3b2db9
66 schema:url https://doi.org/10.1007/978-3-030-26954-8_24
67 sgo:license sg:explorer/license/
68 sgo:sdDataset chapters
69 rdf:type schema:Chapter
70 N0d33519fcea84378b35fb3e3f9626cee rdf:first Nc82a681e677a45f4972c23e890375228
71 rdf:rest Nfcdea07ab879457e8711d7974ac93c7e
72 N11513cf1f70e4c469bf228936506d04e rdf:first N4362d720169d4eb4a86fe653223cc721
73 rdf:rest N450afb7371874a5aafdea2996ee17e77
74 N4362d720169d4eb4a86fe653223cc721 schema:affiliation grid-institutes:grid.47840.3f
75 schema:familyName Zhang
76 schema:givenName Jiaheng
77 rdf:type schema:Person
78 N450afb7371874a5aafdea2996ee17e77 rdf:first Neae3dcaace0d4d15b0a614274e09cab3
79 rdf:rest Nff9f1522315045ecbe3715f142c6b85b
80 N4c168c4c0eab40fe97b07a5157ac4416 schema:affiliation grid-institutes:grid.47840.3f
81 schema:familyName Xie
82 schema:givenName Tiacheng
83 rdf:type schema:Person
84 N6783fe0874ae4452aff4dc229ac3ed52 schema:familyName Micciancio
85 schema:givenName Daniele
86 rdf:type schema:Person
87 N93cd9bd140a443e595c0890f5d5d676d schema:name dimensions_id
88 schema:value pub.1120206954
89 rdf:type schema:PropertyValue
90 Nbb13854a331f42b0a622b42a845fbc00 schema:name Springer Nature
91 rdf:type schema:Organisation
92 Nc82a681e677a45f4972c23e890375228 schema:familyName Boldyreva
93 schema:givenName Alexandra
94 rdf:type schema:Person
95 Nd5c684b2096c421ca425212fe5b22e0e rdf:first sg:person.01143152610.86
96 rdf:rest rdf:nil
97 Ndc12a9a7001d4e1cbf052040858b4cf4 rdf:first N4c168c4c0eab40fe97b07a5157ac4416
98 rdf:rest N11513cf1f70e4c469bf228936506d04e
99 Ne304163cfcc94b0096909e760d3b2db9 schema:name Springer Nature - SN SciGraph project
100 rdf:type schema:Organization
101 Neae3dcaace0d4d15b0a614274e09cab3 schema:affiliation grid-institutes:grid.264756.4
102 schema:familyName Zhang
103 schema:givenName Yupeng
104 rdf:type schema:Person
105 Nec9f50151fa2496aa85a3642c43124aa schema:isbn 978-3-030-26953-1
106 978-3-030-26954-8
107 schema:name Advances in Cryptology – CRYPTO 2019
108 rdf:type schema:Book
109 Nf41b44c65ba14b8f9699e32a46e9faa1 schema:name doi
110 schema:value 10.1007/978-3-030-26954-8_24
111 rdf:type schema:PropertyValue
112 Nfcdea07ab879457e8711d7974ac93c7e rdf:first N6783fe0874ae4452aff4dc229ac3ed52
113 rdf:rest rdf:nil
114 Nff9f1522315045ecbe3715f142c6b85b rdf:first sg:person.010450677547.30
115 rdf:rest Nd5c684b2096c421ca425212fe5b22e0e
116 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
117 schema:name Information and Computing Sciences
118 rdf:type schema:DefinedTerm
119 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
120 schema:name Computation Theory and Mathematics
121 rdf:type schema:DefinedTerm
122 sg:person.010450677547.30 schema:affiliation grid-institutes:grid.164295.d
123 schema:familyName Papamanthou
124 schema:givenName Charalampos
125 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010450677547.30
126 rdf:type schema:Person
127 sg:person.01143152610.86 schema:affiliation grid-institutes:grid.47840.3f
128 schema:familyName Song
129 schema:givenName Dawn
130 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01143152610.86
131 rdf:type schema:Person
132 grid-institutes:grid.164295.d schema:alternateName University of Maryland, College Park, USA
133 schema:name University of Maryland, College Park, USA
134 rdf:type schema:Organization
135 grid-institutes:grid.264756.4 schema:alternateName Texas A&M University, College Station, USA
136 schema:name Texas A&M University, College Station, USA
137 University of California, Berkeley, USA
138 rdf:type schema:Organization
139 grid-institutes:grid.47840.3f schema:alternateName University of California, Berkeley, USA
140 schema:name University of California, Berkeley, USA
141 rdf:type schema:Organization
 




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


...