Optimized Interpolation Attacks on LowMC View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015-12-30

AUTHORS

Itai Dinur , Yunwen Liu , Willi Meier , Qingju Wang

ABSTRACT

LowMC is a collection of block cipher families introduced at Eurocrypt 2015 by Albrecht et al. Its design is optimized for instantiations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. A unique feature of LowMC is that its internal affine layers are chosen at random, and thus each block cipher family contains a huge number of instances. The Eurocrypt paper proposed two specific block cipher families of LowMC, having 80-bit and 128-bit keys.In this paper, we mount interpolation attacks (algebraic attacks introduced by Jakobsen and Knudsen) on LowMC, and show that a practically significant fraction of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{-38}$$\end{document} of its 80-bit key instances could be broken \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{23}$$\end{document} times faster than exhaustive search. Moreover, essentially all instances that are claimed to provide 128-bit security could be broken about 1000 times faster. In order to obtain these results we optimize the interpolation attack using several new techniques. In particular, we present an algorithm that combines two main variants of the interpolation attack, and results in an attack which is more efficient than each one. More... »

PAGES

535-560

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-662-48800-3_22

DOI

http://dx.doi.org/10.1007/978-3-662-48800-3_22

DIMENSIONS

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


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": "D\u00e9partement d\u2019Informatique, \u00c9cole Normale Sup\u00e9rieure, Paris, France", 
          "id": "http://www.grid.ac/institutes/grid.503141.2", 
          "name": [
            "D\u00e9partement d\u2019Informatique, \u00c9cole Normale Sup\u00e9rieure, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Dinur", 
        "givenName": "Itai", 
        "id": "sg:person.012046016703.69", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012046016703.69"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Electrical Engineering, ESAT/COSIC, KU Leuven and iMinds, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "Department of Electrical Engineering, ESAT/COSIC, KU Leuven and iMinds, Leuven, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Liu", 
        "givenName": "Yunwen", 
        "id": "sg:person.010457547165.81", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010457547165.81"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "FHNW, Windisch, Switzerland", 
          "id": "http://www.grid.ac/institutes/grid.410380.e", 
          "name": [
            "FHNW, Windisch, Switzerland"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Meier", 
        "givenName": "Willi", 
        "id": "sg:person.07653531142.18", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China", 
          "id": "http://www.grid.ac/institutes/grid.16821.3c", 
          "name": [
            "Department of Electrical Engineering, ESAT/COSIC, KU Leuven and iMinds, Leuven, Belgium", 
            "Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Wang", 
        "givenName": "Qingju", 
        "id": "sg:person.011431743334.40", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431743334.40"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015-12-30", 
    "datePublishedReg": "2015-12-30", 
    "description": "LowMC is a collection of block cipher families introduced at Eurocrypt 2015 by Albrecht et al. Its design is optimized for instantiations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. A unique feature of LowMC is that its internal affine layers are chosen at random, and thus each block cipher family contains a huge number of instances. The Eurocrypt paper proposed two specific block cipher families of LowMC, having 80-bit and 128-bit keys.In this paper, we mount interpolation attacks (algebraic attacks introduced by Jakobsen and Knudsen) on LowMC, and show that a practically significant fraction of \\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^{-38}$$\\end{document} of its 80-bit key instances could be broken \\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^{23}$$\\end{document} times faster than exhaustive search. Moreover, essentially all instances that are claimed to provide 128-bit security could be broken about 1000 times faster. In order to obtain these results we optimize the interpolation attack using several new techniques. In particular, we present an algorithm that combines two main variants of the interpolation attack, and results in an attack which is more efficient than each one.", 
    "editor": [
      {
        "familyName": "Iwata", 
        "givenName": "Tetsu", 
        "type": "Person"
      }, 
      {
        "familyName": "Cheon", 
        "givenName": "Jung Hee", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-662-48800-3_22", 
    "inLanguage": "en", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-662-48799-0", 
        "978-3-662-48800-3"
      ], 
      "name": "Advances in Cryptology \u2013 ASIACRYPT 2015", 
      "type": "Book"
    }, 
    "keywords": [
      "block cipher family", 
      "multi-party computation", 
      "zero-knowledge proofs", 
      "interpolation attack", 
      "homomorphic encryption", 
      "exhaustive search", 
      "LowMC", 
      "affine layers", 
      "huge number", 
      "Albrecht et al", 
      "attacks", 
      "Eurocrypt 2015", 
      "encryption", 
      "key instances", 
      "instances", 
      "instantiation", 
      "security", 
      "algorithm", 
      "new technique", 
      "computation", 
      "unique features", 
      "key", 
      "search", 
      "proof", 
      "collection", 
      "design", 
      "features", 
      "technique", 
      "time", 
      "order", 
      "main variants", 
      "et al", 
      "results", 
      "one", 
      "number", 
      "variants", 
      "layer", 
      "significant fraction", 
      "al", 
      "family", 
      "fraction", 
      "paper", 
      "cipher families", 
      "internal affine layers", 
      "Eurocrypt paper", 
      "specific block cipher families", 
      "Optimized Interpolation Attacks"
    ], 
    "name": "Optimized Interpolation Attacks on LowMC", 
    "pagination": "535-560", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1023561970"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-662-48800-3_22"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-662-48800-3_22", 
      "https://app.dimensions.ai/details/publication/pub.1023561970"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-01-01T19:10", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/chapter/chapter_167.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-662-48800-3_22"
  }
]
 

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-662-48800-3_22'

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-662-48800-3_22'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-662-48800-3_22'

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-662-48800-3_22'


 

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

143 TRIPLES      23 PREDICATES      72 URIs      65 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-662-48800-3_22 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nab05252112e046d4bbbc997ce685e8ec
4 schema:datePublished 2015-12-30
5 schema:datePublishedReg 2015-12-30
6 schema:description LowMC is a collection of block cipher families introduced at Eurocrypt 2015 by Albrecht et al. Its design is optimized for instantiations of multi-party computation, fully homomorphic encryption, and zero-knowledge proofs. A unique feature of LowMC is that its internal affine layers are chosen at random, and thus each block cipher family contains a huge number of instances. The Eurocrypt paper proposed two specific block cipher families of LowMC, having 80-bit and 128-bit keys.In this paper, we mount interpolation attacks (algebraic attacks introduced by Jakobsen and Knudsen) on LowMC, and show that a practically significant fraction of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{-38}$$\end{document} of its 80-bit key instances could be broken \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{23}$$\end{document} times faster than exhaustive search. Moreover, essentially all instances that are claimed to provide 128-bit security could be broken about 1000 times faster. In order to obtain these results we optimize the interpolation attack using several new techniques. In particular, we present an algorithm that combines two main variants of the interpolation attack, and results in an attack which is more efficient than each one.
7 schema:editor N845a2647737d44caa9287606d811b24c
8 schema:genre chapter
9 schema:inLanguage en
10 schema:isAccessibleForFree true
11 schema:isPartOf N679c4d4fb16f423b8e8656f5dfc8036d
12 schema:keywords Albrecht et al
13 Eurocrypt 2015
14 Eurocrypt paper
15 LowMC
16 Optimized Interpolation Attacks
17 affine layers
18 al
19 algorithm
20 attacks
21 block cipher family
22 cipher families
23 collection
24 computation
25 design
26 encryption
27 et al
28 exhaustive search
29 family
30 features
31 fraction
32 homomorphic encryption
33 huge number
34 instances
35 instantiation
36 internal affine layers
37 interpolation attack
38 key
39 key instances
40 layer
41 main variants
42 multi-party computation
43 new technique
44 number
45 one
46 order
47 paper
48 proof
49 results
50 search
51 security
52 significant fraction
53 specific block cipher families
54 technique
55 time
56 unique features
57 variants
58 zero-knowledge proofs
59 schema:name Optimized Interpolation Attacks on LowMC
60 schema:pagination 535-560
61 schema:productId Nc7b4b1eb5ebf49628283057d30b41e09
62 Nd4e7e39b81f143448288293b1a9276e3
63 schema:publisher N4d584815c2944376b4ed686076d8e103
64 schema:sameAs https://app.dimensions.ai/details/publication/pub.1023561970
65 https://doi.org/10.1007/978-3-662-48800-3_22
66 schema:sdDatePublished 2022-01-01T19:10
67 schema:sdLicense https://scigraph.springernature.com/explorer/license/
68 schema:sdPublisher Ncaf3b52fb7aa4ba6ac0e9364b04cea7f
69 schema:url https://doi.org/10.1007/978-3-662-48800-3_22
70 sgo:license sg:explorer/license/
71 sgo:sdDataset chapters
72 rdf:type schema:Chapter
73 N28d707e143914c14bc89735dd8744c9e rdf:first sg:person.010457547165.81
74 rdf:rest N3126e22e43264af39b224189c00471a7
75 N3126e22e43264af39b224189c00471a7 rdf:first sg:person.07653531142.18
76 rdf:rest Nf476f480c30544dd96c2721add4da6ea
77 N4d584815c2944376b4ed686076d8e103 schema:name Springer Nature
78 rdf:type schema:Organisation
79 N53868ad43c954fb88e332fedd29e51dc schema:familyName Iwata
80 schema:givenName Tetsu
81 rdf:type schema:Person
82 N679c4d4fb16f423b8e8656f5dfc8036d schema:isbn 978-3-662-48799-0
83 978-3-662-48800-3
84 schema:name Advances in Cryptology – ASIACRYPT 2015
85 rdf:type schema:Book
86 N845a2647737d44caa9287606d811b24c rdf:first N53868ad43c954fb88e332fedd29e51dc
87 rdf:rest Nbe187d03c00b4d3d8957055c7e98b9b7
88 N8fb668db6f99408fa5339887bae13138 schema:familyName Cheon
89 schema:givenName Jung Hee
90 rdf:type schema:Person
91 Nab05252112e046d4bbbc997ce685e8ec rdf:first sg:person.012046016703.69
92 rdf:rest N28d707e143914c14bc89735dd8744c9e
93 Nbe187d03c00b4d3d8957055c7e98b9b7 rdf:first N8fb668db6f99408fa5339887bae13138
94 rdf:rest rdf:nil
95 Nc7b4b1eb5ebf49628283057d30b41e09 schema:name doi
96 schema:value 10.1007/978-3-662-48800-3_22
97 rdf:type schema:PropertyValue
98 Ncaf3b52fb7aa4ba6ac0e9364b04cea7f schema:name Springer Nature - SN SciGraph project
99 rdf:type schema:Organization
100 Nd4e7e39b81f143448288293b1a9276e3 schema:name dimensions_id
101 schema:value pub.1023561970
102 rdf:type schema:PropertyValue
103 Nf476f480c30544dd96c2721add4da6ea rdf:first sg:person.011431743334.40
104 rdf:rest rdf:nil
105 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
106 schema:name Information and Computing Sciences
107 rdf:type schema:DefinedTerm
108 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
109 schema:name Data Format
110 rdf:type schema:DefinedTerm
111 sg:person.010457547165.81 schema:affiliation grid-institutes:grid.5596.f
112 schema:familyName Liu
113 schema:givenName Yunwen
114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010457547165.81
115 rdf:type schema:Person
116 sg:person.011431743334.40 schema:affiliation grid-institutes:grid.16821.3c
117 schema:familyName Wang
118 schema:givenName Qingju
119 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011431743334.40
120 rdf:type schema:Person
121 sg:person.012046016703.69 schema:affiliation grid-institutes:grid.503141.2
122 schema:familyName Dinur
123 schema:givenName Itai
124 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012046016703.69
125 rdf:type schema:Person
126 sg:person.07653531142.18 schema:affiliation grid-institutes:grid.410380.e
127 schema:familyName Meier
128 schema:givenName Willi
129 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.07653531142.18
130 rdf:type schema:Person
131 grid-institutes:grid.16821.3c schema:alternateName Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China
132 schema:name Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai, China
133 Department of Electrical Engineering, ESAT/COSIC, KU Leuven and iMinds, Leuven, Belgium
134 rdf:type schema:Organization
135 grid-institutes:grid.410380.e schema:alternateName FHNW, Windisch, Switzerland
136 schema:name FHNW, Windisch, Switzerland
137 rdf:type schema:Organization
138 grid-institutes:grid.503141.2 schema:alternateName Département d’Informatique, École Normale Supérieure, Paris, France
139 schema:name Département d’Informatique, École Normale Supérieure, Paris, France
140 rdf:type schema:Organization
141 grid-institutes:grid.5596.f schema:alternateName Department of Electrical Engineering, ESAT/COSIC, KU Leuven and iMinds, Leuven, Belgium
142 schema:name Department of Electrical Engineering, ESAT/COSIC, KU Leuven and iMinds, Leuven, Belgium
143 rdf:type schema:Organization
 




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


...