Cryptanalysis of Rainbow View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2006

AUTHORS

Olivier Billet , Henri Gilbert

ABSTRACT

Rainbow is a fast asymmetric multivariate signature algorithm proposed by J. Ding and D. Schmidt in [5]. This paper presents a cryptanalysis of Rainbow which enables an attacker provided with the public key to recover an equivalent representation of the secret key, thus allowing her to efficiently forge a signature of any message. For the set of parameter values recommended by the authors of Rainbow in order to achieve a security level strictly higher than 280, the complexity of our attack is less than 271 operations. This is 240 times less than the complexity of the best known attack used by the authors to dimension their system. More... »

PAGES

336-347

Book

TITLE

Security and Cryptography for Networks

ISBN

978-3-540-38080-1
978-3-540-38081-8

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11832072_23

DOI

http://dx.doi.org/10.1007/11832072_23

DIMENSIONS

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


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": "France T\u00e9l\u00e9com R&D, 38\u201340, rue du G\u00e9n\u00e9ral Leclerc, 92794 Cedex 9, Issy les Moulineaux, France", 
          "id": "http://www.grid.ac/institutes/grid.89485.38", 
          "name": [
            "France T\u00e9l\u00e9com R&D, 38\u201340, rue du G\u00e9n\u00e9ral Leclerc, 92794 Cedex 9, Issy les Moulineaux, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Billet", 
        "givenName": "Olivier", 
        "id": "sg:person.011100216333.64", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011100216333.64"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "France T\u00e9l\u00e9com R&D, 38\u201340, rue du G\u00e9n\u00e9ral Leclerc, 92794 Cedex 9, Issy les Moulineaux, France", 
          "id": "http://www.grid.ac/institutes/grid.89485.38", 
          "name": [
            "France T\u00e9l\u00e9com R&D, 38\u201340, rue du G\u00e9n\u00e9ral Leclerc, 92794 Cedex 9, Issy les Moulineaux, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Gilbert", 
        "givenName": "Henri", 
        "id": "sg:person.012771236207.08", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012771236207.08"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "Rainbow is a fast asymmetric multivariate signature algorithm proposed by J. Ding and D. Schmidt in [5]. This paper presents a cryptanalysis of Rainbow which enables an attacker provided with the public key to recover an equivalent representation of the secret key, thus allowing her to efficiently forge a signature of any message. For the set of parameter values recommended by the authors of Rainbow in order to achieve a security level strictly higher than 280, the complexity of our attack is less than 271 operations. This is 240 times less than the complexity of the best known attack used by the authors to dimension their system.", 
    "editor": [
      {
        "familyName": "De Prisco", 
        "givenName": "Roberto", 
        "type": "Person"
      }, 
      {
        "familyName": "Yung", 
        "givenName": "Moti", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11832072_23", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-540-38080-1", 
        "978-3-540-38081-8"
      ], 
      "name": "Security and Cryptography for Networks", 
      "type": "Book"
    }, 
    "keywords": [
      "equivalent representation", 
      "D. Schmidt", 
      "parameter values", 
      "J. Ding", 
      "signature algorithm", 
      "complexity", 
      "rainbow", 
      "algorithm", 
      "Ding", 
      "Schmidt", 
      "cryptanalysis", 
      "representation", 
      "set", 
      "secret key", 
      "security level", 
      "system", 
      "order", 
      "public key", 
      "operation", 
      "attacker", 
      "authors", 
      "signatures", 
      "values", 
      "time", 
      "attacks", 
      "key", 
      "messages", 
      "levels", 
      "paper"
    ], 
    "name": "Cryptanalysis of Rainbow", 
    "pagination": "336-347", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036853782"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11832072_23"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11832072_23", 
      "https://app.dimensions.ai/details/publication/pub.1036853782"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:15", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_277.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11832072_23"
  }
]
 

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/11832072_23'

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/11832072_23'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11832072_23'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11832072_23'


 

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

