Fast batch verification for modular exponentiation and digital signatures View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

1998

AUTHORS

Mihir Bellare , Juan A. Garay , Tal Rabin

ABSTRACT

Many tasks in cryptography (e.g., digital signature verification) call for verification of a basic operation like modular exponentiation in some group: given (g, x, y) check that gx = y. This is typically done by re-computing gx and checking we get y. We would like to do it differently, and faster. The approach we use is batching. Focusing first on the basic modular exponentiation operation, we provide some probabilistic batch verifiers, or tests, that verify a sequence of modular exponentiations significantly faster than the naive re-computation method. This yields speedups for several verification tasks that involve modular exponentiations. Focusing specifically on digital signatures, we then suggest a weaker notion of (batch) verification which we call “screening.” It seems useful for many usages of signatures, and has the advantage that it can be done very fast; in particular, we show how to screen a sequence of RSA signatures at the cost of one RSA verification plus hashing. More... »

PAGES

236-250

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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": "Dept. of Computer Science & Engineering, University of California at San Diego, 9500 Gilman Drive, 92093, La Jolla, California, USA", 
          "id": "http://www.grid.ac/institutes/grid.266100.3", 
          "name": [
            "Dept. of Computer Science & Engineering, University of California at San Diego, 9500 Gilman Drive, 92093, La Jolla, California, 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": "Many tasks in cryptography (e.g., digital signature verification) call for verification of a basic operation like modular exponentiation in some group: given (g, x, y) check that gx = y. This is typically done by re-computing gx and checking we get y. We would like to do it differently, and faster. The approach we use is batching. Focusing first on the basic modular exponentiation operation, we provide some probabilistic batch verifiers, or tests, that verify a sequence of modular exponentiations significantly faster than the naive re-computation method. This yields speedups for several verification tasks that involve modular exponentiations. Focusing specifically on digital signatures, we then suggest a weaker notion of (batch) verification which we call \u201cscreening.\u201d It seems useful for many usages of signatures, and has the advantage that it can be done very fast; in particular, we show how to screen a sequence of RSA signatures at the cost of one RSA verification plus hashing.", 
    "editor": [
      {
        "familyName": "Nyberg", 
        "givenName": "Kaisa", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/bfb0054130", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-64518-4", 
        "978-3-540-69795-4"
      ], 
      "name": "Advances in Cryptology \u2014 EUROCRYPT'98", 
      "type": "Book"
    }, 
    "keywords": [
      "modular exponentiation", 
      "digital signature", 
      "modular exponentiation operation", 
      "batch verification", 
      "exponentiation operation", 
      "RSA signatures", 
      "verification task", 
      "basic operations", 
      "exponentiation", 
      "verification", 
      "weaker notion", 
      "task", 
      "cryptography", 
      "hashing", 
      "verifier", 
      "speedup", 
      "operation", 
      "usage", 
      "signatures", 
      "cost", 
      "check", 
      "advantages", 
      "sequence", 
      "method", 
      "notion", 
      "GX", 
      "test", 
      "group", 
      "approach"
    ], 
    "name": "Fast batch verification for modular exponentiation and digital signatures", 
    "pagination": "236-250", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1007628411"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bfb0054130"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/bfb0054130", 
      "https://app.dimensions.ai/details/publication/pub.1007628411"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-05-20T07:45", 
    "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_310.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/bfb0054130"
  }
]
 

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

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

Turtle is a human-readable linked data format.

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

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

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


 

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

