Itoh-Tsujii Inversion in Standard Basis and Its Application in Cryptography and Codes View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2002-02

AUTHORS

Jorge Guajardo, Christof Paar

ABSTRACT

This contribution is concerned with a generalization of Itoh and Tsujii's algorithm for inversion in extension fields . Unlike the original algorithm, the method introduced here uses a standard (or polynomial) basis representation. The inversion method is generalized for standard basis representation and relevant complexity expressions are established, consisting of the number of extension field multiplications and exponentiations. As the main contribution, for three important classes of fields we show that the Frobenius map can be explored to perform the exponentiations required for the inversion algorithm efficiently. As an important consequence, Itoh and Tsujii's inversion method shows almost the same practical complexity for standard basis as for normal basis representation for the field classes considered. More... »

PAGES

207-216

References to SciGraph publications

  • 1989-10. Hyperelliptic cryptosystems in JOURNAL OF CRYPTOLOGY
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1023/a:1013860532636

    DOI

    http://dx.doi.org/10.1023/a:1013860532636

    DIMENSIONS

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


    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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Worcester Polytechnic Institute", 
              "id": "https://www.grid.ac/institutes/grid.268323.e", 
              "name": [
                "ECE Department, Worcester Polytechnic Institute, 100 Institute Road, 01609, Worcester, MA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Guajardo", 
            "givenName": "Jorge", 
            "id": "sg:person.07607775635.21", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07607775635.21"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Worcester Polytechnic Institute", 
              "id": "https://www.grid.ac/institutes/grid.268323.e", 
              "name": [
                "ECE Department, Worcester Polytechnic Institute, 100 Institute Road, 01609, Worcester, MA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Paar", 
            "givenName": "Christof", 
            "id": "sg:person.016666667155.68", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016666667155.68"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "https://doi.org/10.1016/0890-5401(89)90045-x", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008396396"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1016/0020-0190(91)90219-8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008774178"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02252872", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008777174", 
              "https://doi.org/10.1007/bf02252872"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02252872", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008777174", 
              "https://doi.org/10.1007/bf02252872"
            ], 
            "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": "https://doi.org/10.1016/0890-5401(88)90024-7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1022913144"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/12.156539", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061087338"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/12.508323", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061088378"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.1109/12.707588", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1061088852"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "https://doi.org/10.2307/3616167", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1102044384"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2002-02", 
        "datePublishedReg": "2002-02-01", 
        "description": "This contribution is concerned with a generalization of Itoh and Tsujii's algorithm for inversion in extension fields . Unlike the original algorithm, the method introduced here uses a standard (or polynomial) basis representation. The inversion method is generalized for standard basis representation and relevant complexity expressions are established, consisting of the number of extension field multiplications and exponentiations. As the main contribution, for three important classes of fields we show that the Frobenius map can be explored to perform the exponentiations required for the inversion algorithm efficiently. As an important consequence, Itoh and Tsujii's inversion method shows almost the same practical complexity for standard basis as for normal basis representation for the field classes considered.", 
        "genre": "research_article", 
        "id": "sg:pub.10.1023/a:1013860532636", 
        "inLanguage": [
          "en"
        ], 
        "isAccessibleForFree": true, 
        "isPartOf": [
          {
            "id": "sg:journal.1136552", 
            "issn": [
              "0925-1022", 
              "1573-7586"
            ], 
            "name": "Designs, Codes and Cryptography", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "25"
          }
        ], 
        "name": "Itoh-Tsujii Inversion in Standard Basis and Its Application in Cryptography and Codes", 
        "pagination": "207-216", 
        "productId": [
          {
            "name": "readcube_id", 
            "type": "PropertyValue", 
            "value": [
              "38623c02af5d5860e1721054efd04c2cc582c8cbd50c3edf1b3743d33081f244"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1023/a:1013860532636"
            ]
          }, 
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1011834051"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1023/a:1013860532636", 
          "https://app.dimensions.ai/details/publication/pub.1011834051"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2019-04-10T13:12", 
        "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_8659_00000498.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "http://link.springer.com/10.1023/A:1013860532636"
      }
    ]
     

    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.1023/a:1013860532636'

    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.1023/a:1013860532636'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1023/a:1013860532636'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1023/a:1013860532636'


     

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

    96 TRIPLES      21 PREDICATES      36 URIs      19 LITERALS      7 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1023/a:1013860532636 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 schema:author N8e5b720192d0473aa747d6954d9af70d
    4 schema:citation sg:pub.10.1007/bf02252872
    5 https://doi.org/10.1016/0020-0190(91)90219-8
    6 https://doi.org/10.1016/0890-5401(88)90024-7
    7 https://doi.org/10.1016/0890-5401(89)90045-x
    8 https://doi.org/10.1090/s0025-5718-1987-0866109-5
    9 https://doi.org/10.1109/12.156539
    10 https://doi.org/10.1109/12.508323
    11 https://doi.org/10.1109/12.707588
    12 https://doi.org/10.2307/3616167
    13 schema:datePublished 2002-02
    14 schema:datePublishedReg 2002-02-01
    15 schema:description This contribution is concerned with a generalization of Itoh and Tsujii's algorithm for inversion in extension fields . Unlike the original algorithm, the method introduced here uses a standard (or polynomial) basis representation. The inversion method is generalized for standard basis representation and relevant complexity expressions are established, consisting of the number of extension field multiplications and exponentiations. As the main contribution, for three important classes of fields we show that the Frobenius map can be explored to perform the exponentiations required for the inversion algorithm efficiently. As an important consequence, Itoh and Tsujii's inversion method shows almost the same practical complexity for standard basis as for normal basis representation for the field classes considered.
    16 schema:genre research_article
    17 schema:inLanguage en
    18 schema:isAccessibleForFree true
    19 schema:isPartOf N66be51dfee35479c81b883d7f0f2bfe8
    20 N755b7a856f004c9fa494aff84fd98719
    21 sg:journal.1136552
    22 schema:name Itoh-Tsujii Inversion in Standard Basis and Its Application in Cryptography and Codes
    23 schema:pagination 207-216
    24 schema:productId N751f69426ac14d0d87947a9ae829cf9e
    25 Na7cd0cfbee1f4079b356830f4fa29edc
    26 Nb8d10bc1a495439fb78d2038b92befb5
    27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011834051
    28 https://doi.org/10.1023/a:1013860532636
    29 schema:sdDatePublished 2019-04-10T13:12
    30 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    31 schema:sdPublisher N01d2f65f1d8b470c9f12fdccfd26e9cd
    32 schema:url http://link.springer.com/10.1023/A:1013860532636
    33 sgo:license sg:explorer/license/
    34 sgo:sdDataset articles
    35 rdf:type schema:ScholarlyArticle
    36 N01d2f65f1d8b470c9f12fdccfd26e9cd schema:name Springer Nature - SN SciGraph project
    37 rdf:type schema:Organization
    38 N37ad44f4e17740cdb03316cfa06f1da1 rdf:first sg:person.016666667155.68
    39 rdf:rest rdf:nil
    40 N66be51dfee35479c81b883d7f0f2bfe8 schema:volumeNumber 25
    41 rdf:type schema:PublicationVolume
    42 N751f69426ac14d0d87947a9ae829cf9e schema:name dimensions_id
    43 schema:value pub.1011834051
    44 rdf:type schema:PropertyValue
    45 N755b7a856f004c9fa494aff84fd98719 schema:issueNumber 2
    46 rdf:type schema:PublicationIssue
    47 N8e5b720192d0473aa747d6954d9af70d rdf:first sg:person.07607775635.21
    48 rdf:rest N37ad44f4e17740cdb03316cfa06f1da1
    49 Na7cd0cfbee1f4079b356830f4fa29edc schema:name readcube_id
    50 schema:value 38623c02af5d5860e1721054efd04c2cc582c8cbd50c3edf1b3743d33081f244
    51 rdf:type schema:PropertyValue
    52 Nb8d10bc1a495439fb78d2038b92befb5 schema:name doi
    53 schema:value 10.1023/a:1013860532636
    54 rdf:type schema:PropertyValue
    55 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    56 schema:name Mathematical Sciences
    57 rdf:type schema:DefinedTerm
    58 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    59 schema:name Pure Mathematics
    60 rdf:type schema:DefinedTerm
    61 sg:journal.1136552 schema:issn 0925-1022
    62 1573-7586
    63 schema:name Designs, Codes and Cryptography
    64 rdf:type schema:Periodical
    65 sg:person.016666667155.68 schema:affiliation https://www.grid.ac/institutes/grid.268323.e
    66 schema:familyName Paar
    67 schema:givenName Christof
    68 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016666667155.68
    69 rdf:type schema:Person
    70 sg:person.07607775635.21 schema:affiliation https://www.grid.ac/institutes/grid.268323.e
    71 schema:familyName Guajardo
    72 schema:givenName Jorge
    73 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07607775635.21
    74 rdf:type schema:Person
    75 sg:pub.10.1007/bf02252872 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008777174
    76 https://doi.org/10.1007/bf02252872
    77 rdf:type schema:CreativeWork
    78 https://doi.org/10.1016/0020-0190(91)90219-8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008774178
    79 rdf:type schema:CreativeWork
    80 https://doi.org/10.1016/0890-5401(88)90024-7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022913144
    81 rdf:type schema:CreativeWork
    82 https://doi.org/10.1016/0890-5401(89)90045-x schema:sameAs https://app.dimensions.ai/details/publication/pub.1008396396
    83 rdf:type schema:CreativeWork
    84 https://doi.org/10.1090/s0025-5718-1987-0866109-5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1022745146
    85 rdf:type schema:CreativeWork
    86 https://doi.org/10.1109/12.156539 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061087338
    87 rdf:type schema:CreativeWork
    88 https://doi.org/10.1109/12.508323 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061088378
    89 rdf:type schema:CreativeWork
    90 https://doi.org/10.1109/12.707588 schema:sameAs https://app.dimensions.ai/details/publication/pub.1061088852
    91 rdf:type schema:CreativeWork
    92 https://doi.org/10.2307/3616167 schema:sameAs https://app.dimensions.ai/details/publication/pub.1102044384
    93 rdf:type schema:CreativeWork
    94 https://www.grid.ac/institutes/grid.268323.e schema:alternateName Worcester Polytechnic Institute
    95 schema:name ECE Department, Worcester Polytechnic Institute, 100 Institute Road, 01609, Worcester, MA, USA
    96 rdf:type schema:Organization
     




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


    ...