An Asymptotically Tight Security Analysis of the Iterated Even-Mansour Cipher View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2012

AUTHORS

Rodolphe Lampe , Jacques Patarin , Yannick Seurin

ABSTRACT

We analyze the security of the iterated Even-Mansour cipher (a.k.a. key-alternating cipher), a very simple and natural construction of a blockcipher in the random permutation model. This construction, first considered by Even and Mansour (J. Cryptology, 1997) with a single permutation, was recently generalized to use t permutations in the work of Bogdanov et al. (EUROCRYPT 2012). They proved that the construction is secure up to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ \mathcal{O} (N^{2/3})$\end{document} queries (where N is the domain size of the permutations), as soon as the number t of rounds is 2 or more. This is tight for t = 2, however in the general case the best known attack requires Ω(Nt/(t + 1)) queries. In this paper, we give asymptotically tight security proofs for two types of adversaries:for non-adaptive chosen-plaintext adversaries, we prove that the construction achieves an optimal security bound of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ \mathcal{O} (N^{t/(t+1)})$\end{document} queries;for adaptive chosen-plaintext and ciphertext adversaries, we prove that the construction achieves security up to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ \mathcal{O} (N^{t/(t+2)})$\end{document} queries (for t even). This improves previous results for t ≥ 6.Our proof crucially relies on the use of a coupling to upper-bound the statistical distance of the outputs of the iterated Even-Mansour cipher to the uniform distribution. More... »

PAGES

278-295

Book

TITLE

Advances in Cryptology – ASIACRYPT 2012

ISBN

978-3-642-34960-7
978-3-642-34961-4

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-642-34961-4_18

DOI

http://dx.doi.org/10.1007/978-3-642-34961-4_18

DIMENSIONS

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


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": "University of Versailles, France", 
          "id": "http://www.grid.ac/institutes/grid.12832.3a", 
          "name": [
            "University of Versailles, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Lampe", 
        "givenName": "Rodolphe", 
        "id": "sg:person.013502647333.10", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013502647333.10"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "University of Versailles, France", 
          "id": "http://www.grid.ac/institutes/grid.12832.3a", 
          "name": [
            "University of Versailles, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Patarin", 
        "givenName": "Jacques", 
        "id": "sg:person.012254315647.07", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012254315647.07"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "ANSSI, Paris, France", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "ANSSI, Paris, France"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Seurin", 
        "givenName": "Yannick", 
        "id": "sg:person.011724731171.01", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724731171.01"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2012", 
    "datePublishedReg": "2012-01-01", 
    "description": "We analyze the security of the iterated Even-Mansour cipher (a.k.a. key-alternating cipher), a very simple and natural construction of a blockcipher in the random permutation model. This construction, first considered by Even and Mansour (J. Cryptology, 1997) with a single permutation, was recently generalized to use t permutations in the work of Bogdanov et al. (EUROCRYPT 2012). They proved that the construction is secure up to \\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}$ \\mathcal{O} (N^{2/3})$\\end{document} queries (where N is the domain size of the permutations), as soon as the number t of rounds is 2 or more. This is tight for t\u2009=\u20092, however in the general case the best known attack requires \u03a9(Nt/(t\u2009+\u20091)) queries. In this paper, we give asymptotically tight security proofs for two types of adversaries:for non-adaptive chosen-plaintext adversaries, we prove that the construction achieves an optimal security bound 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}$ \\mathcal{O} (N^{t/(t+1)})$\\end{document} queries;for adaptive chosen-plaintext and ciphertext adversaries, we prove that the construction achieves security up to \\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}$ \\mathcal{O} (N^{t/(t+2)})$\\end{document} queries (for t even). This improves previous results for t\u2009\u2265\u20096.Our proof crucially relies on the use of a coupling to upper-bound the statistical distance of the outputs of the iterated Even-Mansour cipher to the uniform distribution.", 
    "editor": [
      {
        "familyName": "Wang", 
        "givenName": "Xiaoyun", 
        "type": "Person"
      }, 
      {
        "familyName": "Sako", 
        "givenName": "Kazue", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-642-34961-4_18", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-642-34960-7", 
        "978-3-642-34961-4"
      ], 
      "name": "Advances in Cryptology \u2013 ASIACRYPT 2012", 
      "type": "Book"
    }, 
    "keywords": [
      "natural construction", 
      "random permutation model", 
      "general case", 
      "statistical distance", 
      "permutation model", 
      "single permutation", 
      "number t", 
      "tight security proof", 
      "Tight Security Analysis", 
      "permutations", 
      "Bogdanov et al", 
      "et al", 
      "proof", 
      "previous results", 
      "construction", 
      "security proof", 
      "types of adversaries", 
      "uniform distribution", 
      "cipher", 
      "model", 
      "Mansour", 
      "adversary", 
      "optimal security", 
      "coupling", 
      "distance", 
      "output", 
      "distribution", 
      "security analysis", 
      "Even", 
      "work", 
      "al", 
      "cases", 
      "results", 
      "analysis", 
      "security", 
      "blockcipher", 
      "queries", 
      "attacks", 
      "types", 
      "use", 
      "rounds", 
      "paper", 
      "Even-Mansour cipher", 
      "ciphertext adversaries"
    ], 
    "name": "An Asymptotically Tight Security Analysis of the Iterated Even-Mansour Cipher", 
    "pagination": "278-295", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1049788999"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-642-34961-4_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-642-34961-4_18", 
      "https://app.dimensions.ai/details/publication/pub.1049788999"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:18", 
    "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_446.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-642-34961-4_18"
  }
]
 

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-642-34961-4_18'

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-642-34961-4_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-642-34961-4_18'

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-642-34961-4_18'


 

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

