Improved Interpolation Attacks on Cryptographic Primitives of Low Algebraic Degree View Full Text


Ontology type: schema:Chapter     


Chapter Info

DATE

2020-01-10

AUTHORS

Chaoyun Li , Bart Preneel

ABSTRACT

Symmetric cryptographic primitives with low multiplicative complexity have been proposed to improve the performance of emerging applications such as secure Multi-Party Computation. However, primitives composed of round functions with low algebraic degree require a careful evaluation to assess their security against algebraic cryptanalysis, and in particular interpolation attacks. This paper proposes new low-memory interpolation attacks on symmetric key primitives of low degree. Moreover, we present generic attacks on block ciphers with a simple key schedule; our attacks require either constant memory or constant data complexity. The improved attack is applied to the block cipher MiMC which aims to minimize the number of multiplications in large finite fields. As a result, we can break MiMC-129/129 with 38 rounds with time and data complexity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{65.5}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{60.2}$$\end{document} respectively and with negligible memory; this attack invalidates one of the security claims of the designers. Our attack indicates that for MiMC-129/129 the full 82 rounds are necessary even with restrictions on the memory available to the attacker. For variants of MiMC with larger keys, we present new attacks with reduced complexity. Our results do not affect the security claims of the full round MiMC. More... »

PAGES

171-193

Book

TITLE

Selected Areas in Cryptography – SAC 2019

ISBN

978-3-030-38470-8
978-3-030-38471-5

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-030-38471-5_8

DOI

http://dx.doi.org/10.1007/978-3-030-38471-5_8

DIMENSIONS

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


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/0802", 
        "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
        "name": "Computation Theory and Mathematics", 
        "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": "imec-COSIC, Department Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "imec-COSIC, Department Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Li", 
        "givenName": "Chaoyun", 
        "id": "sg:person.012162474100.06", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012162474100.06"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "imec-COSIC, Department Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "imec-COSIC, Department Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "id": "sg:person.011115044357.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2020-01-10", 
    "datePublishedReg": "2020-01-10", 
    "description": "Symmetric cryptographic primitives with low multiplicative complexity have been proposed to improve the performance of emerging applications such as secure Multi-Party Computation. However, primitives composed of round functions with low algebraic degree require a careful evaluation to assess their security against algebraic cryptanalysis, and in particular interpolation attacks. This paper proposes new low-memory interpolation attacks on symmetric key primitives of low degree. Moreover, we present generic attacks on block ciphers with a simple key schedule; our attacks require either constant memory or constant data complexity. The improved attack is applied to the block cipher MiMC which aims to minimize the number of multiplications in large finite fields. As a result, we can break MiMC-129/129 with 38 rounds with time and data complexity \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{65.5}$$\\end{document} and \\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$2^{60.2}$$\\end{document} respectively and with negligible memory; this attack invalidates one of the security claims of the designers. Our attack indicates that for MiMC-129/129 the full 82 rounds are necessary even with restrictions on the memory available to the attacker. For variants of MiMC with larger keys, we present new attacks with reduced complexity. Our results do not affect the security claims of the full round MiMC.", 
    "editor": [
      {
        "familyName": "Paterson", 
        "givenName": "Kenneth G.", 
        "type": "Person"
      }, 
      {
        "familyName": "Stebila", 
        "givenName": "Douglas", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-030-38471-5_8", 
    "isAccessibleForFree": false, 
    "isPartOf": {
      "isbn": [
        "978-3-030-38470-8", 
        "978-3-030-38471-5"
      ], 
      "name": "Selected Areas in Cryptography \u2013 SAC 2019", 
      "type": "Book"
    }, 
    "keywords": [
      "cryptographic primitives", 
      "data complexity", 
      "secure multi-party computation", 
      "security claims", 
      "multi-party computation", 
      "symmetric cryptographic primitives", 
      "interpolation attack", 
      "symmetric-key primitives", 
      "low multiplicative complexity", 
      "large finite fields", 
      "key primitives", 
      "number of multiplications", 
      "large keys", 
      "new attacks", 
      "constant memory", 
      "low algebraic degree", 
      "generic attacks", 
      "negligible memory", 
      "block cipher", 
      "primitives", 
      "algebraic cryptanalysis", 
      "multiplicative complexity", 
      "key schedule", 
      "round function", 
      "improved attacks", 
      "simple key schedule", 
      "attacks", 
      "reduced complexity", 
      "complexity", 
      "finite field", 
      "attacker", 
      "cipher", 
      "cryptanalysis", 
      "memory", 
      "security", 
      "designers", 
      "computation", 
      "MIMC", 
      "algebraic degree", 
      "key", 
      "applications", 
      "performance", 
      "multiplication", 
      "rounds", 
      "schedule", 
      "results", 
      "evaluation", 
      "number", 
      "time", 
      "field", 
      "variants", 
      "restriction", 
      "degree", 
      "function", 
      "claims", 
      "low degree", 
      "careful evaluation", 
      "paper"
    ], 
    "name": "Improved Interpolation Attacks on Cryptographic Primitives of Low Algebraic Degree", 
    "pagination": "171-193", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1123979163"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-030-38471-5_8"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-030-38471-5_8", 
      "https://app.dimensions.ai/details/publication/pub.1123979163"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-09-02T16:10", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/chapter/chapter_115.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-030-38471-5_8"
  }
]
 

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/978-3-030-38471-5_8'

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/978-3-030-38471-5_8'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38471-5_8'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/978-3-030-38471-5_8'


 

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

