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 Ncbbd858bd7c641e1847f38353a731690
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 N0f38e74ba6f0445ba1702bcb60ce163e
19 schema:genre chapter
20 schema:inLanguage en
21 schema:isAccessibleForFree true
22 schema:isPartOf Nba0e1ce55fdd4580b5acf865de8451df
23 schema:name Multi-precision Squaring for Public-Key Cryptography on Embedded Microprocessors
24 schema:pagination 227-243
25 schema:productId N0b3b2afcd6604d158c2396cb2befb193
26 N7d24590fee3042c28006a73beaf24302
27 Ne6a6f4d6ff654afabb8b7348cbd87942
28 schema:publisher N8c9aa7ca13e54ecbb48bd6fd320608ee
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 N04451fadfbe34b4abe3869a588ec8a9a
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 N04451fadfbe34b4abe3869a588ec8a9a schema:name Springer Nature - SN SciGraph project
39 rdf:type schema:Organization
40 N0b3b2afcd6604d158c2396cb2befb193 schema:name dimensions_id
41 schema:value pub.1028254199
42 rdf:type schema:PropertyValue
43 N0ca4c26b0e2040e58e80749eb2711e3c rdf:first Nb96d870056304c3bb4f8f2f25284162d
44 rdf:rest rdf:nil
45 N0f38e74ba6f0445ba1702bcb60ce163e rdf:first N4e71f344b3ff44af9ec170ccef9bdea3
46 rdf:rest N0ca4c26b0e2040e58e80749eb2711e3c
47 N4897b53921664e2ab8b811acffb6193e rdf:first sg:person.013144776623.84
48 rdf:rest Nc908990c414f4cb1ab04879a1a2f20f0
49 N4e71f344b3ff44af9ec170ccef9bdea3 schema:familyName Paul
50 schema:givenName Goutam
51 rdf:type schema:Person
52 N67a00dd1b1324392b72b6ff7d161a921 rdf:first sg:person.010610076315.82
53 rdf:rest rdf:nil
54 N7d24590fee3042c28006a73beaf24302 schema:name doi
55 schema:value 10.1007/978-3-319-03515-4_15
56 rdf:type schema:PropertyValue
57 N8c9aa7ca13e54ecbb48bd6fd320608ee schema:location Cham
58 schema:name Springer International Publishing
59 rdf:type schema:Organisation
60 Nb96d870056304c3bb4f8f2f25284162d schema:familyName Vaudenay
61 schema:givenName Serge
62 rdf:type schema:Person
63 Nba0e1ce55fdd4580b5acf865de8451df schema:isbn 978-3-319-03514-7
64 978-3-319-03515-4
65 schema:name Progress in Cryptology – INDOCRYPT 2013
66 rdf:type schema:Book
67 Nc908990c414f4cb1ab04879a1a2f20f0 rdf:first sg:person.016515567115.78
68 rdf:rest N67a00dd1b1324392b72b6ff7d161a921
69 Ncbbd858bd7c641e1847f38353a731690 rdf:first sg:person.015101423711.26
70 rdf:rest N4897b53921664e2ab8b811acffb6193e
71 Ne6a6f4d6ff654afabb8b7348cbd87942 schema:name readcube_id
72 schema:value 8698ef4f6d0e135d0eaffb6e2c9d857583254e3aa4acfc400d0fadf25b854b16
73 rdf:type schema:PropertyValue
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)


...