106 TRIPLES      23 PREDICATES      55 URIs      48 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bfb0054130 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 schema:author Nc8a7b691c40546369dae817a2b6560f3
4 schema:datePublished 1998
5 schema:datePublishedReg 1998-01-01
6 schema:description Many tasks in cryptography (e.g., digital signature verification) call for verification of a basic operation like modular exponentiation in some group: given (g, x, y) check that gx = y. This is typically done by re-computing gx and checking we get y. We would like to do it differently, and faster. The approach we use is batching. Focusing first on the basic modular exponentiation operation, we provide some probabilistic batch verifiers, or tests, that verify a sequence of modular exponentiations significantly faster than the naive re-computation method. This yields speedups for several verification tasks that involve modular exponentiations. Focusing specifically on digital signatures, we then suggest a weaker notion of (batch) verification which we call “screening.” It seems useful for many usages of signatures, and has the advantage that it can be done very fast; in particular, we show how to screen a sequence of RSA signatures at the cost of one RSA verification plus hashing.
7 schema:editor N5d930e0bf894411a8d88248b5027d700
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nafc0235df6e5471893cd5f2ea2d87679
12 schema:keywords GX
13 RSA signatures
14 advantages
15 approach
16 basic operations
17 batch verification
18 check
19 cost
20 cryptography
21 digital signature
22 exponentiation
23 exponentiation operation
24 group
25 hashing
26 method
27 modular exponentiation
28 modular exponentiation operation
29 notion
30 operation
31 sequence
32 signatures
33 speedup
34 task
35 test
36 usage
37 verification
38 verification task
39 verifier
40 weaker notion
41 schema:name Fast batch verification for modular exponentiation and digital signatures
42 schema:pagination 236-250
43 schema:productId N0e9b8a913f5248ddb25982c697695275
44 N1ca7ef50dc39429781531b5a7ef3677e
45 schema:publisher N37ec90cc52734c729af8f05eec4f662c
46 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007628411
47 https://doi.org/10.1007/bfb0054130
48 schema:sdDatePublished 2022-05-20T07:45
49 schema:sdLicense https://scigraph.springernature.com/explorer/license/
50 schema:sdPublisher N851e528df01d4684ac0d5c31fe5fa145
51 schema:url https://doi.org/10.1007/bfb0054130
52 sgo:license sg:explorer/license/
53 sgo:sdDataset chapters
54 rdf:type schema:Chapter
55 N0bb61dc16acc4d1ebce1794b27f9a112 rdf:first sg:person.015473523512.58
56 rdf:rest rdf:nil
57 N0e9b8a913f5248ddb25982c697695275 schema:name dimensions_id
58 schema:value pub.1007628411
59 rdf:type schema:PropertyValue
60 N173e56b0d4aa4bababece40b91a460c8 schema:familyName Nyberg
61 schema:givenName Kaisa
62 rdf:type schema:Person
63 N1ca7ef50dc39429781531b5a7ef3677e schema:name doi
64 schema:value 10.1007/bfb0054130
65 rdf:type schema:PropertyValue
66 N37ec90cc52734c729af8f05eec4f662c schema:name Springer Nature
67 rdf:type schema:Organisation
68 N5d930e0bf894411a8d88248b5027d700 rdf:first N173e56b0d4aa4bababece40b91a460c8
69 rdf:rest rdf:nil
70 N851e528df01d4684ac0d5c31fe5fa145 schema:name Springer Nature - SN SciGraph project
71 rdf:type schema:Organization
72 N898aee292aa04331b3187726178ce206 rdf:first sg:person.015655737162.07
73 rdf:rest N0bb61dc16acc4d1ebce1794b27f9a112
74 Nafc0235df6e5471893cd5f2ea2d87679 schema:isbn 978-3-540-64518-4
75 978-3-540-69795-4
76 schema:name Advances in Cryptology — EUROCRYPT'98
77 rdf:type schema:Book
78 Nc8a7b691c40546369dae817a2b6560f3 rdf:first sg:person.011052537334.13
79 rdf:rest N898aee292aa04331b3187726178ce206
80 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
81 schema:name Information and Computing Sciences
82 rdf:type schema:DefinedTerm
83 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
84 schema:name Computation Theory and Mathematics
85 rdf:type schema:DefinedTerm
86 sg:person.011052537334.13 schema:affiliation grid-institutes:grid.266100.3
87 schema:familyName Bellare
88 schema:givenName Mihir
89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011052537334.13
90 rdf:type schema:Person
91 sg:person.015473523512.58 schema:affiliation grid-institutes:grid.481554.9
92 schema:familyName Rabin
93 schema:givenName Tal
94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015473523512.58
95 rdf:type schema:Person
96 sg:person.015655737162.07 schema:affiliation grid-institutes:grid.481554.9
97 schema:familyName Garay
98 schema:givenName Juan A.
99 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015655737162.07
100 rdf:type schema:Person
101 grid-institutes:grid.266100.3 schema:alternateName Dept. of Computer Science & Engineering, University of California at San Diego, 9500 Gilman Drive, 92093, La Jolla, California, USA
102 schema:name Dept. of Computer Science & Engineering, University of California at San Diego, 9500 Gilman Drive, 92093, La Jolla, California, USA
103 rdf:type schema:Organization
104 grid-institutes:grid.481554.9 schema:alternateName IBM T.J. Watson Research Center, PO Box 704, 10598, Yorktown Heights, New York, USA
105 schema:name IBM T.J. Watson Research Center, PO Box 704, 10598, Yorktown Heights, New York, USA
106 rdf:type schema:Organization
 




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


...