ECC2K-130 on Cell CPUs View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2010

AUTHORS

Joppe W. Bos , Thorsten Kleinjung , Ruben Niederhagen , Peter Schwabe

ABSTRACT

This paper describes an implementation of Pollard’s rho algorithm to compute the elliptic curve discrete logarithm for the Synergistic Processor Elements of the Cell Broadband Engine Architecture. Our implementation targets the elliptic curve discrete logarithm problem defined in the Certicom ECC2K-130 challenge. We compare a bitsliced implementation to a non-bitsliced implementation and describe several optimization techniques for both approaches. In particular, we address the question whether normal-basis or polynomial-basis representation of field elements leads to better performance. We show that using our software the ECC2K-130 challenge can be solved in one year using the Synergistic Processor Units of less than 2700 Sony Playstation 3 gaming consoles. More... »

PAGES

225-242

References to SciGraph publications

  • 2007. Efficient Multiplication Using Type 2 Optimal Normal Bases in ARITHMETIC OF FINITE FIELDS
  • 2009. Batch Binary Edwards in ADVANCES IN CRYPTOLOGY - CRYPTO 2009
  • 2006-05-17. A fast new DES implementation in software in FAST SOFTWARE ENCRYPTION
  • Book

    TITLE

    Progress in Cryptology – AFRICACRYPT 2010

    ISBN

    978-3-642-12677-2
    978-3-642-12678-9

    Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/978-3-642-12678-9_14

    DOI

    http://dx.doi.org/10.1007/978-3-642-12678-9_14

    DIMENSIONS

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


    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/0803", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computer Software", 
            "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": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
              "id": "https://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "Laboratory for Cryptologic Algorithms, EPFL, Station 14, CH-1015, Lausanne, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Bos", 
            "givenName": "Joppe W.", 
            "id": "sg:person.011356726653.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011356726653.68"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "\u00c9cole Polytechnique F\u00e9d\u00e9rale de Lausanne", 
              "id": "https://www.grid.ac/institutes/grid.5333.6", 
              "name": [
                "Laboratory for Cryptologic Algorithms, EPFL, Station 14, CH-1015, Lausanne, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kleinjung", 
            "givenName": "Thorsten", 
            "id": "sg:person.011764222665.65", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011764222665.65"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Eindhoven University of Technology", 
              "id": "https://www.grid.ac/institutes/grid.6852.9", 
              "name": [
                "Department of Electrical Engineering, National Taiwan University, 1 Section 4 Roosevelt Road, 106-70, Taipei, Taiwan", 
                "Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600, Eindhoven, MB, Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Niederhagen", 
            "givenName": "Ruben", 
            "id": "sg:person.016071317521.58", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016071317521.58"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Eindhoven University of Technology", 
              "id": "https://www.grid.ac/institutes/grid.6852.9", 
              "name": [
                "Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600, Eindhoven, MB, Netherlands"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Schwabe", 
            "givenName": "Peter", 
            "id": "sg:person.010637555557.91", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010637555557.91"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-03356-8_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012320763", 
              "https://doi.org/10.1007/978-3-642-03356-8_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0021-9991(67)90047-2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1025057781"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0052352", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028761841", 
              "https://doi.org/10.1007/bfb0052352"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0052352", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1028761841", 
              "https://doi.org/10.1007/bfb0052352"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-73074-3_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1033696916", 
              "https://doi.org/10.1007/978-3-540-73074-3_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1214/aoms/1177705677", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1064400756"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/2006496", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1069694303"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/hpca.2005.26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1094158096"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2010", 
        "datePublishedReg": "2010-01-01", 
        "description": "This paper describes an implementation of Pollard\u2019s rho algorithm to compute the elliptic curve discrete logarithm for the Synergistic Processor Elements of the Cell Broadband Engine Architecture. Our implementation targets the elliptic curve discrete logarithm problem defined in the Certicom ECC2K-130 challenge. We compare a bitsliced implementation to a non-bitsliced implementation and describe several optimization techniques for both approaches. In particular, we address the question whether normal-basis or polynomial-basis representation of field elements leads to better performance. We show that using our software the ECC2K-130 challenge can be solved in one year using the Synergistic Processor Units of less than 2700 Sony Playstation 3 gaming consoles.", 
        "editor": [
          {
            "familyName": "Bernstein", 
            "givenName": "Daniel J.", 
            "type": "Person"
          }, 
          {
            "familyName": "Lange", 
            "givenName": "Tanja", 
            "type": "Person"
          }
        ], 
        "genre": "chapter", 
        "id": "sg:pub.10.1007/978-3-642-12678-9_14", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": {
          "isbn": [
            "978-3-642-12677-2", 
            "978-3-642-12678-9"
          ], 
          "name": "Progress in Cryptology \u2013 AFRICACRYPT 2010", 
          "type": "Book"
        }, 
        "name": "ECC2K-130 on Cell CPUs", 
        "pagination": "225-242", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1050946718"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/978-3-642-12678-9_14"
            ]
          }, 
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "f2b1239cf6266db0085f005ff53afb5dc3849ff78d1316fe8a8506cf63883017"
            ]
          }
        ], 
        "publisher": {
          "location": "Berlin, Heidelberg", 
          "name": "Springer Berlin Heidelberg", 
          "type": "Organisation"
        }, 
        "sameAs": [
          "https://doi.org/10.1007/978-3-642-12678-9_14", 
          "https://app.dimensions.ai/details/publication/pub.1050946718"
        ], 
        "sdDataset": "chapters", 
        "sdDatePublished": "2019-04-16T07:36", 
        "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/0000000357_0000000357/records_99308_00000001.jsonl", 
        "type": "Chapter", 
        "url": "https://link.springer.com/10.1007%2F978-3-642-12678-9_14"
      }
    ]
     

    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-642-12678-9_14'

    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-642-12678-9_14'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-12678-9_14'

    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-642-12678-9_14'


     

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

    119 TRIPLES      23 PREDICATES      34 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/978-3-642-12678-9_14 schema:about anzsrc-for:08
    2 anzsrc-for:0803
    3 schema:author N23f59430d6834b898779d0189a521170
    4 schema:citation sg:pub.10.1007/978-3-540-73074-3_6
    5 sg:pub.10.1007/978-3-642-03356-8_19
    6 sg:pub.10.1007/bfb0052352
    7 https://doi.org/10.1016/0021-9991(67)90047-2
    8 https://doi.org/10.1109/hpca.2005.26
    9 https://doi.org/10.1214/aoms/1177705677
    10 https://doi.org/10.2307/2006496
    11 schema:datePublished 2010
    12 schema:datePublishedReg 2010-01-01
    13 schema:description This paper describes an implementation of Pollard’s rho algorithm to compute the elliptic curve discrete logarithm for the Synergistic Processor Elements of the Cell Broadband Engine Architecture. Our implementation targets the elliptic curve discrete logarithm problem defined in the Certicom ECC2K-130 challenge. We compare a bitsliced implementation to a non-bitsliced implementation and describe several optimization techniques for both approaches. In particular, we address the question whether normal-basis or polynomial-basis representation of field elements leads to better performance. We show that using our software the ECC2K-130 challenge can be solved in one year using the Synergistic Processor Units of less than 2700 Sony Playstation 3 gaming consoles.
    14 schema:editor Nffbe2b1ebb69478caab88b9d88301840
    15 schema:genre chapter
    16 schema:inLanguage en
    17 schema:isAccessibleForFree true
    18 schema:isPartOf N0f995c268d744f11b11f5fe7772dfc7a
    19 schema:name ECC2K-130 on Cell CPUs
    20 schema:pagination 225-242
    21 schema:productId N87f5c2fac9c04ece9fe59655fb903913
    22 Ne10b6c90c8cd4594828f4cc21fe3b50e
    23 Ne47a1c2deac14e29844096a7d1b6ef5e
    24 schema:publisher Na10708059d1745638f46834dfa02d192
    25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050946718
    26 https://doi.org/10.1007/978-3-642-12678-9_14
    27 schema:sdDatePublished 2019-04-16T07:36
    28 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    29 schema:sdPublisher N86256fdf9ea34ca99326ec52e45dc868
    30 schema:url https://link.springer.com/10.1007%2F978-3-642-12678-9_14
    31 sgo:license sg:explorer/license/
    32 sgo:sdDataset chapters
    33 rdf:type schema:Chapter
    34 N0f995c268d744f11b11f5fe7772dfc7a schema:isbn 978-3-642-12677-2
    35 978-3-642-12678-9
    36 schema:name Progress in Cryptology – AFRICACRYPT 2010
    37 rdf:type schema:Book
    38 N10f653148bff40f8a4fbfe7a86962b4e rdf:first Nf91f2af60f9045e18ef1adb68a0b2c93
    39 rdf:rest rdf:nil
    40 N23f59430d6834b898779d0189a521170 rdf:first sg:person.011356726653.68
    41 rdf:rest Nf94a484817f041f7b0454a070c8646d4
    42 N6ed2b6cb022f4636b54294bfafbf440d rdf:first sg:person.010637555557.91
    43 rdf:rest rdf:nil
    44 N86256fdf9ea34ca99326ec52e45dc868 schema:name Springer Nature - SN SciGraph project
    45 rdf:type schema:Organization
    46 N87f5c2fac9c04ece9fe59655fb903913 schema:name dimensions_id
    47 schema:value pub.1050946718
    48 rdf:type schema:PropertyValue
    49 N8a3a7c356a274db88dc91148d6e58bed schema:familyName Bernstein
    50 schema:givenName Daniel J.
    51 rdf:type schema:Person
    52 Na10708059d1745638f46834dfa02d192 schema:location Berlin, Heidelberg
    53 schema:name Springer Berlin Heidelberg
    54 rdf:type schema:Organisation
    55 Nb98efb5da51c4510a6dd2f45b887ae3e rdf:first sg:person.016071317521.58
    56 rdf:rest N6ed2b6cb022f4636b54294bfafbf440d
    57 Ne10b6c90c8cd4594828f4cc21fe3b50e schema:name doi
    58 schema:value 10.1007/978-3-642-12678-9_14
    59 rdf:type schema:PropertyValue
    60 Ne47a1c2deac14e29844096a7d1b6ef5e schema:name readcube_id
    61 schema:value f2b1239cf6266db0085f005ff53afb5dc3849ff78d1316fe8a8506cf63883017
    62 rdf:type schema:PropertyValue
    63 Nf91f2af60f9045e18ef1adb68a0b2c93 schema:familyName Lange
    64 schema:givenName Tanja
    65 rdf:type schema:Person
    66 Nf94a484817f041f7b0454a070c8646d4 rdf:first sg:person.011764222665.65
    67 rdf:rest Nb98efb5da51c4510a6dd2f45b887ae3e
    68 Nffbe2b1ebb69478caab88b9d88301840 rdf:first N8a3a7c356a274db88dc91148d6e58bed
    69 rdf:rest N10f653148bff40f8a4fbfe7a86962b4e
    70 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    71 schema:name Information and Computing Sciences
    72 rdf:type schema:DefinedTerm
    73 anzsrc-for:0803 schema:inDefinedTermSet anzsrc-for:
    74 schema:name Computer Software
    75 rdf:type schema:DefinedTerm
    76 sg:person.010637555557.91 schema:affiliation https://www.grid.ac/institutes/grid.6852.9
    77 schema:familyName Schwabe
    78 schema:givenName Peter
    79 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010637555557.91
    80 rdf:type schema:Person
    81 sg:person.011356726653.68 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
    82 schema:familyName Bos
    83 schema:givenName Joppe W.
    84 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011356726653.68
    85 rdf:type schema:Person
    86 sg:person.011764222665.65 schema:affiliation https://www.grid.ac/institutes/grid.5333.6
    87 schema:familyName Kleinjung
    88 schema:givenName Thorsten
    89 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011764222665.65
    90 rdf:type schema:Person
    91 sg:person.016071317521.58 schema:affiliation https://www.grid.ac/institutes/grid.6852.9
    92 schema:familyName Niederhagen
    93 schema:givenName Ruben
    94 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016071317521.58
    95 rdf:type schema:Person
    96 sg:pub.10.1007/978-3-540-73074-3_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1033696916
    97 https://doi.org/10.1007/978-3-540-73074-3_6
    98 rdf:type schema:CreativeWork
    99 sg:pub.10.1007/978-3-642-03356-8_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012320763
    100 https://doi.org/10.1007/978-3-642-03356-8_19
    101 rdf:type schema:CreativeWork
    102 sg:pub.10.1007/bfb0052352 schema:sameAs https://app.dimensions.ai/details/publication/pub.1028761841
    103 https://doi.org/10.1007/bfb0052352
    104 rdf:type schema:CreativeWork
    105 https://doi.org/10.1016/0021-9991(67)90047-2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025057781
    106 rdf:type schema:CreativeWork
    107 https://doi.org/10.1109/hpca.2005.26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1094158096
    108 rdf:type schema:CreativeWork
    109 https://doi.org/10.1214/aoms/1177705677 schema:sameAs https://app.dimensions.ai/details/publication/pub.1064400756
    110 rdf:type schema:CreativeWork
    111 https://doi.org/10.2307/2006496 schema:sameAs https://app.dimensions.ai/details/publication/pub.1069694303
    112 rdf:type schema:CreativeWork
    113 https://www.grid.ac/institutes/grid.5333.6 schema:alternateName École Polytechnique Fédérale de Lausanne
    114 schema:name Laboratory for Cryptologic Algorithms, EPFL, Station 14, CH-1015, Lausanne, Switzerland
    115 rdf:type schema:Organization
    116 https://www.grid.ac/institutes/grid.6852.9 schema:alternateName Eindhoven University of Technology
    117 schema:name Department of Electrical Engineering, National Taiwan University, 1 Section 4 Roosevelt Road, 106-70, Taipei, Taiwan
    118 Department of Mathematics and Computer Science, Technische Universiteit Eindhoven, P.O. Box 513, 5600, Eindhoven, MB, Netherlands
    119 rdf:type schema:Organization
     




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


    ...