Batch verification with applications to cryptography and checking View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

1998

AUTHORS

Mihir Bellare , Juan A. Garay , Tal Rabin

ABSTRACT

Let R(·) be a polynomial time-computable boolean relation. Suppose we are given a sequence inst1,..., instn of instances and asked whether it is the case that R(insti)=1 for all i=1,...,n. The naive way to figure out the answer is to compute R(insti) for each i and check that we get 1 each time. But this takes n computations of R. Can one do any better? The above is the “batch verification” problem. We initiate a broad investigation of it. We look at the possibility of designing probabilistic batch verifiers, or tests, for basic mathematical relations R. Our main results are for modular exponentiation, an expensive operation in terms of number of multiplications: here g is some fixed element of a group G and R(x,y)=1 iff gx=y. We find surprisingly fast batch verifiers for this relation. We also find efficient batch verifiers for the degrees of polynomials. The first application is to cryptography, where modular exponentiation is a common component of a large number of protocols, including digital signatures, bit commitment, and zero knowledge. Similarly, the problem of verifying the degrees of polynomials underlies (verifiable) secret sharing, which in turn underlies many secure distributed protocols. The second application is to program checking. We can use batch verification to provide faster batch checkers, in the sense of [20], for modular exponentiation. These checkers also have stronger properties than standard ones, and illustrate how batch verification can not only speed up how we do old things, but also enable us to do new things. More... »

PAGES

170-191

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bfb0054320

DOI

http://dx.doi.org/10.1007/bfb0054320

DIMENSIONS

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


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": "Department of Computer Science & Engineering, University of California at San Diego, Mail Code 0114, 9500 Gilman Drive, 92093, La Jolla, CA, USA", 
          "id": "http://www.grid.ac/institutes/grid.266100.3", 
          "name": [
            "Department of Computer Science & Engineering, University of California at San Diego, Mail Code 0114, 9500 Gilman Drive, 92093, La Jolla, CA, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Bellare", 
        "givenName": "Mihir", 
        "id": "sg:person.011052537334.13", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011052537334.13"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J. Watson Research Center, PO Box 704, 10598, Yorktown Heights, New York, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J. Watson Research Center, PO Box 704, 10598, Yorktown Heights, New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Garay", 
        "givenName": "Juan A.", 
        "id": "sg:person.015655737162.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015655737162.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "IBM T.J. Watson Research Center, PO Box 704, 10598, Yorktown Heights, New York, USA", 
          "id": "http://www.grid.ac/institutes/grid.481554.9", 
          "name": [
            "IBM T.J. Watson Research Center, PO Box 704, 10598, Yorktown Heights, New York, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Rabin", 
        "givenName": "Tal", 
        "id": "sg:person.015473523512.58", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "1998", 
    "datePublishedReg": "1998-01-01", 
    "description": "Let R(\u00b7) be a polynomial time-computable boolean relation. Suppose we are given a sequence inst1,..., instn of instances and asked whether it is the case that R(insti)=1 for all i=1,...,n. The naive way to figure out the answer is to compute R(insti) for each i and check that we get 1 each time. But this takes n computations of R. Can one do any better? The above is the \u201cbatch verification\u201d problem. We initiate a broad investigation of it. We look at the possibility of designing probabilistic batch verifiers, or tests, for basic mathematical relations R. Our main results are for modular exponentiation, an expensive operation in terms of number of multiplications: here g is some fixed element of a group G and R(x,y)=1 iff gx=y. We find surprisingly fast batch verifiers for this relation. We also find efficient batch verifiers for the degrees of polynomials. The first application is to cryptography, where modular exponentiation is a common component of a large number of protocols, including digital signatures, bit commitment, and zero knowledge. Similarly, the problem of verifying the degrees of polynomials underlies (verifiable) secret sharing, which in turn underlies many secure distributed protocols. The second application is to program checking. We can use batch verification to provide faster batch checkers, in the sense of [20], for modular exponentiation. These checkers also have stronger properties than standard ones, and illustrate how batch verification can not only speed up how we do old things, but also enable us to do new things.", 
    "editor": [
      {
        "familyName": "Lucchesi", 
        "givenName": "Cl\u00e1udio L.", 
        "type": "Person"
      }, 
      {
        "familyName": "Moura", 
        "givenName": "Arnaldo V.", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0054320", 
    "inLanguage": "en", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64275-6", 
        "978-3-540-69715-2"
      ], 
      "name": "LATIN'98: Theoretical Informatics", 
      "type": "Book"
    }, 
    "keywords": [
      "batch verification", 
      "modular exponentiation", 
      "digital signature", 
      "secret sharing", 
      "program checking", 
      "expensive operation", 
      "naive way", 
      "verifier", 
      "cryptography", 
      "exponentiation", 
      "checker", 
      "verification", 
      "bit commitment", 
      "relation R.", 
      "terms of number", 
      "things", 
      "Boolean relations", 
      "large number", 
      "applications", 
      "checking", 
      "second application", 
      "sharing", 
      "protocol", 
      "new things", 
      "computation", 
      "standard ones", 
      "stronger property", 
      "degree of polynomial", 
      "first application", 
      "old things", 
      "instances", 
      "multiplication", 
      "group G", 
      "operation", 
      "common component", 
      "number", 
      "way", 
      "answers", 
      "broader investigation", 
      "knowledge", 
      "main results", 
      "signatures", 
      "one", 
      "terms", 
      "time", 
      "problem", 
      "polynomials", 
      "sense", 
      "components", 
      "results", 
      "elements", 
      "possibility", 
      "degree", 
      "R.", 
      "relation", 
      "cases", 
      "properties", 
      "GX", 
      "commitment", 
      "test", 
      "investigation", 
      "underlies"
    ], 
    "name": "Batch verification with applications to cryptography and checking", 
    "pagination": "170-191", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1005108675"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0054320"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0054320", 
      "https://app.dimensions.ai/details/publication/pub.1005108675"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-10T10:37", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/chapter/chapter_124.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0054320"
  }
]
 

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/bfb0054320'

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/bfb0054320'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bfb0054320'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bfb0054320'


 

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

