Ontology type: schema:Chapter Open Access: True
2015
AUTHORSHwajeong Seo , Zhe Liu , Johann Großschädl , Jongseok Choi , Howon Kim
ABSTRACTMontgomery modular multiplication constitutes the “arithmetic foundation” of modern public-key cryptography with applications ranging from RSA, DSA and Diffie-Hellman over elliptic curve schemes to pairing-based cryptosystems. The increased prevalence of SIMD-type instructions in commodity processors (e.g. Intel SSE, ARM NEON) has initiated a massive body of research on vector-parallel implementations of Montgomery modular multiplication. In this paper, we introduce the Cascade Operand Scanning (COS) method to speed up multi-precision multiplication on SIMD architectures. We developed the COS technique with the goal of reducing Read-After-Write (RAW) dependencies in the propagation of carries, which also reduces the number of pipeline stalls (i.e. bubbles). The COS method operates on 32-bit words in a row-wise fashion (similar to the operand-scanning method) and does not require a “non-canonical” representation of operands with a reduced radix. We show that two COS computations can be “coarsely” integrated into an efficient vectorized variant of Montgomery multiplication, which we call Coarsely Integrated Cascade Operand Scanning (CICOS) method. Due to our sophisticated instruction scheduling, the CICOS method reaches record-setting execution times for Montgomery modular multiplication on ARM-NEON platforms. Detailed benchmarking results obtained on an ARM Cortex-A9 and Cortex-A15 processors show that the proposed CICOS method outperforms Bos et al’s implementation from SAC 2013 by up to 57 % (A9) and 40 % (A15), respectively. More... »
PAGES328-342
Information Security and Cryptology - ICISC 2014
ISBN
978-3-319-15942-3
978-3-319-15943-0
http://scigraph.springernature.com/pub.10.1007/978-3-319-15943-0_20
DOIhttp://dx.doi.org/10.1007/978-3-319-15943-0_20
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1024476057
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/1006",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Computer Hardware",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/10",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Technology",
"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. Kirchberg, 1359\u00a0Luxembourg-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": "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. Kirchberg, 1359\u00a0Luxembourg-Kirchberg, Luxembourg"
],
"type": "Organization"
},
"familyName": "Gro\u00dfsch\u00e4dl",
"givenName": "Johann",
"id": "sg:person.011275441722.34",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011275441722.34"
],
"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-662-43414-7_24",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006581738",
"https://doi.org/10.1007/978-3-662-43414-7_24"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-319-04852-9_1",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1017542132",
"https://doi.org/10.1007/978-3-319-04852-9_1"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-33027-8_19",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1030639334",
"https://doi.org/10.1007/978-3-642-33027-8_19"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-31662-3_9",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032931092",
"https://doi.org/10.1007/978-3-642-31662-3_9"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-38980-1_20",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036018547",
"https://doi.org/10.1007/978-3-642-38980-1_20"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-38980-1_20",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1036018547",
"https://doi.org/10.1007/978-3-642-38980-1_20"
],
"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": "sg:pub.10.1007/978-3-642-14390-8_50",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041484288",
"https://doi.org/10.1007/978-3-642-14390-8_50"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-14390-8_50",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1041484288",
"https://doi.org/10.1007/978-3-642-14390-8_50"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-642-40588-4_10",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048398256",
"https://doi.org/10.1007/978-3-642-40588-4_10"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/3-540-47721-7_24",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1052590106",
"https://doi.org/10.1007/3-540-47721-7_24"
],
"type": "CreativeWork"
}
],
"datePublished": "2015",
"datePublishedReg": "2015-01-01",
"description": "Montgomery modular multiplication constitutes the \u201carithmetic foundation\u201d of modern public-key cryptography with applications ranging from RSA, DSA and Diffie-Hellman over elliptic curve schemes to pairing-based cryptosystems. The increased prevalence of SIMD-type instructions in commodity processors (e.g. Intel SSE, ARM NEON) has initiated a massive body of research on vector-parallel implementations of Montgomery modular multiplication. In this paper, we introduce the Cascade Operand Scanning (COS) method to speed up multi-precision multiplication on SIMD architectures. We developed the COS technique with the goal of reducing Read-After-Write (RAW) dependencies in the propagation of carries, which also reduces the number of pipeline stalls (i.e. bubbles). The COS method operates on 32-bit words in a row-wise fashion (similar to the operand-scanning method) and does not require a \u201cnon-canonical\u201d representation of operands with a reduced radix. We show that two COS computations can be \u201ccoarsely\u201d integrated into an efficient vectorized variant of Montgomery multiplication, which we call Coarsely Integrated Cascade Operand Scanning (CICOS) method. Due to our sophisticated instruction scheduling, the CICOS method reaches record-setting execution times for Montgomery modular multiplication on ARM-NEON platforms. Detailed benchmarking results obtained on an ARM Cortex-A9 and Cortex-A15 processors show that the proposed CICOS method outperforms Bos et al\u2019s implementation from SAC 2013 by up\u00a0to 57\u00a0% (A9) and 40\u00a0% (A15), respectively.",
"editor": [
{
"familyName": "Lee",
"givenName": "Jooyoung",
"type": "Person"
},
{
"familyName": "Kim",
"givenName": "Jongsung",
"type": "Person"
}
],
"genre": "chapter",
"id": "sg:pub.10.1007/978-3-319-15943-0_20",
"inLanguage": [
"en"
],
"isAccessibleForFree": true,
"isPartOf": {
"isbn": [
"978-3-319-15942-3",
"978-3-319-15943-0"
],
"name": "Information Security and Cryptology - ICISC 2014",
"type": "Book"
},
"name": "Montgomery Modular Multiplication on ARM-NEON Revisited",
"pagination": "328-342",
"productId": [
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/978-3-319-15943-0_20"
]
},
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"749ade6bc35aee7bb834ed2c8745a92ff59ec2ee73681c4d883320e04d8a82c6"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1024476057"
]
}
],
"publisher": {
"location": "Cham",
"name": "Springer International Publishing",
"type": "Organisation"
},
"sameAs": [
"https://doi.org/10.1007/978-3-319-15943-0_20",
"https://app.dimensions.ai/details/publication/pub.1024476057"
],
"sdDataset": "chapters",
"sdDatePublished": "2019-04-15T23:52",
"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_8697_00000258.jsonl",
"type": "Chapter",
"url": "http://link.springer.com/10.1007/978-3-319-15943-0_20"
}
]Download the RDF metadata as: json-ld nt turtle xml License info
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-15943-0_20'
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-15943-0_20'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-15943-0_20'
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-15943-0_20'
This table displays all metadata directly associated to this object as RDF triples.
136 TRIPLES
23 PREDICATES
36 URIs
20 LITERALS
8 BLANK NODES