100 TRIPLES      22 PREDICATES      54 URIs      47 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11832072_23 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nd550e567d18849b880b736726ac1406a
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description Rainbow is a fast asymmetric multivariate signature algorithm proposed by J. Ding and D. Schmidt in [5]. This paper presents a cryptanalysis of Rainbow which enables an attacker provided with the public key to recover an equivalent representation of the secret key, thus allowing her to efficiently forge a signature of any message. For the set of parameter values recommended by the authors of Rainbow in order to achieve a security level strictly higher than 280, the complexity of our attack is less than 271 operations. This is 240 times less than the complexity of the best known attack used by the authors to dimension their system.
7 schema:editor N032ff732d5324db5a6cf82109b3a6518
8 schema:genre chapter
9 schema:isAccessibleForFree false
10 schema:isPartOf Na9e37c6883f249409a4fa9722b661f83
11 schema:keywords D. Schmidt
12 Ding
13 J. Ding
14 Schmidt
15 algorithm
16 attacker
17 attacks
18 authors
19 complexity
20 cryptanalysis
21 equivalent representation
22 key
23 levels
24 messages
25 operation
26 order
27 paper
28 parameter values
29 public key
30 rainbow
31 representation
32 secret key
33 security level
34 set
35 signature algorithm
36 signatures
37 system
38 time
39 values
40 schema:name Cryptanalysis of Rainbow
41 schema:pagination 336-347
42 schema:productId Nb20492edf21243748c2e9b7360c5fd88
43 Nc973c2b104a645b591aee4cf93bbc0d3
44 schema:publisher Nfd0e23c8eaa44edaa41daf33588c6841
45 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036853782
46 https://doi.org/10.1007/11832072_23
47 schema:sdDatePublished 2022-11-24T21:15
48 schema:sdLicense https://scigraph.springernature.com/explorer/license/
49 schema:sdPublisher N82ccd3f8f7e44e59a1482ee6098f9be2
50 schema:url https://doi.org/10.1007/11832072_23
51 sgo:license sg:explorer/license/
52 sgo:sdDataset chapters
53 rdf:type schema:Chapter
54 N032ff732d5324db5a6cf82109b3a6518 rdf:first Na2ec7e68b67042eebaa71c4c44fb6381
55 rdf:rest N3db1223f5c0c43419be7e59c664dce37
56 N3db1223f5c0c43419be7e59c664dce37 rdf:first N4f2c784d29d945609aa2cdbc74b7760f
57 rdf:rest rdf:nil
58 N4f2c784d29d945609aa2cdbc74b7760f schema:familyName Yung
59 schema:givenName Moti
60 rdf:type schema:Person
61 N82ccd3f8f7e44e59a1482ee6098f9be2 schema:name Springer Nature - SN SciGraph project
62 rdf:type schema:Organization
63 Na2ec7e68b67042eebaa71c4c44fb6381 schema:familyName De Prisco
64 schema:givenName Roberto
65 rdf:type schema:Person
66 Na9e37c6883f249409a4fa9722b661f83 schema:isbn 978-3-540-38080-1
67 978-3-540-38081-8
68 schema:name Security and Cryptography for Networks
69 rdf:type schema:Book
70 Nae11658c886447dba57dd689ab9182a2 rdf:first sg:person.012771236207.08
71 rdf:rest rdf:nil
72 Nb20492edf21243748c2e9b7360c5fd88 schema:name doi
73 schema:value 10.1007/11832072_23
74 rdf:type schema:PropertyValue
75 Nc973c2b104a645b591aee4cf93bbc0d3 schema:name dimensions_id
76 schema:value pub.1036853782
77 rdf:type schema:PropertyValue
78 Nd550e567d18849b880b736726ac1406a rdf:first sg:person.011100216333.64
79 rdf:rest Nae11658c886447dba57dd689ab9182a2
80 Nfd0e23c8eaa44edaa41daf33588c6841 schema:name Springer Nature
81 rdf:type schema:Organisation
82 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
83 schema:name Information and Computing Sciences
84 rdf:type schema:DefinedTerm
85 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
86 schema:name Data Format
87 rdf:type schema:DefinedTerm
88 sg:person.011100216333.64 schema:affiliation grid-institutes:grid.89485.38
89 schema:familyName Billet
90 schema:givenName Olivier
91 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011100216333.64
92 rdf:type schema:Person
93 sg:person.012771236207.08 schema:affiliation grid-institutes:grid.89485.38
94 schema:familyName Gilbert
95 schema:givenName Henri
96 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012771236207.08
97 rdf:type schema:Person
98 grid-institutes:grid.89485.38 schema:alternateName France Télécom R&D, 38–40, rue du Général Leclerc, 92794 Cedex 9, Issy les Moulineaux, France
99 schema:name France Télécom R&D, 38–40, rue du Général Leclerc, 92794 Cedex 9, Issy les Moulineaux, France
100 rdf:type schema:Organization
 




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


...