C−+* and HM: Variations Around Two Schemes of T. Matsumoto and H. Imai View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2002-09-24

AUTHORS

Jacques Patarin , Louis Goubin , Nicolas Courtois

ABSTRACT

In [4], H. Imai and T. Matsumoto presented new candidate trapdoor one-way permutations with a public key given as multivariate polynomials over a finite field. One of them, based on the idea of hiding a monomial field equation, was later presented in [7] under the name C*. It was broken by J. Patarin in [8]. J. Patarin and L. Goubin then suggested ([9], [10], [11], [12]) some schemes to repair C*, but with slightly more complex public key or secret key computations. In part I, we study some very simple variations of C* — such as C−+* — where the attack of [8] is avoided, and where the very simple secret key computations are kept. We then design some new cryptanalysis that are efficient against some of — but not all — these variations. [C] is another scheme of [4], very different from C* (despite the name), and based on the idea of hiding a monomial matrix equation. In part II, we show how to attack it (no cryptanalysis had been published so far). We then study more general schemes, still using the idea of hiding matrix equations, such as HM. An extended version of this paper can be obtained from the authors. More... »

PAGES

35-50

References to SciGraph publications

Book

TITLE

Advances in Cryptology — ASIACRYPT’98

ISBN

978-3-540-65109-3
978-3-540-49649-6

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/3-540-49649-1_4

DOI

http://dx.doi.org/10.1007/3-540-49649-1_4

DIMENSIONS

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


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/0804", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Data Format", 
        "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": {
          "name": [
            "Bull Smart Cards Terminals, BP 45, 68 route de Versailles, 78431, Louveciennes Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Patarin", 
        "givenName": "Jacques", 
        "id": "sg:person.011133025705.92", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011133025705.92"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "name": [
            "Bull Smart Cards Terminals, BP 45, 68 route de Versailles, 78431, Louveciennes Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Goubin", 
        "givenName": "Louis", 
        "id": "sg:person.015370711241.32", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015370711241.32"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Universite De Toulon Et Du Var", 
          "id": "https://www.grid.ac/institutes/grid.12611.35", 
          "name": [
            "Mod\u00e9lisation et Signal, Universit\u00e9 de Toulon et du Var, BP 132, 83957, La Garde Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Courtois", 
        "givenName": "Nicolas", 
        "id": "sg:person.013151403707.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013151403707.45"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/978-3-662-03642-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011913013", 
          "https://doi.org/10.1007/978-3-662-03642-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/978-3-662-03642-6", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1011913013", 
          "https://doi.org/10.1007/978-3-662-03642-6"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0028491", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1014519443", 
          "https://doi.org/10.1007/bfb0028491"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bfb0028492", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021787653", 
          "https://doi.org/10.1007/bfb0028492"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-68339-9_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051894160", 
          "https://doi.org/10.1007/3-540-68339-9_4"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/3-540-68339-9_4", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1051894160", 
          "https://doi.org/10.1007/3-540-68339-9_4"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "2002-09-24", 
    "datePublishedReg": "2002-09-24", 
    "description": "In [4], H. Imai and T. Matsumoto presented new candidate trapdoor one-way permutations with a public key given as multivariate polynomials over a finite field. One of them, based on the idea of hiding a monomial field equation, was later presented in [7] under the name C*. It was broken by J. Patarin in [8]. J. Patarin and L. Goubin then suggested ([9], [10], [11], [12]) some schemes to repair C*, but with slightly more complex public key or secret key computations. In part I, we study some very simple variations of C* \u2014 such as C\u2212+* \u2014 where the attack of [8] is avoided, and where the very simple secret key computations are kept. We then design some new cryptanalysis that are efficient against some of \u2014 but not all \u2014 these variations. [C] is another scheme of [4], very different from C* (despite the name), and based on the idea of hiding a monomial matrix equation. In part II, we show how to attack it (no cryptanalysis had been published so far). We then study more general schemes, still using the idea of hiding matrix equations, such as HM. An extended version of this paper can be obtained from the authors.", 
    "editor": [
      {
        "familyName": "Ohta", 
        "givenName": "Kazuo", 
        "type": "Person"
      }, 
      {
        "familyName": "Pei", 
        "givenName": "Dingyi", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-49649-1_4", 
    "inLanguage": [
      "en"
    ], 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-65109-3", 
        "978-3-540-49649-6"
      ], 
      "name": "Advances in Cryptology \u2014 ASIACRYPT\u201998", 
      "type": "Book"
    }, 
    "name": "C\u2212+* and HM: Variations Around Two Schemes of T. Matsumoto and H. Imai", 
    "pagination": "35-50", 
    "productId": [
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-49649-1_4"
        ]
      }, 
      {
        "name": "readcube_id", 
        "type": "PropertyValue", 
        "value": [
          "b64fddcfbdee02dff8c1a30db74534fbc36b013a9c3f740f60505ebe47ea3627"
        ]
      }, 
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1038271412"
        ]
      }
    ], 
    "publisher": {
      "location": "Berlin, Heidelberg", 
      "name": "Springer Berlin Heidelberg", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-49649-1_4", 
      "https://app.dimensions.ai/details/publication/pub.1038271412"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2019-04-16T05:41", 
    "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/0000000347_0000000347/records_89786_00000001.jsonl", 
    "type": "Chapter", 
    "url": "https://link.springer.com/10.1007%2F3-540-49649-1_4"
  }
]
 

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/3-540-49649-1_4'

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/3-540-49649-1_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-49649-1_4'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/3-540-49649-1_4'


 

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