144 TRIPLES      23 PREDICATES      88 URIs      81 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0054320 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nd156064830c34466877110bed794825a
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description Let R(·) be a polynomial time-computable boolean relation. Suppose we are given a sequence inst1,..., instn of instances and asked whether it is the case that R(insti)=1 for all i=1,...,n. The naive way to figure out the answer is to compute R(insti) for each i and check that we get 1 each time. But this takes n computations of R. Can one do any better? The above is the “batch verification” problem. We initiate a broad investigation of it. We look at the possibility of designing probabilistic batch verifiers, or tests, for basic mathematical relations R. Our main results are for modular exponentiation, an expensive operation in terms of number of multiplications: here g is some fixed element of a group G and R(x,y)=1 iff gx=y. We find surprisingly fast batch verifiers for this relation. We also find efficient batch verifiers for the degrees of polynomials. The first application is to cryptography, where modular exponentiation is a common component of a large number of protocols, including digital signatures, bit commitment, and zero knowledge. Similarly, the problem of verifying the degrees of polynomials underlies (verifiable) secret sharing, which in turn underlies many secure distributed protocols. The second application is to program checking. We can use batch verification to provide faster batch checkers, in the sense of [20], for modular exponentiation. These checkers also have stronger properties than standard ones, and illustrate how batch verification can not only speed up how we do old things, but also enable us to do new things.
7 schema:editor Nfd1984a49b984eebad9d730f00532c19
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree false
11 schema:isPartOf N09e45a94cddf49e3b4829535e65d2224
12 schema:keywords Boolean relations
13 GX
14 R.
15 answers
16 applications
17 batch verification
18 bit commitment
19 broader investigation
20 cases
21 checker
22 checking
23 commitment
24 common component
25 components
26 computation
27 cryptography
28 degree
29 degree of polynomial
30 digital signature
31 elements
32 expensive operation
33 exponentiation
34 first application
35 group G
36 instances
37 investigation
38 knowledge
39 large number
40 main results
41 modular exponentiation
42 multiplication
43 naive way
44 new things
45 number
46 old things
47 one
48 operation
49 polynomials
50 possibility
51 problem
52 program checking
53 properties
54 protocol
55 relation
56 relation R.
57 results
58 second application
59 secret sharing
60 sense
61 sharing
62 signatures
63 standard ones
64 stronger property
65 terms
66 terms of number
67 test
68 things
69 time
70 underlies
71 verification
72 verifier
73 way
74 schema:name Batch verification with applications to cryptography and checking
75 schema:pagination 170-191
76 schema:productId N90c2b2de05944a8990616f0bb0201815
77 Ne5f4855d9bc4457ab7783d4611a0ba64
78 schema:publisher Ncb333082478d482086620aaaf9e56fcf
79 schema:sameAs https://app.dimensions.ai/details/publication/pub.1005108675
80 https://doi.org/10.1007/bfb0054320
81 schema:sdDatePublished 2022-05-10T10:37
82 schema:sdLicense https://scigraph.springernature.com/explorer/license/
83 schema:sdPublisher N85969650b5be475c857e703df40ee8be
84 schema:url https://doi.org/10.1007/bfb0054320
85 sgo:license sg:explorer/license/
86 sgo:sdDataset chapters
87 rdf:type schema:Chapter
88 N09e45a94cddf49e3b4829535e65d2224 schema:isbn 978-3-540-64275-6
89 978-3-540-69715-2
90 schema:name LATIN'98: Theoretical Informatics
91 rdf:type schema:Book
92 N530e9c3327cb42b8a0c31d64e5fa1b0b rdf:first Nd216d91b081e4f87b232da25d79363ec
93 rdf:rest rdf:nil
94 N5b5d95f6c9084816897a5144bb8cf0d5 rdf:first sg:person.015473523512.58
95 rdf:rest rdf:nil
96 N85969650b5be475c857e703df40ee8be schema:name Springer Nature - SN SciGraph project
97 rdf:type schema:Organization
98 N90c2b2de05944a8990616f0bb0201815 schema:name dimensions_id
99 schema:value pub.1005108675
100 rdf:type schema:PropertyValue
101 Nafed94021bf0414ab876252e01380995 rdf:first sg:person.015655737162.07
102 rdf:rest N5b5d95f6c9084816897a5144bb8cf0d5
103 Nb9b84f3e040c4c0384a38b18b2015c97 schema:familyName Lucchesi
104 schema:givenName Cláudio L.
105 rdf:type schema:Person
106 Ncb333082478d482086620aaaf9e56fcf schema:name Springer Nature
107 rdf:type schema:Organisation
108 Nd156064830c34466877110bed794825a rdf:first sg:person.011052537334.13
109 rdf:rest Nafed94021bf0414ab876252e01380995
110 Nd216d91b081e4f87b232da25d79363ec schema:familyName Moura
111 schema:givenName Arnaldo V.
112 rdf:type schema:Person
113 Ne5f4855d9bc4457ab7783d4611a0ba64 schema:name doi
114 schema:value 10.1007/bfb0054320
115 rdf:type schema:PropertyValue
116 Nfd1984a49b984eebad9d730f00532c19 rdf:first Nb9b84f3e040c4c0384a38b18b2015c97
117 rdf:rest N530e9c3327cb42b8a0c31d64e5fa1b0b
118 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
119 schema:name Information and Computing Sciences
120 rdf:type schema:DefinedTerm
121 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
122 schema:name Computation Theory and Mathematics
123 rdf:type schema:DefinedTerm
124 sg:person.011052537334.13 schema:affiliation grid-institutes:grid.266100.3
125 schema:familyName Bellare
126 schema:givenName Mihir
127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011052537334.13
128 rdf:type schema:Person
129 sg:person.015473523512.58 schema:affiliation grid-institutes:grid.481554.9
130 schema:familyName Rabin
131 schema:givenName Tal
132 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58
133 rdf:type schema:Person
134 sg:person.015655737162.07 schema:affiliation grid-institutes:grid.481554.9
135 schema:familyName Garay
136 schema:givenName Juan A.
137 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015655737162.07
138 rdf:type schema:Person
139 grid-institutes:grid.266100.3 schema:alternateName Department of Computer Science & Engineering, University of California at San Diego, Mail Code 0114, 9500 Gilman Drive, 92093, La Jolla, CA, USA
140 schema:name Department of Computer Science & Engineering, University of California at San Diego, Mail Code 0114, 9500 Gilman Drive, 92093, La Jolla, CA, USA
141 rdf:type schema:Organization
142 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research Center, PO Box 704, 10598, Yorktown Heights, New York, USA
143 schema:name IBM T.J. Watson Research Center, PO Box 704, 10598, Yorktown Heights, New York, USA
144 rdf:type schema:Organization
 




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


...