Cryptanalysis of the TTM Cryptosystem View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2000-10-27

AUTHORS

Louis Goubin , Nicolas T. Courtois

ABSTRACT

In 1985 Fell and Diffie proposed constructing trapdoor functions with multivariate equations [11]. They used several sequentially solved stages that combine into a triangular system we call T. In the present paper, we study a more general family of TPM (for “Triangle Plus Minus”) schemes: a triangular construction mixed with some u random polynomials and with some r of the beginning equations removed. We go beyond all previous attacks proposed on such cryptosystems using a low degree component of the inverse function. The cryptanalysis of TPM is reduced to a simple linear algebra problem called MinRank(r): Find a linear combination of given matrices that has a small rank r. We introduce a new attack for MinRank called ‘Kernel Attack’ that works for qr small. We explain that TPM schemes can be used in encryption only if qr is small and therefore they are not secure.As an application, we showed that the TTM cryptosystem proposed by T.T. Moh at CrypTec’99 [15],[16] reduces to MinRank(2). Thus, though the cleartext size is 512 bits, we break it in O(252). The particular TTM of [15],[16] can be broken in O(228) due additional weaknesses, and we needed only few minutes to solve the challenge TTM 2.1. from the website of the TTM selling company, US Data Security.We also studied TPM in signature, possible only if qu small. It is equally insecure: the ‘Degeneracy Attack’ we introduce runs in qu· polynomial. More... »

PAGES

44-57

Book

TITLE

Advances in Cryptology — ASIACRYPT 2000

ISBN

978-3-540-41404-9
978-3-540-44448-0

Identifiers

URI

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

DOI

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