125 TRIPLES      22 PREDICATES      69 URIs      62 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-642-34961-4_18 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author N31dd35371ef143d1a22324f35ef7d3c9
4 schema:datePublished 2012
5 schema:datePublishedReg 2012-01-01
6 schema:description We analyze the security of the iterated Even-Mansour cipher (a.k.a. key-alternating cipher), a very simple and natural construction of a blockcipher in the random permutation model. This construction, first considered by Even and Mansour (J. Cryptology, 1997) with a single permutation, was recently generalized to use t permutations in the work of Bogdanov et al. (EUROCRYPT 2012). They proved that the construction is secure up to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ \mathcal{O} (N^{2/3})$\end{document} queries (where N is the domain size of the permutations), as soon as the number t of rounds is 2 or more. This is tight for t = 2, however in the general case the best known attack requires Ω(Nt/(t + 1)) queries. In this paper, we give asymptotically tight security proofs for two types of adversaries:for non-adaptive chosen-plaintext adversaries, we prove that the construction achieves an optimal security bound of \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ \mathcal{O} (N^{t/(t+1)})$\end{document} queries;for adaptive chosen-plaintext and ciphertext adversaries, we prove that the construction achieves security up to \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$ \mathcal{O} (N^{t/(t+2)})$\end{document} queries (for t even). This improves previous results for t ≥ 6.Our proof crucially relies on the use of a coupling to upper-bound the statistical distance of the outputs of the iterated Even-Mansour cipher to the uniform distribution.
7 schema:editor N769193a325d24ca7a3a6e83377da7060
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N4984f1ec4112451680d8a485b76097e8
11 schema:keywords Bogdanov et al
12 Even
13 Even-Mansour cipher
14 Mansour
15 Tight Security Analysis
16 adversary
17 al
18 analysis
19 attacks
20 blockcipher
21 cases
22 cipher
23 ciphertext adversaries
24 construction
25 coupling
26 distance
27 distribution
28 et al
29 general case
30 model
31 natural construction
32 number t
33 optimal security
34 output
35 paper
36 permutation model
37 permutations
38 previous results
39 proof
40 queries
41 random permutation model
42 results
43 rounds
44 security
45 security analysis
46 security proof
47 single permutation
48 statistical distance
49 tight security proof
50 types
51 types of adversaries
52 uniform distribution
53 use
54 work
55 schema:name An Asymptotically Tight Security Analysis of the Iterated Even-Mansour Cipher
56 schema:pagination 278-295
57 schema:productId Nc5c9f5027604462081c1083377818057
58 Need8c2ea16764d0f96c4130391e8dca3
59 schema:publisher N23240003a9fa4ed3a2a1a99493f49cb3
60 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049788999
61 https://doi.org/10.1007/978-3-642-34961-4_18
62 schema:sdDatePublished 2022-11-24T21:18
63 schema:sdLicense https://scigraph.springernature.com/explorer/license/
64 schema:sdPublisher Ncb5a6cb4f9a8459eb7bc27cda360c5a9
65 schema:url https://doi.org/10.1007/978-3-642-34961-4_18
66 sgo:license sg:explorer/license/
67 sgo:sdDataset chapters
68 rdf:type schema:Chapter
69 N161f0392372c464f8eeee7490abf89dc schema:familyName Wang
70 schema:givenName Xiaoyun
71 rdf:type schema:Person
72 N23240003a9fa4ed3a2a1a99493f49cb3 schema:name Springer Nature
73 rdf:type schema:Organisation
74 N31dd35371ef143d1a22324f35ef7d3c9 rdf:first sg:person.013502647333.10
75 rdf:rest Nff1340ad76b24750bb4088642f0971b4
76 N4984f1ec4112451680d8a485b76097e8 schema:isbn 978-3-642-34960-7
77 978-3-642-34961-4
78 schema:name Advances in Cryptology – ASIACRYPT 2012
79 rdf:type schema:Book
80 N4d64541743704686885cb9d9b01fd760 schema:familyName Sako
81 schema:givenName Kazue
82 rdf:type schema:Person
83 N769193a325d24ca7a3a6e83377da7060 rdf:first N161f0392372c464f8eeee7490abf89dc
84 rdf:rest Ndbc2c747138b4ab6a899834bc24af383
85 Nc5c9f5027604462081c1083377818057 schema:name dimensions_id
86 schema:value pub.1049788999
87 rdf:type schema:PropertyValue
88 Ncb5a6cb4f9a8459eb7bc27cda360c5a9 schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
90 Ndbc2c747138b4ab6a899834bc24af383 rdf:first N4d64541743704686885cb9d9b01fd760
91 rdf:rest rdf:nil
92 Need8c2ea16764d0f96c4130391e8dca3 schema:name doi
93 schema:value 10.1007/978-3-642-34961-4_18
94 rdf:type schema:PropertyValue
95 Nfde0ff5348c74a0b97523e4d26fb0b9b rdf:first sg:person.011724731171.01
96 rdf:rest rdf:nil
97 Nff1340ad76b24750bb4088642f0971b4 rdf:first sg:person.012254315647.07
98 rdf:rest Nfde0ff5348c74a0b97523e4d26fb0b9b
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
103 schema:name Data Format
104 rdf:type schema:DefinedTerm
105 sg:person.011724731171.01 schema:affiliation grid-institutes:None
106 schema:familyName Seurin
107 schema:givenName Yannick
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724731171.01
109 rdf:type schema:Person
110 sg:person.012254315647.07 schema:affiliation grid-institutes:grid.12832.3a
111 schema:familyName Patarin
112 schema:givenName Jacques
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012254315647.07
114 rdf:type schema:Person
115 sg:person.013502647333.10 schema:affiliation grid-institutes:grid.12832.3a
116 schema:familyName Lampe
117 schema:givenName Rodolphe
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.013502647333.10
119 rdf:type schema:Person
120 grid-institutes:None schema:alternateName ANSSI, Paris, France
121 schema:name ANSSI, Paris, France
122 rdf:type schema:Organization
123 grid-institutes:grid.12832.3a schema:alternateName University of Versailles, France
124 schema:name University of Versailles, France
125 rdf:type schema:Organization
 




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


...