Efficient Fixed-base exponentiation and scalar multiplication based on a multiplicative splitting exponent recoding View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-11-12

AUTHORS

Jean-Marc Robert, Christophe Negre, Thomas Plantard

ABSTRACT

Digital signature algorithm (DSA) (resp. ECDSA) involves modular exponentiation (resp. scalar multiplication) of a public and known base by a random one-time exponent. In order to speed up this operation, well-known methods take advantage of the memorization of base powers (resp. base multiples). Best approaches are the Fixed-base radix-R method and the Fixed-base Comb method. In this paper, we present a new approach for storage/online computation trade-off, by using a multiplicative splitting of the digits of the exponent radix-R representation. We adapt classical algorithms for modular exponentiation and scalar multiplication in order to take advantage of the proposed exponent recoding. An analysis of the complexity for practical size shows that our proposed approach involves a lower storage for a given level of online computation. This is confirmed by implementation results showing significant memory saving, up to 3 times for the largest NIST standardized key sizes, compared to the state-of-the-art approaches. More... »

PAGES

1-22

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s13389-018-0196-7

DOI

http://dx.doi.org/10.1007/s13389-018-0196-7

DIMENSIONS

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


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/0801", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Artificial Intelligence and Image Processing", 
        "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": {
          "alternateName": "Montpellier Laboratory of Informatics, Robotics and Microelectronics", 
          "id": "https://www.grid.ac/institutes/grid.464638.b", 
          "name": [
            "Team DALI, Universit\u00e9 de Perpignan Via Domitia, Perpignan, France", 
            "LIRMM, UMR 5506, Universit\u00e9 de Montpellier and CNRS, Montpellier, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Robert", 
        "givenName": "Jean-Marc", 
        "id": "sg:person.015201516147.57", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015201516147.57"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Montpellier Laboratory of Informatics, Robotics and Microelectronics", 
          "id": "https://www.grid.ac/institutes/grid.464638.b", 
          "name": [
            "Team DALI, Universit\u00e9 de Perpignan Via Domitia, Perpignan, France", 
            "LIRMM, UMR 5506, Universit\u00e9 de Montpellier and CNRS, Montpellier, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Negre", 
        "givenName": "Christophe", 
        "id": "sg:person.013345137071.30", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345137071.30"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Wollongong", 
          "id": "https://www.grid.ac/institutes/grid.1007.6", 
          "name": [
            "CCISR, SCIT, University of Wollongong, Wollongong, Australia"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Plantard", 
        "givenName": "Thomas", 
        "id": "sg:person.010324171343.29", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010324171343.29"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/3-540-44499-8_1", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1007259557", 
          "https://doi.org/10.1007/3-540-44499-8_1"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.amc.2004.10.010", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011912875"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-02384-2_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014047662", 
          "https://doi.org/10.1007/978-3-642-02384-2_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-02384-2_21", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014047662", 
          "https://doi.org/10.1007/978-3-642-02384-2_21"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-45353-9_19", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021281712", 
          "https://doi.org/10.1007/3-540-45353-9_19"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-48329-2_16", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021921938", 
          "https://doi.org/10.1007/3-540-48329-2_16"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-48329-2_16", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021921938", 
          "https://doi.org/10.1007/3-540-48329-2_16"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-39799-x_31", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022380878", 
          "https://doi.org/10.1007/3-540-39799-x_31"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0025-5718-1987-0866109-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1022745146"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s13389-016-0134-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026158795", 
          "https://doi.org/10.1007/s13389-016-0134-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/s13389-016-0134-5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1026158795", 
          "https://doi.org/10.1007/s13389-016-0134-5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-76900-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029290922", 
          "https://doi.org/10.1007/978-3-540-76900-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-76900-2", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029290922", 
          "https://doi.org/10.1007/978-3-540-76900-2"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-48658-5_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029692519", 
          "https://doi.org/10.1007/3-540-48658-5_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-48658-5_11", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029692519", 
          "https://doi.org/10.1007/3-540-48658-5_11"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1090/s0025-5718-1985-0777282-x", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041482767"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1006/jagm.1997.0913", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047704368"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-31410-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050575543", 
          "https://doi.org/10.1007/978-3-642-31410-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-31410-0", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1050575543", 
          "https://doi.org/10.1007/978-3-642-31410-0"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-319-55227-9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1084684671", 
          "https://doi.org/10.1007/978-3-319-55227-9"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2018-11-12", 
    "datePublishedReg": "2018-11-12", 
    "description": "Digital signature algorithm (DSA) (resp. ECDSA) involves modular exponentiation (resp. scalar multiplication) of a public and known base by a random one-time exponent. In order to speed up this operation, well-known methods take advantage of the memorization of base powers (resp. base multiples). Best approaches are the Fixed-base radix-R method and the Fixed-base Comb method. In this paper, we present a new approach for storage/online computation trade-off, by using a multiplicative splitting of the digits of the exponent radix-R representation. We adapt classical algorithms for modular exponentiation and scalar multiplication in order to take advantage of the proposed exponent recoding. An analysis of the complexity for practical size shows that our proposed approach involves a lower storage for a given level of online computation. This is confirmed by implementation results showing significant memory saving, up to 3 times for the largest NIST standardized key sizes, compared to the state-of-the-art approaches.", 
    "genre": "research_article", 
    "id": "sg:pub.10.1007/s13389-018-0196-7", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136625", 
        "issn": [
          "2190-8508", 
          "2190-8516"
        ], 
        "name": "Journal of Cryptographic Engineering", 
        "type": "Periodical"
      }
    ], 
    "name": "Efficient Fixed-base exponentiation and scalar multiplication based on a multiplicative splitting exponent recoding", 
    "pagination": "1-22", 
    "productId": [
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "c6c63aa381fd3b8f29553a0f5e9123454abf7dd04c4dc5e21178608d4859fe32"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/s13389-018-0196-7"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1109858645"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/s13389-018-0196-7", 
      "https://app.dimensions.ai/details/publication/pub.1109858645"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2019-04-11T08:07", 
    "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/0000000265_0000000265/records_67391_00000000.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://link.springer.com/10.1007%2Fs13389-018-0196-7"
  }
]
 

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/s13389-018-0196-7'

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/s13389-018-0196-7'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s13389-018-0196-7'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s13389-018-0196-7'


 

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

125 TRIPLES      21 PREDICATES      38 URIs      16 LITERALS      5 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/s13389-018-0196-7 schema:about anzsrc-for:08
2 anzsrc-for:0801
3 schema:author N1fcf9e78ee30443c938fca6b78ad169d
4 schema:citation sg:pub.10.1007/3-540-39799-x_31
5 sg:pub.10.1007/3-540-44499-8_1
6 sg:pub.10.1007/3-540-45353-9_19
7 sg:pub.10.1007/3-540-48329-2_16
8 sg:pub.10.1007/3-540-48658-5_11
9 sg:pub.10.1007/978-3-319-55227-9
10 sg:pub.10.1007/978-3-540-76900-2
11 sg:pub.10.1007/978-3-642-02384-2_21
12 sg:pub.10.1007/978-3-642-31410-0
13 sg:pub.10.1007/s13389-016-0134-5
14 https://doi.org/10.1006/jagm.1997.0913
15 https://doi.org/10.1016/j.amc.2004.10.010
16 https://doi.org/10.1090/s0025-5718-1985-0777282-x
17 https://doi.org/10.1090/s0025-5718-1987-0866109-5
18 schema:datePublished 2018-11-12
19 schema:datePublishedReg 2018-11-12
20 schema:description Digital signature algorithm (DSA) (resp. ECDSA) involves modular exponentiation (resp. scalar multiplication) of a public and known base by a random one-time exponent. In order to speed up this operation, well-known methods take advantage of the memorization of base powers (resp. base multiples). Best approaches are the Fixed-base radix-R method and the Fixed-base Comb method. In this paper, we present a new approach for storage/online computation trade-off, by using a multiplicative splitting of the digits of the exponent radix-R representation. We adapt classical algorithms for modular exponentiation and scalar multiplication in order to take advantage of the proposed exponent recoding. An analysis of the complexity for practical size shows that our proposed approach involves a lower storage for a given level of online computation. This is confirmed by implementation results showing significant memory saving, up to 3 times for the largest NIST standardized key sizes, compared to the state-of-the-art approaches.
21 schema:genre research_article
22 schema:inLanguage en
23 schema:isAccessibleForFree false
24 schema:isPartOf sg:journal.1136625
25 schema:name Efficient Fixed-base exponentiation and scalar multiplication based on a multiplicative splitting exponent recoding
26 schema:pagination 1-22
27 schema:productId N5f144ae58af5485a99e874d97cd46dac
28 N801178a04cb3416287c4469b39c69add
29 N938901a36a954d419bedda836e8d1a0a
30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1109858645
31 https://doi.org/10.1007/s13389-018-0196-7
32 schema:sdDatePublished 2019-04-11T08:07
33 schema:sdLicense https://scigraph.springernature.com/explorer/license/
34 schema:sdPublisher Nf9614026dd7d4b7fbe328760e622fa68
35 schema:url https://link.springer.com/10.1007%2Fs13389-018-0196-7
36 sgo:license sg:explorer/license/
37 sgo:sdDataset articles
38 rdf:type schema:ScholarlyArticle
39 N0b7cb14ffa5c4385b16655d015022f1c rdf:first sg:person.010324171343.29
40 rdf:rest rdf:nil
41 N1fcf9e78ee30443c938fca6b78ad169d rdf:first sg:person.015201516147.57
42 rdf:rest N40c7fb780882444392469a012f167c0a
43 N40c7fb780882444392469a012f167c0a rdf:first sg:person.013345137071.30
44 rdf:rest N0b7cb14ffa5c4385b16655d015022f1c
45 N5f144ae58af5485a99e874d97cd46dac schema:name doi
46 schema:value 10.1007/s13389-018-0196-7
47 rdf:type schema:PropertyValue
48 N801178a04cb3416287c4469b39c69add schema:name readcube_id
49 schema:value c6c63aa381fd3b8f29553a0f5e9123454abf7dd04c4dc5e21178608d4859fe32
50 rdf:type schema:PropertyValue
51 N938901a36a954d419bedda836e8d1a0a schema:name dimensions_id
52 schema:value pub.1109858645
53 rdf:type schema:PropertyValue
54 Nf9614026dd7d4b7fbe328760e622fa68 schema:name Springer Nature - SN SciGraph project
55 rdf:type schema:Organization
56 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
57 schema:name Information and Computing Sciences
58 rdf:type schema:DefinedTerm
59 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
60 schema:name Artificial Intelligence and Image Processing
61 rdf:type schema:DefinedTerm
62 sg:journal.1136625 schema:issn 2190-8508
63 2190-8516
64 schema:name Journal of Cryptographic Engineering
65 rdf:type schema:Periodical
66 sg:person.010324171343.29 schema:affiliation https://www.grid.ac/institutes/grid.1007.6
67 schema:familyName Plantard
68 schema:givenName Thomas
69 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010324171343.29
70 rdf:type schema:Person
71 sg:person.013345137071.30 schema:affiliation https://www.grid.ac/institutes/grid.464638.b
72 schema:familyName Negre
73 schema:givenName Christophe
74 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013345137071.30
75 rdf:type schema:Person
76 sg:person.015201516147.57 schema:affiliation https://www.grid.ac/institutes/grid.464638.b
77 schema:familyName Robert
78 schema:givenName Jean-Marc
79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015201516147.57
80 rdf:type schema:Person
81 sg:pub.10.1007/3-540-39799-x_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022380878
82 https://doi.org/10.1007/3-540-39799-x_31
83 rdf:type schema:CreativeWork
84 sg:pub.10.1007/3-540-44499-8_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1007259557
85 https://doi.org/10.1007/3-540-44499-8_1
86 rdf:type schema:CreativeWork
87 sg:pub.10.1007/3-540-45353-9_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021281712
88 https://doi.org/10.1007/3-540-45353-9_19
89 rdf:type schema:CreativeWork
90 sg:pub.10.1007/3-540-48329-2_16 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021921938
91 https://doi.org/10.1007/3-540-48329-2_16
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/3-540-48658-5_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029692519
94 https://doi.org/10.1007/3-540-48658-5_11
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/978-3-319-55227-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084684671
97 https://doi.org/10.1007/978-3-319-55227-9
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/978-3-540-76900-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029290922
100 https://doi.org/10.1007/978-3-540-76900-2
101 rdf:type schema:CreativeWork
102 sg:pub.10.1007/978-3-642-02384-2_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014047662
103 https://doi.org/10.1007/978-3-642-02384-2_21
104 rdf:type schema:CreativeWork
105 sg:pub.10.1007/978-3-642-31410-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050575543
106 https://doi.org/10.1007/978-3-642-31410-0
107 rdf:type schema:CreativeWork
108 sg:pub.10.1007/s13389-016-0134-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026158795
109 https://doi.org/10.1007/s13389-016-0134-5
110 rdf:type schema:CreativeWork
111 https://doi.org/10.1006/jagm.1997.0913 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047704368
112 rdf:type schema:CreativeWork
113 https://doi.org/10.1016/j.amc.2004.10.010 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011912875
114 rdf:type schema:CreativeWork
115 https://doi.org/10.1090/s0025-5718-1985-0777282-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1041482767
116 rdf:type schema:CreativeWork
117 https://doi.org/10.1090/s0025-5718-1987-0866109-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022745146
118 rdf:type schema:CreativeWork
119 https://www.grid.ac/institutes/grid.1007.6 schema:alternateName University of Wollongong
120 schema:name CCISR, SCIT, University of Wollongong, Wollongong, Australia
121 rdf:type schema:Organization
122 https://www.grid.ac/institutes/grid.464638.b schema:alternateName Montpellier Laboratory of Informatics, Robotics and Microelectronics
123 schema:name LIRMM, UMR 5506, Université de Montpellier and CNRS, Montpellier, France
124 Team DALI, Université de Perpignan Via Domitia, Perpignan, France
125 rdf:type schema:Organization
 




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


...