133 TRIPLES      22 PREDICATES      83 URIs      75 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-030-38471-5_8 schema:about anzsrc-for:08
2 anzsrc-for:0802
3 anzsrc-for:0804
4 schema:author Naf3952c742ea488bb92aab17256e06c2
5 schema:datePublished 2020-01-10
6 schema:datePublishedReg 2020-01-10
7 schema:description Symmetric cryptographic primitives with low multiplicative complexity have been proposed to improve the performance of emerging applications such as secure Multi-Party Computation. However, primitives composed of round functions with low algebraic degree require a careful evaluation to assess their security against algebraic cryptanalysis, and in particular interpolation attacks. This paper proposes new low-memory interpolation attacks on symmetric key primitives of low degree. Moreover, we present generic attacks on block ciphers with a simple key schedule; our attacks require either constant memory or constant data complexity. The improved attack is applied to the block cipher MiMC which aims to minimize the number of multiplications in large finite fields. As a result, we can break MiMC-129/129 with 38 rounds with time and data complexity \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{65.5}$$\end{document} and \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{60.2}$$\end{document} respectively and with negligible memory; this attack invalidates one of the security claims of the designers. Our attack indicates that for MiMC-129/129 the full 82 rounds are necessary even with restrictions on the memory available to the attacker. For variants of MiMC with larger keys, we present new attacks with reduced complexity. Our results do not affect the security claims of the full round MiMC.
8 schema:editor Nd5d67462f86f447d90d2cf01baa9b3a0
9 schema:genre chapter
10 schema:isAccessibleForFree false
11 schema:isPartOf Nba572a058a1d42ce83a8cac7048d57f4
12 schema:keywords MIMC
13 algebraic cryptanalysis
14 algebraic degree
15 applications
16 attacker
17 attacks
18 block cipher
19 careful evaluation
20 cipher
21 claims
22 complexity
23 computation
24 constant memory
25 cryptanalysis
26 cryptographic primitives
27 data complexity
28 degree
29 designers
30 evaluation
31 field
32 finite field
33 function
34 generic attacks
35 improved attacks
36 interpolation attack
37 key
38 key primitives
39 key schedule
40 large finite fields
41 large keys
42 low algebraic degree
43 low degree
44 low multiplicative complexity
45 memory
46 multi-party computation
47 multiplication
48 multiplicative complexity
49 negligible memory
50 new attacks
51 number
52 number of multiplications
53 paper
54 performance
55 primitives
56 reduced complexity
57 restriction
58 results
59 round function
60 rounds
61 schedule
62 secure multi-party computation
63 security
64 security claims
65 simple key schedule
66 symmetric cryptographic primitives
67 symmetric-key primitives
68 time
69 variants
70 schema:name Improved Interpolation Attacks on Cryptographic Primitives of Low Algebraic Degree
71 schema:pagination 171-193
72 schema:productId N2d5f49394e5142b9800e38e7aea5eb65
73 N7f1d5e1ffd2f42bbb9639c4bf77a7845
74 schema:publisher Nc4295d0658144c1585f4b83769c9cde2
75 schema:sameAs https://app.dimensions.ai/details/publication/pub.1123979163
76 https://doi.org/10.1007/978-3-030-38471-5_8
77 schema:sdDatePublished 2022-09-02T16:10
78 schema:sdLicense https://scigraph.springernature.com/explorer/license/
79 schema:sdPublisher Ne13d5784dfe94797bd66c946387d0df6
80 schema:url https://doi.org/10.1007/978-3-030-38471-5_8
81 sgo:license sg:explorer/license/
82 sgo:sdDataset chapters
83 rdf:type schema:Chapter
84 N0f99d0c7ff5f4fb9911e58c713f85990 rdf:first N2dfee50568d24e5987ee53fc405d04be
85 rdf:rest rdf:nil
86 N141b67d0a4564692ab1b83628fb4153c schema:familyName Paterson
87 schema:givenName Kenneth G.
88 rdf:type schema:Person
89 N2d5f49394e5142b9800e38e7aea5eb65 schema:name dimensions_id
90 schema:value pub.1123979163
91 rdf:type schema:PropertyValue
92 N2dfee50568d24e5987ee53fc405d04be schema:familyName Stebila
93 schema:givenName Douglas
94 rdf:type schema:Person
95 N7f1d5e1ffd2f42bbb9639c4bf77a7845 schema:name doi
96 schema:value 10.1007/978-3-030-38471-5_8
97 rdf:type schema:PropertyValue
98 Naf3952c742ea488bb92aab17256e06c2 rdf:first sg:person.012162474100.06
99 rdf:rest Nf3bc3d339e4044a681338b6b67bedca6
100 Nba572a058a1d42ce83a8cac7048d57f4 schema:isbn 978-3-030-38470-8
101 978-3-030-38471-5
102 schema:name Selected Areas in Cryptography – SAC 2019
103 rdf:type schema:Book
104 Nc4295d0658144c1585f4b83769c9cde2 schema:name Springer Nature
105 rdf:type schema:Organisation
106 Nd5d67462f86f447d90d2cf01baa9b3a0 rdf:first N141b67d0a4564692ab1b83628fb4153c
107 rdf:rest N0f99d0c7ff5f4fb9911e58c713f85990
108 Ne13d5784dfe94797bd66c946387d0df6 schema:name Springer Nature - SN SciGraph project
109 rdf:type schema:Organization
110 Nf3bc3d339e4044a681338b6b67bedca6 rdf:first sg:person.011115044357.39
111 rdf:rest rdf:nil
112 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
113 schema:name Information and Computing Sciences
114 rdf:type schema:DefinedTerm
115 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
116 schema:name Computation Theory and Mathematics
117 rdf:type schema:DefinedTerm
118 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
119 schema:name Data Format
120 rdf:type schema:DefinedTerm
121 sg:person.011115044357.39 schema:affiliation grid-institutes:grid.5596.f
122 schema:familyName Preneel
123 schema:givenName Bart
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39
125 rdf:type schema:Person
126 sg:person.012162474100.06 schema:affiliation grid-institutes:grid.5596.f
127 schema:familyName Li
128 schema:givenName Chaoyun
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012162474100.06
130 rdf:type schema:Person
131 grid-institutes:grid.5596.f schema:alternateName imec-COSIC, Department Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium
132 schema:name imec-COSIC, Department Electrical Engineering (ESAT), KU Leuven, Leuven, Belgium
133 rdf:type schema:Organization
 




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


...