Multi-precision Squaring for Public-Key Cryptography on Embedded Microprocessors View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2013

AUTHORS

Hwajeong Seo , Zhe Liu , Jongseok Choi , Howon Kim

ABSTRACT

In the paper, we revisit the “Lazy Doubling” (LD) method for multi-precision squaring, which reduces the number of addition operations by deferring the doubling process so that it can be performed on accumulated results. The original LD method has to employ carry-catcher registers to store carry values, which reduces the number of general purpose registers available for optimization of the implementation. Furthermore, the LD method adopts the idea of hybrid multiplication to separate the partial products into several product blocks, which prevents the doubling process to be conducted on fully accumulated intermediate results. To overcome these deficiencies of the LD method and improve the performance of multi-precision squaring, we propose a novel and flexible method named “Sliding Block Doubling” (SBD). The SBD method delays the doubling process till the very end of the partial-product computation and then doubles the result by simply shifting it one bit to the left. In order to further reduce the overhead of doubling, we also optimize the execution process for updating carry values and adopt the product-scanning method for efficient computation of the partial products. Our experimental results on an AVR ATmega128 processor show that the SBD method outperforms state-of-the-art implementations by a factor of between 3.5% and 4.4% for operands ranging from 128 bits to 192 bits. More... »

PAGES

227-243

Book

TITLE

Progress in Cryptology – INDOCRYPT 2013

ISBN

978-3-319-03514-7
978-3-319-03515-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-03515-4_15

DOI

http://dx.doi.org/10.1007/978-3-319-03515-4_15