DIMENSIONS

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


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/08", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Information and Computing Sciences", 
        "type": "DefinedTerm"
      }, 
      {
        "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"
      }
    ], 
    "author": [
      {
        "affiliation": {
          "alternateName": "Bull CP8, 68 route de Versailles, BP45, 78431, Louveciennes Cedex, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Bull CP8, 68 route de Versailles, BP45, 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": "Bull CP8, 68 route de Versailles, BP45, 78431, Louveciennes Cedex, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Bull CP8, 68 route de Versailles, BP45, 78431, Louveciennes Cedex, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Courtois", 
        "givenName": "Nicolas T.", 
        "id": "sg:person.013151403707.45", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013151403707.45"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2000-10-27", 
    "datePublishedReg": "2000-10-27", 
    "description": "In 1985 Fell and Diffie proposed constructing trapdoor functions with multivariate equations [11]. They used several sequentially solved stages that combine into a triangular system we call T. In the present paper, we study a more general family of TPM (for \u201cTriangle Plus Minus\u201d) schemes: a triangular construction mixed with some u random polynomials and with some r of the beginning equations removed. We go beyond all previous attacks proposed on such cryptosystems using a low degree component of the inverse function. The cryptanalysis of TPM is reduced to a simple linear algebra problem called MinRank(r): Find a linear combination of given matrices that has a small rank r. We introduce a new attack for MinRank called \u2018Kernel Attack\u2019 that works for qr small. We explain that TPM schemes can be used in encryption only if qr is small and therefore they are not secure.As an application, we showed that the TTM cryptosystem proposed by T.T. Moh at CrypTec\u201999 [15],[16] reduces to MinRank(2). Thus, though the cleartext size is 512 bits, we break it in O(252). The particular TTM of [15],[16] can be broken in O(228) due additional weaknesses, and we needed only few minutes to solve the challenge TTM 2.1. from the website of the TTM selling company, US Data Security.We also studied TPM in signature, possible only if qu small. It is equally insecure: the \u2018Degeneracy Attack\u2019 we introduce runs in qu\u00b7 polynomial.", 
    "editor": [
      {
        "familyName": "Okamoto", 
        "givenName": "Tatsuaki", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/3-540-44448-3_4", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-41404-9", 
        "978-3-540-44448-0"
      ], 
      "name": "Advances in Cryptology \u2014 ASIACRYPT 2000", 
      "type": "Book"
    }, 
    "keywords": [
      "linear algebra problems", 
      "low degree components", 
      "TPM scheme", 
      "random polynomials", 
      "algebra problems", 
      "triangular systems", 
      "general family", 
      "multivariate equations", 
      "rank r.", 
      "triangular construction", 
      "linear combination", 
      "kernel attacks", 
      "degree components", 
      "inverse function", 
      "such cryptosystems", 
      "equations", 
      "scheme", 
      "present paper", 
      "cryptosystem", 
      "QR", 
      "polynomials", 
      "minrank", 
      "problem", 
      "cryptanalysis", 
      "function", 
      "Qu", 
      "matrix", 
      "R.", 
      "construction", 
      "Diffie", 
      "applications", 
      "system", 
      "additional weakness", 
      "bits", 
      "new attacks", 
      "trapdoor functions", 
      "run", 
      "Fell", 
      "previous attacks", 
      "attacks", 
      "family", 
      "size", 
      "data security", 
      "security", 
      "combination", 
      "components", 
      "encryption", 
      "companies", 
      "TTM", 
      "weakness", 
      "signatures", 
      "stage", 
      "TPM", 
      "websites", 
      "Mohs", 
      "minutes", 
      "paper", 
      "beginning equations", 
      "cryptanalysis of TPM", 
      "simple linear algebra problem", 
      "small rank r.", 
      "TTM cryptosystem", 
      "T.T. Moh", 
      "CrypTec\u201999", 
      "cleartext size", 
      "particular TTM", 
      "due additional weaknesses", 
      "challenge TTM 2.1", 
      "TTM 2.1", 
      "US Data Security", 
      "Degeneracy Attack"
    ], 
    "name": "Cryptanalysis of the TTM Cryptosystem", 
    "pagination": "44-57", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1052740197"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/3-540-44448-3_4"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/3-540-44448-3_4", 
      "https://app.dimensions.ai/details/publication/pub.1052740197"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2021-12-01T20:05", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20211201/entities/gbq_results/chapter/chapter_309.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/3-540-44448-3_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-44448-3_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-44448-3_4'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/3-540-44448-3_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-44448-3_4'


 

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

138 TRIPLES      23 PREDICATES      96 URIs      89 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/3-540-44448-3_4 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nb5ca7de7db8c438f971c0b99eb8e2028
4 schema:datePublished 2000-10-27
5 schema:datePublishedReg 2000-10-27
6 schema:description In 1985 Fell and Diffie proposed constructing trapdoor functions with multivariate equations [11]. They used several sequentially solved stages that combine into a triangular system we call T. In the present paper, we study a more general family of TPM (for “Triangle Plus Minus”) schemes: a triangular construction mixed with some u random polynomials and with some r of the beginning equations removed. We go beyond all previous attacks proposed on such cryptosystems using a low degree component of the inverse function. The cryptanalysis of TPM is reduced to a simple linear algebra problem called MinRank(r): Find a linear combination of given matrices that has a small rank r. We introduce a new attack for MinRank called ‘Kernel Attack’ that works for qr small. We explain that TPM schemes can be used in encryption only if qr is small and therefore they are not secure.As an application, we showed that the TTM cryptosystem proposed by T.T. Moh at CrypTec’99 [15],[16] reduces to MinRank(2). Thus, though the cleartext size is 512 bits, we break it in O(252). The particular TTM of [15],[16] can be broken in O(228) due additional weaknesses, and we needed only few minutes to solve the challenge TTM 2.1. from the website of the TTM selling company, US Data Security.We also studied TPM in signature, possible only if qu small. It is equally insecure: the ‘Degeneracy Attack’ we introduce runs in qu· polynomial.
7 schema:editor N4490ac0366f249268b0d7ad0e66d06e3
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf Nfcf6d54ba81c45e594e05388bde2e410
12 schema:keywords CrypTec’99
13 Degeneracy Attack
14 Diffie
15 Fell
16 Mohs
17 QR
18 Qu
19 R.
20 T.T. Moh
21 TPM
22 TPM scheme
23 TTM
24 TTM 2.1
25 TTM cryptosystem
26 US Data Security
27 additional weakness
28 algebra problems
29 applications
30 attacks
31 beginning equations
32 bits
33 challenge TTM 2.1
34 cleartext size
35 combination
36 companies
37 components
38 construction
39 cryptanalysis
40 cryptanalysis of TPM
41 cryptosystem
42 data security
43 degree components
44 due additional weaknesses
45 encryption
46 equations
47 family
48 function
49 general family
50 inverse function
51 kernel attacks
52 linear algebra problems
53 linear combination
54 low degree components
55 matrix
56 minrank
57 minutes
58 multivariate equations
59 new attacks
60 paper
61 particular TTM
62 polynomials
63 present paper
64 previous attacks
65 problem
66 random polynomials
67 rank r.
68 run
69 scheme
70 security
71 signatures
72 simple linear algebra problem
73 size
74 small rank r.
75 stage
76 such cryptosystems
77 system
78 trapdoor functions
79 triangular construction
80 triangular systems
81 weakness
82 websites
83 schema:name Cryptanalysis of the TTM Cryptosystem
84 schema:pagination 44-57
85 schema:productId Naf485c7be231471b96180974ad7b10ca
86 Ne0018419744446dda5dc48009d6fa4ca
87 schema:publisher N8441be71797048d28610775a5d1b971f
88 schema:sameAs https://app.dimensions.ai/details/publication/pub.1052740197
89 https://doi.org/10.1007/3-540-44448-3_4
90 schema:sdDatePublished 2021-12-01T20:05
91 schema:sdLicense https://scigraph.springernature.com/explorer/license/
92 schema:sdPublisher N180733f3f1794c9c8883359bc55960a4
93 schema:url https://doi.org/10.1007/3-540-44448-3_4
94 sgo:license sg:explorer/license/
95 sgo:sdDataset chapters
96 rdf:type schema:Chapter
97 N180733f3f1794c9c8883359bc55960a4 schema:name Springer Nature - SN SciGraph project
98 rdf:type schema:Organization
99 N4490ac0366f249268b0d7ad0e66d06e3 rdf:first N53485d24d5604f2a982bc1ce48c99b08
100 rdf:rest rdf:nil
101 N53485d24d5604f2a982bc1ce48c99b08 schema:familyName Okamoto
102 schema:givenName Tatsuaki
103 rdf:type schema:Person
104 N8441be71797048d28610775a5d1b971f schema:name Springer Nature
105 rdf:type schema:Organisation
106 Naf485c7be231471b96180974ad7b10ca schema:name dimensions_id
107 schema:value pub.1052740197
108 rdf:type schema:PropertyValue
109 Nb5ca7de7db8c438f971c0b99eb8e2028 rdf:first sg:person.015370711241.32
110 rdf:rest Nc108cd86c2914b328b621f6ce001545e
111 Nc108cd86c2914b328b621f6ce001545e rdf:first sg:person.013151403707.45
112 rdf:rest rdf:nil
113 Ne0018419744446dda5dc48009d6fa4ca schema:name doi
114 schema:value 10.1007/3-540-44448-3_4
115 rdf:type schema:PropertyValue
116 Nfcf6d54ba81c45e594e05388bde2e410 schema:isbn 978-3-540-41404-9
117 978-3-540-44448-0
118 schema:name Advances in Cryptology — ASIACRYPT 2000
119 rdf:type schema:Book
120 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
121 schema:name Information and Computing Sciences
122 rdf:type schema:DefinedTerm
123 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
124 schema:name Data Format
125 rdf:type schema:DefinedTerm
126 sg:person.013151403707.45 schema:affiliation grid-institutes:None
127 schema:familyName Courtois
128 schema:givenName Nicolas T.
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013151403707.45
130 rdf:type schema:Person
131 sg:person.015370711241.32 schema:affiliation grid-institutes:None
132 schema:familyName Goubin
133 schema:givenName Louis
134 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015370711241.32
135 rdf:type schema:Person
136 grid-institutes:None schema:alternateName Bull CP8, 68 route de Versailles, BP45, 78431, Louveciennes Cedex, France
137 schema:name Bull CP8, 68 route de Versailles, BP45, 78431, Louveciennes Cedex, France
138 rdf:type schema:Organization
 




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


...