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 Nd502adf3521e464f9cdd02038c04e77d
    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 Ndb26bc68884744b4abeaa3e90a4ae4b3
    37 schema:genre chapter
    38 schema:inLanguage en
    39 schema:isAccessibleForFree true
    40 schema:isPartOf N36b92d7016ee441db868e6566aba7288
    41 schema:name Constant-Size Commitments to Polynomials and Their Applications
    42 schema:pagination 177-194
    43 schema:productId N15bf1e4be72145a4a6d155a16fb252fd
    44 N7f85a914896b4fe5886562ebc9ac199e
    45 Nf41326a50898486384d5e3b0521770de
    46 schema:publisher N0954b2077c754e479fcf63011393e38d
    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 Neb24c047f1144f6e9bab1e7d00523659
    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 N084c0d369c14415cb98f14a732ca32e3 schema:name Max Planck Institute for Software Systems (MPI-SWS)
    57 rdf:type schema:Organization
    58 N0954b2077c754e479fcf63011393e38d schema:location Berlin, Heidelberg
    59 schema:name Springer Berlin Heidelberg
    60 rdf:type schema:Organisation
    61 N10f6413f914e4be7b577bd8ae38e8fba schema:name Certicom Research
    62 rdf:type schema:Organization
    63 N15bf1e4be72145a4a6d155a16fb252fd schema:name readcube_id
    64 schema:value f22b4ab71879c24a4b84ce6048b33d45a7d1fe4651969f9e9e3d08060ca8289c
    65 rdf:type schema:PropertyValue
    66 N2979e1a821604e009ddda0f15b164d48 rdf:first sg:person.012057510223.72
    67 rdf:rest rdf:nil
    68 N36b92d7016ee441db868e6566aba7288 schema:isbn 978-3-642-17372-1
    69 978-3-642-17373-8
    70 schema:name Advances in Cryptology - ASIACRYPT 2010
    71 rdf:type schema:Book
    72 N4ddad5c4096d47de9644745d141c2718 rdf:first sg:person.016403156015.00
    73 rdf:rest N2979e1a821604e009ddda0f15b164d48
    74 N7f85a914896b4fe5886562ebc9ac199e schema:name dimensions_id
    75 schema:value pub.1050837469
    76 rdf:type schema:PropertyValue
    77 N97df296c78884030810be38b20d185bc schema:familyName Abe
    78 schema:givenName Masayuki
    79 rdf:type schema:Person
    80 Nd502adf3521e464f9cdd02038c04e77d rdf:first sg:person.010446465027.39
    81 rdf:rest N4ddad5c4096d47de9644745d141c2718
    82 Ndb26bc68884744b4abeaa3e90a4ae4b3 rdf:first N97df296c78884030810be38b20d185bc
    83 rdf:rest rdf:nil
    84 Neb24c047f1144f6e9bab1e7d00523659 schema:name Springer Nature - SN SciGraph project
    85 rdf:type schema:Organization
    86 Nf41326a50898486384d5e3b0521770de schema:name doi
    87 schema:value 10.1007/978-3-642-17373-8_11
    88 rdf:type schema:PropertyValue
    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 N084c0d369c14415cb98f14a732ca32e3
    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 N10f6413f914e4be7b577bd8ae38e8fba
    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)


    ...