DIMENSIONS

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


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/0904", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Chemical Engineering", 
        "type": "DefinedTerm"
      }, 
      {
        "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/09", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Engineering", 
        "type": "DefinedTerm"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Pusan National University", 
          "id": "https://www.grid.ac/institutes/grid.262229.f", 
          "name": [
            "School of Computer Science and Engineering, Pusan National University, San-30, Jangjeon-Dong, Geumjeong-Gu, Busan, 609\u2013735, Republic of Korea"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seo", 
        "givenName": "Hwajeong", 
        "id": "sg:person.015101423711.26", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015101423711.26"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Luxembourg", 
          "id": "https://www.grid.ac/institutes/grid.16008.3f", 
          "name": [
            "Laboratory of Algorithmics, Cryptology and Security (LACS), University of Luxembourg, 6, rue R. Coudenhove-Kalergi, L\u20131359, Luxembourg, Kirchberg, Luxembourg"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liu", 
        "givenName": "Zhe", 
        "id": "sg:person.013144776623.84", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013144776623.84"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Pusan National University", 
          "id": "https://www.grid.ac/institutes/grid.262229.f", 
          "name": [
            "School of Computer Science and Engineering, Pusan National University, San-30, Jangjeon-Dong, Geumjeong-Gu, Busan, 609\u2013735, Republic of Korea"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Choi", 
        "givenName": "Jongseok", 
        "id": "sg:person.016515567115.78", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016515567115.78"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Pusan National University", 
          "id": "https://www.grid.ac/institutes/grid.262229.f", 
          "name": [
            "School of Computer Science and Engineering, Pusan National University, San-30, Jangjeon-Dong, Geumjeong-Gu, Busan, 609\u2013735, Republic of Korea"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Kim", 
        "givenName": "Howon", 
        "id": "sg:person.010610076315.82", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010610076315.82"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-540-28632-5_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008174972", 
          "https://doi.org/10.1007/978-3-540-28632-5_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-28632-5_9", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1008174972", 
          "https://doi.org/10.1007/978-3-540-28632-5_9"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-73275-4_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009898538", 
          "https://doi.org/10.1007/978-3-540-73275-4_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-540-73275-4_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1009898538", 
          "https://doi.org/10.1007/978-3-540-73275-4_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1145/359340.359342", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1013337011"
        ], 
        "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/3-540-39568-7_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1029422590", 
          "https://doi.org/10.1007/3-540-39568-7_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1016/j.jss.2012.06.074", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1030997602"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-35416-8_5", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1034940906", 
          "https://doi.org/10.1007/978-3-642-35416-8_5"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11545262_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044926321", 
          "https://doi.org/10.1007/11545262_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/11545262_6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1044926321", 
          "https://doi.org/10.1007/11545262_6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-23951-9_30", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047137953", 
          "https://doi.org/10.1007/978-3-642-23951-9_30"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-642-23951-9_30", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1047137953", 
          "https://doi.org/10.1007/978-3-642-23951-9_30"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1147/sj.294.0526", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1063184115"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "https://doi.org/10.1109/iccsnt.2011.6181997", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1094496856"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2013", 
    "datePublishedReg": "2013-01-01", 
    "description": "In the paper, we revisit the \u201cLazy Doubling\u201d (LD) method for multi-precision squaring, which reduces the number of addition operations by deferring the doubling process so that it can be performed on accumulated results. The original LD method has to employ carry-catcher registers to store carry values, which reduces the number of general purpose registers available for optimization of the implementation. Furthermore, the LD method adopts the idea of hybrid multiplication to separate the partial products into several product blocks, which prevents the doubling process to be conducted on fully accumulated intermediate results. To overcome these deficiencies of the LD method and improve the performance of multi-precision squaring, we propose a novel and flexible method named \u201cSliding Block Doubling\u201d (SBD). The SBD method delays the doubling process till the very end of the partial-product computation and then doubles the result by simply shifting it one bit to the left. In order to further reduce the overhead of doubling, we also optimize the execution process for updating carry values and adopt the product-scanning method for efficient computation of the partial products. Our experimental results on an AVR ATmega128 processor show that the SBD method outperforms state-of-the-art implementations by a factor of between 3.5% and 4.4% for operands ranging from 128 bits to 192 bits.", 
    "editor": [
      {
        "familyName": "Paul", 
        "givenName": "Goutam", 
        "type": "Person"
      }, 
      {
        "familyName": "Vaudenay", 
        "givenName": "Serge", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-03515-4_15", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-03514-7", 
        "978-3-319-03515-4"
      ], 
      "name": "Progress in Cryptology \u2013 INDOCRYPT 2013", 
      "type": "Book"
    }, 
    "name": "Multi-precision Squaring for Public-Key Cryptography on Embedded Microprocessors", 
    "pagination": "227-243", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-03515-4_15"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "8698ef4f6d0e135d0eaffb6e2c9d857583254e3aa4acfc400d0fadf25b854b16"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1028254199"
        ]
      }
    ], 
    "publisher": {
      "location": "Cham", 
      "name": "Springer International Publishing", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-03515-4_15", 
      "https://app.dimensions.ai/details/publication/pub.1028254199"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-15T20:06", 
    "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/0000000001_0000000264/records_8687_00000260.jsonl", 
    "type": "Chapter", 
    "url": "http://link.springer.com/10.1007/978-3-319-03515-4_15"
  }
]
 

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-319-03515-4_15'

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-319-03515-4_15'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-03515-4_15'

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-319-03515-4_15'


 

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

