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 N743b20940eae4c088bfea228bb448071
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 N198a94338c3248fcb2ef420c779d70df
12 schema:genre chapter
13 schema:inLanguage en
14 schema:isAccessibleForFree true
15 schema:isPartOf Na71411e1362a4feda623d4a34985b8b4
16 schema:name C−+* and HM: Variations Around Two Schemes of T. Matsumoto and H. Imai
17 schema:pagination 35-50
18 schema:productId N85eed65926ca4f178d8d85249c579e83
19 Nc29d02a1c8cf4e99a2d4204b0c108019
20 Ne74ebb58492f4380860cdbbd1d7b12ae
21 schema:publisher N0bc5ec5652f54b4fbe70fc21901c8e32
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 N8316b62c74fa4e2e8a89259cdfb8b00a
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 N0bc5ec5652f54b4fbe70fc21901c8e32 schema:location Berlin, Heidelberg
32 schema:name Springer Berlin Heidelberg
33 rdf:type schema:Organisation
34 N198a94338c3248fcb2ef420c779d70df rdf:first Neb36f7aca35c4618856213bcebc457e1
35 rdf:rest Nc3aaa46aad4542358801c4d17524838c
36 N5658549b5c5f4bd68eac376f0c1ae344 rdf:first sg:person.015370711241.32
37 rdf:rest Nd0acbdd68af8427096890c6817fd7c85
38 N743b20940eae4c088bfea228bb448071 rdf:first sg:person.011133025705.92
39 rdf:rest N5658549b5c5f4bd68eac376f0c1ae344
40 N8316b62c74fa4e2e8a89259cdfb8b00a schema:name Springer Nature - SN SciGraph project
41 rdf:type schema:Organization
42 N85eed65926ca4f178d8d85249c579e83 schema:name dimensions_id
43 schema:value pub.1038271412
44 rdf:type schema:PropertyValue
45 Na71411e1362a4feda623d4a34985b8b4 schema:isbn 978-3-540-49649-6
46 978-3-540-65109-3
47 schema:name Advances in Cryptology — ASIACRYPT’98
48 rdf:type schema:Book
49 Nc29d02a1c8cf4e99a2d4204b0c108019 schema:name readcube_id
50 schema:value b64fddcfbdee02dff8c1a30db74534fbc36b013a9c3f740f60505ebe47ea3627
51 rdf:type schema:PropertyValue
52 Nc3aaa46aad4542358801c4d17524838c rdf:first Nc902917eae2845cea170e0696c9aebe7
53 rdf:rest rdf:nil
54 Nc902917eae2845cea170e0696c9aebe7 schema:familyName Pei
55 schema:givenName Dingyi
56 rdf:type schema:Person
57 Nd0acbdd68af8427096890c6817fd7c85 rdf:first sg:person.013151403707.45
58 rdf:rest rdf:nil
59 Ne74ebb58492f4380860cdbbd1d7b12ae schema:name doi
60 schema:value 10.1007/3-540-49649-1_4
61 rdf:type schema:PropertyValue
62 Neb36f7aca35c4618856213bcebc457e1 schema:familyName Ohta
63 schema:givenName Kazuo
64 rdf:type schema:Person
65 Nef1f8a5347eb4dd6b7be6c393b934b5b schema:name Bull Smart Cards Terminals, BP 45, 68 route de Versailles, 78431, Louveciennes Cedex, France
66 rdf:type schema:Organization
67 Nf3462377e20e4e9788802949b244e594 schema:name Bull Smart Cards Terminals, BP 45, 68 route de Versailles, 78431, Louveciennes Cedex, France
68 rdf:type schema:Organization
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 Nf3462377e20e4e9788802949b244e594
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 Nef1f8a5347eb4dd6b7be6c393b934b5b
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)


...