Constant-Size Commitments to Polynomials and Their Applications View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Aniket Kate , Gregory M. Zaverucha , Ian Goldberg

ABSTRACT

We introduce and formally define polynomial commitment schemes, and provide two efficient constructions. A polynomial commitment scheme allows a committer to commit to a polynomial with a short string that can be used by a verifier to confirm claimed evaluations of the committed polynomial. Although the homomorphic commitment schemes in the literature can be used to achieve this goal, the sizes of their commitments are linear in the degree of the committed polynomial. On the other hand, polynomial commitments in our schemes are of constant size (single elements). The overhead of opening a commitment is also constant; even opening multiple evaluations requires only a constant amount of communication overhead. Therefore, our schemes are useful tools to reduce the communication cost in cryptographic protocols. On that front, we apply our polynomial commitment schemes to four problems in cryptography: verifiable secret sharing, zero-knowledge sets, credentials and content extraction signatures. More... »

PAGES

177-194

References to SciGraph publications

  • 1999. Commitment Schemes and Zero-Knowledge Protocols in LECTURES ON DATA SECURITY
  • 2006. Compact E-Cash from Bounded Accumulator in TOPICS IN CRYPTOLOGY – CT-RSA 2007
  • 2010. Concise Mercurial Vector Commitments and Independent Zero-Knowledge Sets with Short Proofs in THEORY OF CRYPTOGRAPHY
  • 2001-05-18. Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing in ADVANCES IN CRYPTOLOGY — CRYPTO ’91
  • 2009. Statistically Hiding Sets in TOPICS IN CRYPTOLOGY – CT-RSA 2009
  • 2004. Efficient Consistency Proofs for Generalized Queries on a Committed Database in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 2008. Practical Anonymous Divisible E-Cash from Bounded Accumulators in FINANCIAL CRYPTOGRAPHY AND DATA SECURITY
  • 2008. Zero-Knowledge Sets with Short Proofs in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2008
  • 2001-07-13. Proactive Secret Sharing Or: How to Cope With Perpetual Leakage in ADVANCES IN CRYPTOLOGY — CRYPT0’ 95
  • 2007. Identity-Based Encryption: How to Decrypt Multiple Ciphertexts Using a Single Decryption Key in PAIRING-BASED CRYPTOGRAPHY – PAIRING 2007
  • 2004. Short Signatures Without Random Oracles in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2004
  • 2005. Accumulators from Bilinear Pairings and Applications in TOPICS IN CRYPTOLOGY – CT-RSA 2005
  • 2004. Efficient Selective-ID Secure Identity-Based Encryption Without Random Oracles in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2004
  • 2005. Mercurial Commitments with Applications to Zero-Knowledge Sets in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2005
  • 2005. Hierarchical Identity Based Encryption with Constant Size Ciphertext in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2005
  • 2002-09-13. Dynamic Accumulators and Application to Efficient Revocation of Anonymous Credentials in ADVANCES IN CRYPTOLOGY — CRYPTO 2002
  • 2006. Independent Zero-Knowledge Sets in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1994. One-Way Accumulators: A Decentralized Alternative to Digital Signatures in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’93
  • 2006. Security Analysis of the Strong Diffie-Hellman Problem in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2006
  • 2002-04-23. Content Extraction Signatures in INFORMATION SECURITY AND CRYPTOLOGY — ICISC 2001
  • 2005. Collusion Resistant Broadcast Encryption with Short Ciphertexts and Private Keys in ADVANCES IN CRYPTOLOGY – CRYPTO 2005
  • 2007. Reducing Trust in the PKG in Identity Based Cryptosystems in ADVANCES IN CRYPTOLOGY - CRYPTO 2007
  • Book

    TITLE

    Advances in Cryptology - ASIACRYPT 2010

    ISBN

    978-3-642-17372-1
    978-3-642-17373-8

    Author Affiliations

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-17373-8_11

    DOI

    http://dx.doi.org/10.1007/978-3-642-17373-8_11

    DIMENSIONS

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


    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/0804", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Data Format", 
            "type": "DefinedTerm"
          }, 
          {
            "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"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "name": [
                "Max Planck Institute for Software Systems (MPI-SWS)"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kate", 
            "givenName": "Aniket", 
            "id": "sg:person.010446465027.39", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010446465027.39"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "name": [
                "Certicom Research"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Zaverucha", 
            "givenName": "Gregory M.", 
            "id": "sg:person.016403156015.00", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016403156015.00"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Waterloo", 
              "id": "https://www.grid.ac/institutes/grid.46078.3d", 
              "name": [
                "University of Waterloo"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Goldberg", 
            "givenName": "Ian", 
            "id": "sg:person.012057510223.72", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012057510223.72"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45861-1_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002852371", 
              "https://doi.org/10.1007/3-540-45861-1_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45861-1_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002852371", 
              "https://doi.org/10.1007/3-540-45861-1_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24676-3_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002863944", 
              "https://doi.org/10.1007/978-3-540-24676-3_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24676-3_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002863944", 
              "https://doi.org/10.1007/978-3-540-24676-3_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48285-7_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004089232", 
              "https://doi.org/10.1007/3-540-48285-7_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11761679_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005196183", 
              "https://doi.org/10.1007/11761679_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11761679_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1005196183", 
              "https://doi.org/10.1007/11761679_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-78967-3_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008533343", 
              "https://doi.org/10.1007/978-3-540-78967-3_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-78967-3_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008533343", 
              "https://doi.org/10.1007/978-3-540-78967-3_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27836-8_87", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014928758", 
              "https://doi.org/10.1007/978-3-540-27836-8_87"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-27836-8_87", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1014928758", 
              "https://doi.org/10.1007/978-3-540-27836-8_87"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46766-1_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021532235", 
              "https://doi.org/10.1007/3-540-46766-1_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46766-1_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021532235", 
              "https://doi.org/10.1007/3-540-46766-1_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11967668_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023178824", 
              "https://doi.org/10.1007/11967668_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11967668_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1023178824", 
              "https://doi.org/10.1007/11967668_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30574-3_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024565237", 
              "https://doi.org/10.1007/978-3-540-30574-3_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-30574-3_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1024565237", 
              "https://doi.org/10.1007/978-3-540-30574-3_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-48969-x_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025122637", 
              "https://doi.org/10.1007/3-540-48969-x_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11799-2_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026007185", 
              "https://doi.org/10.1007/978-3-642-11799-2_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-11799-2_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026007185", 
              "https://doi.org/10.1007/978-3-642-11799-2_30"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11426639_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026821672", 
              "https://doi.org/10.1007/11426639_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11426639_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026821672", 
              "https://doi.org/10.1007/11426639_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73489-5_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026954556", 
              "https://doi.org/10.1007/978-3-540-73489-5_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73489-5_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026954556", 
              "https://doi.org/10.1007/978-3-540-73489-5_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24676-3_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028494825", 
              "https://doi.org/10.1007/978-3-540-24676-3_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24676-3_14", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028494825", 
              "https://doi.org/10.1007/978-3-540-24676-3_14"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11787006_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030613060", 
              "https://doi.org/10.1007/11787006_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11787006_4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030613060", 
              "https://doi.org/10.1007/11787006_4"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/277697.277716", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031837667"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-00862-7_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034393003", 
              "https://doi.org/10.1007/978-3-642-00862-7_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-00862-7_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034393003", 
              "https://doi.org/10.1007/978-3-642-00862-7_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1145/359168.359176", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036015253"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45708-9_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037806224", 
              "https://doi.org/10.1007/3-540-45708-9_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45708-9_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1037806224", 
              "https://doi.org/10.1007/3-540-45708-9_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-85230-8_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1039095984", 
              "https://doi.org/10.1007/978-3-540-85230-8_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74143-5_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041352930", 
              "https://doi.org/10.1007/978-3-540-74143-5_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-74143-5_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041352930", 
              "https://doi.org/10.1007/978-3-540-74143-5_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44750-4_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047548397", 
              "https://doi.org/10.1007/3-540-44750-4_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-44750-4_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047548397", 
              "https://doi.org/10.1007/3-540-44750-4_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11535218_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048846772", 
              "https://doi.org/10.1007/11535218_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11535218_16", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048846772", 
              "https://doi.org/10.1007/11535218_16"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.3233/jcs-2002-10304", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1051261203"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11426639_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053043634", 
              "https://doi.org/10.1007/11426639_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11426639_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1053043634", 
              "https://doi.org/10.1007/11426639_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1976.21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086215657"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1987.4", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086239677"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.1985.64", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1086253451"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/sfcs.2003.1238183", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1095802477"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010", 
        "datePublishedReg": "2010-01-01", 
        "description": "We introduce and formally define polynomial commitment schemes, and provide two efficient constructions. A polynomial commitment scheme allows a committer to commit to a polynomial with a short string that can be used by a verifier to confirm claimed evaluations of the committed polynomial. Although the homomorphic commitment schemes in the literature can be used to achieve this goal, the sizes of their commitments are linear in the degree of the committed polynomial. On the other hand, polynomial commitments in our schemes are of constant size (single elements). The overhead of opening a commitment is also constant; even opening multiple evaluations requires only a constant amount of communication overhead. Therefore, our schemes are useful tools to reduce the communication cost in cryptographic protocols. On that front, we apply our polynomial commitment schemes to four problems in cryptography: verifiable secret sharing, zero-knowledge sets, credentials and content extraction signatures.", 
        "editor": [
          {
            "familyName": "Abe", 
            "givenName": "Masayuki", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-17373-8_11", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-642-17372-1", 
            "978-3-642-17373-8"
          ], 
          "name": "Advances in Cryptology - ASIACRYPT 2010", 
          "type": "Book"
        }, 
        "name": "Constant-Size Commitments to Polynomials and Their Applications", 
        "pagination": "177-194", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1050837469"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-17373-8_11"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "f22b4ab71879c24a4b84ce6048b33d45a7d1fe4651969f9e9e3d08060ca8289c"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-17373-8_11", 
          "https://app.dimensions.ai/details/publication/pub.1050837469"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T08:30", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000364_0000000364/records_72834_00000000.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-17373-8_11"
      }
    ]
     

    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-17373-8_11'

    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-17373-8_11'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-17373-8_11'

    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-17373-8_11'


     

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

    192 TRIPLES      23 PREDICATES      56 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-17373-8_11 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author N7622e1288c3448debc647a8f396bca54
    4 schema:citation sg:pub.10.1007/11426639_25
    5 sg:pub.10.1007/11426639_26
    6 sg:pub.10.1007/11535218_16
    7 sg:pub.10.1007/11761679_1
    8 sg:pub.10.1007/11787006_4
    9 sg:pub.10.1007/11967668_12
    10 sg:pub.10.1007/3-540-44750-4_27
    11 sg:pub.10.1007/3-540-45708-9_5
    12 sg:pub.10.1007/3-540-45861-1_22
    13 sg:pub.10.1007/3-540-46766-1_9
    14 sg:pub.10.1007/3-540-48285-7_24
    15 sg:pub.10.1007/3-540-48969-x_3
    16 sg:pub.10.1007/978-3-540-24676-3_14
    17 sg:pub.10.1007/978-3-540-24676-3_4
    18 sg:pub.10.1007/978-3-540-27836-8_87
    19 sg:pub.10.1007/978-3-540-30574-3_19
    20 sg:pub.10.1007/978-3-540-73489-5_22
    21 sg:pub.10.1007/978-3-540-74143-5_24
    22 sg:pub.10.1007/978-3-540-78967-3_25
    23 sg:pub.10.1007/978-3-540-85230-8_26
    24 sg:pub.10.1007/978-3-642-00862-7_7
    25 sg:pub.10.1007/978-3-642-11799-2_30
    26 https://doi.org/10.1109/sfcs.1976.21
    27 https://doi.org/10.1109/sfcs.1985.64
    28 https://doi.org/10.1109/sfcs.1987.4
    29 https://doi.org/10.1109/sfcs.2003.1238183
    30 https://doi.org/10.1145/277697.277716
    31 https://doi.org/10.1145/359168.359176
    32 https://doi.org/10.3233/jcs-2002-10304
    33 schema:datePublished 2010
    34 schema:datePublishedReg 2010-01-01
    35 schema:description We introduce and formally define polynomial commitment schemes, and provide two efficient constructions. A polynomial commitment scheme allows a committer to commit to a polynomial with a short string that can be used by a verifier to confirm claimed evaluations of the committed polynomial. Although the homomorphic commitment schemes in the literature can be used to achieve this goal, the sizes of their commitments are linear in the degree of the committed polynomial. On the other hand, polynomial commitments in our schemes are of constant size (single elements). The overhead of opening a commitment is also constant; even opening multiple evaluations requires only a constant amount of communication overhead. Therefore, our schemes are useful tools to reduce the communication cost in cryptographic protocols. On that front, we apply our polynomial commitment schemes to four problems in cryptography: verifiable secret sharing, zero-knowledge sets, credentials and content extraction signatures.
    36 schema:editor Nbd23ca1f3a7b438986c270fb8f2d0bf9
    37 schema:genre chapter
    38 schema:inLanguage en
    39 schema:isAccessibleForFree true
    40 schema:isPartOf N333d807086604073b91f188014de2aed
    41 schema:name Constant-Size Commitments to Polynomials and Their Applications
    42 schema:pagination 177-194
    43 schema:productId N7dfb49dc766842d188f7eaacfb8132d8
    44 N884c9a0f8f884045adfe1987d24544b7
    45 Nd6e92b4de0124015a12a8986a62cb964
    46 schema:publisher Nae721d8e66824d20a9d92ef39a2f2bbd
    47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050837469
    48 https://doi.org/10.1007/978-3-642-17373-8_11
    49 schema:sdDatePublished 2019-04-16T08:30
    50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    51 schema:sdPublisher N8d7d85f8293845538ee593fca478ab6e
    52 schema:url https://link.springer.com/10.1007%2F978-3-642-17373-8_11
    53 sgo:license sg:explorer/license/
    54 sgo:sdDataset chapters
    55 rdf:type schema:Chapter
    56 N105cb224211e46cebabb130467722096 schema:familyName Abe
    57 schema:givenName Masayuki
    58 rdf:type schema:Person
    59 N333d807086604073b91f188014de2aed schema:isbn 978-3-642-17372-1
    60 978-3-642-17373-8
    61 schema:name Advances in Cryptology - ASIACRYPT 2010
    62 rdf:type schema:Book
    63 N71cfaf4cf5cd420a856924029f67b363 rdf:first sg:person.012057510223.72
    64 rdf:rest rdf:nil
    65 N7622e1288c3448debc647a8f396bca54 rdf:first sg:person.010446465027.39
    66 rdf:rest Nf2eb9c0f57fd47ce9772c494ba3a1204
    67 N7dfb49dc766842d188f7eaacfb8132d8 schema:name dimensions_id
    68 schema:value pub.1050837469
    69 rdf:type schema:PropertyValue
    70 N884c9a0f8f884045adfe1987d24544b7 schema:name doi
    71 schema:value 10.1007/978-3-642-17373-8_11
    72 rdf:type schema:PropertyValue
    73 N8d7d85f8293845538ee593fca478ab6e schema:name Springer Nature - SN SciGraph project
    74 rdf:type schema:Organization
    75 N95ba619d59af4b3d80b14d91a2a4f785 schema:name Certicom Research
    76 rdf:type schema:Organization
    77 Nae721d8e66824d20a9d92ef39a2f2bbd schema:location Berlin, Heidelberg
    78 schema:name Springer Berlin Heidelberg
    79 rdf:type schema:Organisation
    80 Nb715feb382604c5689ad8dab5fb3370f schema:name Max Planck Institute for Software Systems (MPI-SWS)
    81 rdf:type schema:Organization
    82 Nbd23ca1f3a7b438986c270fb8f2d0bf9 rdf:first N105cb224211e46cebabb130467722096
    83 rdf:rest rdf:nil
    84 Nd6e92b4de0124015a12a8986a62cb964 schema:name readcube_id
    85 schema:value f22b4ab71879c24a4b84ce6048b33d45a7d1fe4651969f9e9e3d08060ca8289c
    86 rdf:type schema:PropertyValue
    87 Nf2eb9c0f57fd47ce9772c494ba3a1204 rdf:first sg:person.016403156015.00
    88 rdf:rest N71cfaf4cf5cd420a856924029f67b363
    89 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    90 schema:name Information and Computing Sciences
    91 rdf:type schema:DefinedTerm
    92 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    93 schema:name Data Format
    94 rdf:type schema:DefinedTerm
    95 sg:person.010446465027.39 schema:affiliation Nb715feb382604c5689ad8dab5fb3370f
    96 schema:familyName Kate
    97 schema:givenName Aniket
    98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010446465027.39
    99 rdf:type schema:Person
    100 sg:person.012057510223.72 schema:affiliation https://www.grid.ac/institutes/grid.46078.3d
    101 schema:familyName Goldberg
    102 schema:givenName Ian
    103 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012057510223.72
    104 rdf:type schema:Person
    105 sg:person.016403156015.00 schema:affiliation N95ba619d59af4b3d80b14d91a2a4f785
    106 schema:familyName Zaverucha
    107 schema:givenName Gregory M.
    108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016403156015.00
    109 rdf:type schema:Person
    110 sg:pub.10.1007/11426639_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1053043634
    111 https://doi.org/10.1007/11426639_25
    112 rdf:type schema:CreativeWork
    113 sg:pub.10.1007/11426639_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026821672
    114 https://doi.org/10.1007/11426639_26
    115 rdf:type schema:CreativeWork
    116 sg:pub.10.1007/11535218_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048846772
    117 https://doi.org/10.1007/11535218_16
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/11761679_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005196183
    120 https://doi.org/10.1007/11761679_1
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/11787006_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030613060
    123 https://doi.org/10.1007/11787006_4
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/11967668_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023178824
    126 https://doi.org/10.1007/11967668_12
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/3-540-44750-4_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047548397
    129 https://doi.org/10.1007/3-540-44750-4_27
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/3-540-45708-9_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037806224
    132 https://doi.org/10.1007/3-540-45708-9_5
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/3-540-45861-1_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002852371
    135 https://doi.org/10.1007/3-540-45861-1_22
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/3-540-46766-1_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021532235
    138 https://doi.org/10.1007/3-540-46766-1_9
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/3-540-48285-7_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004089232
    141 https://doi.org/10.1007/3-540-48285-7_24
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/3-540-48969-x_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025122637
    144 https://doi.org/10.1007/3-540-48969-x_3
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/978-3-540-24676-3_14 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028494825
    147 https://doi.org/10.1007/978-3-540-24676-3_14
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/978-3-540-24676-3_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002863944
    150 https://doi.org/10.1007/978-3-540-24676-3_4
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/978-3-540-27836-8_87 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014928758
    153 https://doi.org/10.1007/978-3-540-27836-8_87
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/978-3-540-30574-3_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1024565237
    156 https://doi.org/10.1007/978-3-540-30574-3_19
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/978-3-540-73489-5_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026954556
    159 https://doi.org/10.1007/978-3-540-73489-5_22
    160 rdf:type schema:CreativeWork
    161 sg:pub.10.1007/978-3-540-74143-5_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041352930
    162 https://doi.org/10.1007/978-3-540-74143-5_24
    163 rdf:type schema:CreativeWork
    164 sg:pub.10.1007/978-3-540-78967-3_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008533343
    165 https://doi.org/10.1007/978-3-540-78967-3_25
    166 rdf:type schema:CreativeWork
    167 sg:pub.10.1007/978-3-540-85230-8_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1039095984
    168 https://doi.org/10.1007/978-3-540-85230-8_26
    169 rdf:type schema:CreativeWork
    170 sg:pub.10.1007/978-3-642-00862-7_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034393003
    171 https://doi.org/10.1007/978-3-642-00862-7_7
    172 rdf:type schema:CreativeWork
    173 sg:pub.10.1007/978-3-642-11799-2_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026007185
    174 https://doi.org/10.1007/978-3-642-11799-2_30
    175 rdf:type schema:CreativeWork
    176 https://doi.org/10.1109/sfcs.1976.21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086215657
    177 rdf:type schema:CreativeWork
    178 https://doi.org/10.1109/sfcs.1985.64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086253451
    179 rdf:type schema:CreativeWork
    180 https://doi.org/10.1109/sfcs.1987.4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1086239677
    181 rdf:type schema:CreativeWork
    182 https://doi.org/10.1109/sfcs.2003.1238183 schema:sameAs https://app.dimensions.ai/details/publication/pub.1095802477
    183 rdf:type schema:CreativeWork
    184 https://doi.org/10.1145/277697.277716 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031837667
    185 rdf:type schema:CreativeWork
    186 https://doi.org/10.1145/359168.359176 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036015253
    187 rdf:type schema:CreativeWork
    188 https://doi.org/10.3233/jcs-2002-10304 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051261203
    189 rdf:type schema:CreativeWork
    190 https://www.grid.ac/institutes/grid.46078.3d schema:alternateName University of Waterloo
    191 schema:name University of Waterloo
    192 rdf:type schema:Organization
     




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


    ...