104 TRIPLES      23 PREDICATES      30 URIs      19 LITERALS      8 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-49649-1_4 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N832115d54b2d466ab07b6fcd5603e3b9
4 schema:citation sg:pub.10.1007/3-540-68339-9_4
5 sg:pub.10.1007/978-3-662-03642-6
6 sg:pub.10.1007/bfb0028491
7 sg:pub.10.1007/bfb0028492
8 schema:datePublished 2002-09-24
9 schema:datePublishedReg 2002-09-24
10 schema:description In [4], H. Imai and T. Matsumoto presented new candidate trapdoor one-way permutations with a public key given as multivariate polynomials over a finite field. One of them, based on the idea of hiding a monomial field equation, was later presented in [7] under the name C*. It was broken by J. Patarin in [8]. J. Patarin and L. Goubin then suggested ([9], [10], [11], [12]) some schemes to repair C*, but with slightly more complex public key or secret key computations. In part I, we study some very simple variations of C* — such as C−+* — where the attack of [8] is avoided, and where the very simple secret key computations are kept. We then design some new cryptanalysis that are efficient against some of — but not all — these variations. [C] is another scheme of [4], very different from C* (despite the name), and based on the idea of hiding a monomial matrix equation. In part II, we show how to attack it (no cryptanalysis had been published so far). We then study more general schemes, still using the idea of hiding matrix equations, such as HM. An extended version of this paper can be obtained from the authors.
11 schema:editor N2ebf4064bf6f4a23aa3d408296b1e1fd
12 schema:genre chapter
13 schema:inLanguage en
14 schema:isAccessibleForFree true
15 schema:isPartOf N12c95af770ac46628173e198607e8a36
16 schema:name C−+* and HM: Variations Around Two Schemes of T. Matsumoto and H. Imai
17 schema:pagination 35-50
18 schema:productId N42fa37f7c4ea4d408272dfd6df63fa57
19 Nb12e6bb065d6427189cb8d786615863a
20 Nbffbed219a36498ca1c54ffeba19fec7
21 schema:publisher N79d65fe62971433da79ee6e261b441c0
22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038271412
23 https://doi.org/10.1007/3-540-49649-1_4
24 schema:sdDatePublished 2019-04-16T05:41
25 schema:sdLicense https://scigraph.springernature.com/explorer/license/
26 schema:sdPublisher N3445a4e3b174436ca6a46257bd523a82
27 schema:url https://link.springer.com/10.1007%2F3-540-49649-1_4
28 sgo:license sg:explorer/license/
29 sgo:sdDataset chapters
30 rdf:type schema:Chapter
31 N12c95af770ac46628173e198607e8a36 schema:isbn 978-3-540-49649-6
32 978-3-540-65109-3
33 schema:name Advances in Cryptology — ASIACRYPT’98
34 rdf:type schema:Book
35 N13992a77ae6d454ba16d2f2607f179a0 schema:familyName Pei
36 schema:givenName Dingyi
37 rdf:type schema:Person
38 N1f96dc8b751749549fd141ce13844de2 schema:familyName Ohta
39 schema:givenName Kazuo
40 rdf:type schema:Person
41 N2ebf4064bf6f4a23aa3d408296b1e1fd rdf:first N1f96dc8b751749549fd141ce13844de2
42 rdf:rest N88348b121ef149dd8a0b2b0ee01eae85
43 N30920fb70cdd40b98746f712da8a43c2 schema:name Bull Smart Cards Terminals, BP 45, 68 route de Versailles, 78431, Louveciennes Cedex, France
44 rdf:type schema:Organization
45 N3445a4e3b174436ca6a46257bd523a82 schema:name Springer Nature - SN SciGraph project
46 rdf:type schema:Organization
47 N42fa37f7c4ea4d408272dfd6df63fa57 schema:name doi
48 schema:value 10.1007/3-540-49649-1_4
49 rdf:type schema:PropertyValue
50 N656dda3f8ce54c50bf7559f4429ec2f9 rdf:first sg:person.015370711241.32
51 rdf:rest Nf4daa74b3b7a49d08c4142a07ffc5ce1
52 N79d65fe62971433da79ee6e261b441c0 schema:location Berlin, Heidelberg
53 schema:name Springer Berlin Heidelberg
54 rdf:type schema:Organisation
55 N832115d54b2d466ab07b6fcd5603e3b9 rdf:first sg:person.011133025705.92
56 rdf:rest N656dda3f8ce54c50bf7559f4429ec2f9
57 N88348b121ef149dd8a0b2b0ee01eae85 rdf:first N13992a77ae6d454ba16d2f2607f179a0
58 rdf:rest rdf:nil
59 N8fecc12413c6408d81d407f28ac227a4 schema:name Bull Smart Cards Terminals, BP 45, 68 route de Versailles, 78431, Louveciennes Cedex, France
60 rdf:type schema:Organization
61 Nb12e6bb065d6427189cb8d786615863a schema:name dimensions_id
62 schema:value pub.1038271412
63 rdf:type schema:PropertyValue
64 Nbffbed219a36498ca1c54ffeba19fec7 schema:name readcube_id
65 schema:value b64fddcfbdee02dff8c1a30db74534fbc36b013a9c3f740f60505ebe47ea3627
66 rdf:type schema:PropertyValue
67 Nf4daa74b3b7a49d08c4142a07ffc5ce1 rdf:first sg:person.013151403707.45
68 rdf:rest rdf:nil
69 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
70 schema:name Information and Computing Sciences
71 rdf:type schema:DefinedTerm
72 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
73 schema:name Data Format
74 rdf:type schema:DefinedTerm
75 sg:person.011133025705.92 schema:affiliation N30920fb70cdd40b98746f712da8a43c2
76 schema:familyName Patarin
77 schema:givenName Jacques
78 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011133025705.92
79 rdf:type schema:Person
80 sg:person.013151403707.45 schema:affiliation https://www.grid.ac/institutes/grid.12611.35
81 schema:familyName Courtois
82 schema:givenName Nicolas
83 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013151403707.45
84 rdf:type schema:Person
85 sg:person.015370711241.32 schema:affiliation N8fecc12413c6408d81d407f28ac227a4
86 schema:familyName Goubin
87 schema:givenName Louis
88 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015370711241.32
89 rdf:type schema:Person
90 sg:pub.10.1007/3-540-68339-9_4 schema:sameAs https://app.dimensions.ai/details/publication/pub.1051894160
91 https://doi.org/10.1007/3-540-68339-9_4
92 rdf:type schema:CreativeWork
93 sg:pub.10.1007/978-3-662-03642-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1011913013
94 https://doi.org/10.1007/978-3-662-03642-6
95 rdf:type schema:CreativeWork
96 sg:pub.10.1007/bfb0028491 schema:sameAs https://app.dimensions.ai/details/publication/pub.1014519443
97 https://doi.org/10.1007/bfb0028491
98 rdf:type schema:CreativeWork
99 sg:pub.10.1007/bfb0028492 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021787653
100 https://doi.org/10.1007/bfb0028492
101 rdf:type schema:CreativeWork
102 https://www.grid.ac/institutes/grid.12611.35 schema:alternateName Universite De Toulon Et Du Var
103 schema:name Modélisation et Signal, Université de Toulon et du Var, BP 132, 83957, La Garde Cedex, France
104 rdf:type schema:Organization
 




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


...