133 TRIPLES      23 PREDICATES      38 URIs      20 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-03515-4_15 schema:about anzsrc-for:09
2 anzsrc-for:0904
3 schema:author Nc9dc3f3103f04407a4cf5b743f4c685a
4 schema:citation sg:pub.10.1007/11545262_6
5 sg:pub.10.1007/3-540-39568-7_5
6 sg:pub.10.1007/978-3-540-28632-5_9
7 sg:pub.10.1007/978-3-540-73275-4_6
8 sg:pub.10.1007/978-3-642-23951-9_30
9 sg:pub.10.1007/978-3-642-35416-8_5
10 https://doi.org/10.1016/j.jss.2012.06.074
11 https://doi.org/10.1090/s0025-5718-1987-0866109-5
12 https://doi.org/10.1109/iccsnt.2011.6181997
13 https://doi.org/10.1145/359340.359342
14 https://doi.org/10.1147/sj.294.0526
15 schema:datePublished 2013
16 schema:datePublishedReg 2013-01-01
17 schema:description In the paper, we revisit the “Lazy Doubling” (LD) method for multi-precision squaring, which reduces the number of addition operations by deferring the doubling process so that it can be performed on accumulated results. The original LD method has to employ carry-catcher registers to store carry values, which reduces the number of general purpose registers available for optimization of the implementation. Furthermore, the LD method adopts the idea of hybrid multiplication to separate the partial products into several product blocks, which prevents the doubling process to be conducted on fully accumulated intermediate results. To overcome these deficiencies of the LD method and improve the performance of multi-precision squaring, we propose a novel and flexible method named “Sliding Block Doubling” (SBD). The SBD method delays the doubling process till the very end of the partial-product computation and then doubles the result by simply shifting it one bit to the left. In order to further reduce the overhead of doubling, we also optimize the execution process for updating carry values and adopt the product-scanning method for efficient computation of the partial products. Our experimental results on an AVR ATmega128 processor show that the SBD method outperforms state-of-the-art implementations by a factor of between 3.5% and 4.4% for operands ranging from 128 bits to 192 bits.
18 schema:editor Nb525f91f96274b60a4bfc2660b9c980d
19 schema:genre chapter
20 schema:inLanguage en
21 schema:isAccessibleForFree true
22 schema:isPartOf N254edbdd63ea45bc929cbc2369f6fd8b
23 schema:name Multi-precision Squaring for Public-Key Cryptography on Embedded Microprocessors
24 schema:pagination 227-243
25 schema:productId N22a8a09e04714410898b3473b88d8f2f
26 N4c87c19515f24c90842b114585d3e752
27 N94e0b176ffc14f4fbade3c9cf2d47f82
28 schema:publisher N189730d98f754722a63d7c7cd73bee9b
29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028254199
30 https://doi.org/10.1007/978-3-319-03515-4_15
31 schema:sdDatePublished 2019-04-15T20:06
32 schema:sdLicense https://scigraph.springernature.com/explorer/license/
33 schema:sdPublisher N32c98ccdd7894afeb572f849572afc9c
34 schema:url http://link.springer.com/10.1007/978-3-319-03515-4_15
35 sgo:license sg:explorer/license/
36 sgo:sdDataset chapters
37 rdf:type schema:Chapter
38 N01f1e0a5588a449fa92eea8d27582752 rdf:first sg:person.016515567115.78
39 rdf:rest Neb603524a4044710a6e86a4388be0e32
40 N189730d98f754722a63d7c7cd73bee9b schema:location Cham
41 schema:name Springer International Publishing
42 rdf:type schema:Organisation
43 N22a8a09e04714410898b3473b88d8f2f schema:name doi
44 schema:value 10.1007/978-3-319-03515-4_15
45 rdf:type schema:PropertyValue
46 N254edbdd63ea45bc929cbc2369f6fd8b schema:isbn 978-3-319-03514-7
47 978-3-319-03515-4
48 schema:name Progress in Cryptology – INDOCRYPT 2013
49 rdf:type schema:Book
50 N32c98ccdd7894afeb572f849572afc9c schema:name Springer Nature - SN SciGraph project
51 rdf:type schema:Organization
52 N4c87c19515f24c90842b114585d3e752 schema:name dimensions_id
53 schema:value pub.1028254199
54 rdf:type schema:PropertyValue
55 N7fc9130723e942acbbe79514e3da125c schema:familyName Paul
56 schema:givenName Goutam
57 rdf:type schema:Person
58 N7fd66e8aebfd42768786a2da31996725 rdf:first sg:person.013144776623.84
59 rdf:rest N01f1e0a5588a449fa92eea8d27582752
60 N94e0b176ffc14f4fbade3c9cf2d47f82 schema:name readcube_id
61 schema:value 8698ef4f6d0e135d0eaffb6e2c9d857583254e3aa4acfc400d0fadf25b854b16
62 rdf:type schema:PropertyValue
63 Nb31b99c61e0547d38944ddb8eaaa2e74 schema:familyName Vaudenay
64 schema:givenName Serge
65 rdf:type schema:Person
66 Nb525f91f96274b60a4bfc2660b9c980d rdf:first N7fc9130723e942acbbe79514e3da125c
67 rdf:rest Nc96c46538e904bfdbb7d3cbefadd6542
68 Nc96c46538e904bfdbb7d3cbefadd6542 rdf:first Nb31b99c61e0547d38944ddb8eaaa2e74
69 rdf:rest rdf:nil
70 Nc9dc3f3103f04407a4cf5b743f4c685a rdf:first sg:person.015101423711.26
71 rdf:rest N7fd66e8aebfd42768786a2da31996725
72 Neb603524a4044710a6e86a4388be0e32 rdf:first sg:person.010610076315.82
73 rdf:rest rdf:nil
74 anzsrc-for:09 schema:inDefinedTermSet anzsrc-for:
75 schema:name Engineering
76 rdf:type schema:DefinedTerm
77 anzsrc-for:0904 schema:inDefinedTermSet anzsrc-for:
78 schema:name Chemical Engineering
79 rdf:type schema:DefinedTerm
80 sg:person.010610076315.82 schema:affiliation https://www.grid.ac/institutes/grid.262229.f
81 schema:familyName Kim
82 schema:givenName Howon
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010610076315.82
84 rdf:type schema:Person
85 sg:person.013144776623.84 schema:affiliation https://www.grid.ac/institutes/grid.16008.3f
86 schema:familyName Liu
87 schema:givenName Zhe
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013144776623.84
89 rdf:type schema:Person
90 sg:person.015101423711.26 schema:affiliation https://www.grid.ac/institutes/grid.262229.f
91 schema:familyName Seo
92 schema:givenName Hwajeong
93 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015101423711.26
94 rdf:type schema:Person
95 sg:person.016515567115.78 schema:affiliation https://www.grid.ac/institutes/grid.262229.f
96 schema:familyName Choi
97 schema:givenName Jongseok
98 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016515567115.78
99 rdf:type schema:Person
100 sg:pub.10.1007/11545262_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044926321
101 https://doi.org/10.1007/11545262_6
102 rdf:type schema:CreativeWork
103 sg:pub.10.1007/3-540-39568-7_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029422590
104 https://doi.org/10.1007/3-540-39568-7_5
105 rdf:type schema:CreativeWork
106 sg:pub.10.1007/978-3-540-28632-5_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008174972
107 https://doi.org/10.1007/978-3-540-28632-5_9
108 rdf:type schema:CreativeWork
109 sg:pub.10.1007/978-3-540-73275-4_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1009898538
110 https://doi.org/10.1007/978-3-540-73275-4_6
111 rdf:type schema:CreativeWork
112 sg:pub.10.1007/978-3-642-23951-9_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047137953
113 https://doi.org/10.1007/978-3-642-23951-9_30
114 rdf:type schema:CreativeWork
115 sg:pub.10.1007/978-3-642-35416-8_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034940906
116 https://doi.org/10.1007/978-3-642-35416-8_5
117 rdf:type schema:CreativeWork
118 https://doi.org/10.1016/j.jss.2012.06.074 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030997602
119 rdf:type schema:CreativeWork
120 https://doi.org/10.1090/s0025-5718-1987-0866109-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022745146
121 rdf:type schema:CreativeWork
122 https://doi.org/10.1109/iccsnt.2011.6181997 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094496856
123 rdf:type schema:CreativeWork
124 https://doi.org/10.1145/359340.359342 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013337011
125 rdf:type schema:CreativeWork
126 https://doi.org/10.1147/sj.294.0526 schema:sameAs https://app.dimensions.ai/details/publication/pub.1063184115
127 rdf:type schema:CreativeWork
128 https://www.grid.ac/institutes/grid.16008.3f schema:alternateName University of Luxembourg
129 schema:name Laboratory of Algorithmics, Cryptology and Security (LACS), University of Luxembourg, 6, rue R. Coudenhove-Kalergi, L–1359, Luxembourg, Kirchberg, Luxembourg
130 rdf:type schema:Organization
131 https://www.grid.ac/institutes/grid.262229.f schema:alternateName Pusan National University
132 schema:name School of Computer Science and Engineering, Pusan National University, San-30, Jangjeon-Dong, Geumjeong-Gu, Busan, 609–735, Republic of Korea
133 rdf:type schema:Organization
 




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


...