How to Build an Ideal Cipher: The Indifferentiability of the Feistel Construction View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2014-11-01

AUTHORS

Jean-Sébastien Coron, Thomas Holenstein, Robin Künzler, Jacques Patarin, Yannick Seurin, Stefano Tessaro

ABSTRACT

This paper provides the first provably secure construction of an invertible random permutation (and of an ideal cipher) from a public random function that can be evaluated by all parties in the system, including the adversary. The associated security goal was formalized via the notion of indifferentiability by Maurer et al. (TCC 2004). The problem is the natural extension of that of building (invertible) random permutations from (private) random functions, first solved by Luby and Rackoff (SIAM J Comput 17(2):373–386, 1988) via the four-round Feistel construction. As our main result, we prove that the Feistel construction with fourteen rounds is indifferentiable from an invertible random permutation. We also provide a new lower bound showing that five rounds are not sufficient to achieve indifferentiability. A major corollary of our result is the equivalence (in a well-defined sense) of the random oracle model and the ideal cipher model. More... »

PAGES

61-114

References to SciGraph publications

  • 1996. The Exact Security of Digital Signatures-How to Sign with RSA and Rabin in ADVANCES IN CRYPTOLOGY — EUROCRYPT ’96
  • 1997-06. A construction of a cipher from a single pseudorandom permutation in JOURNAL OF CRYPTOLOGY
  • 2008-01-01. The Random Oracle Model and the Ideal Cipher Model Are Equivalent in ADVANCES IN CRYPTOLOGY – CRYPTO 2008
  • 2004-07-30. Short Signatures from the Weil Pairing in JOURNAL OF CRYPTOLOGY
  • 2014. Tight Security Bounds for Key-Alternating Ciphers in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2014
  • 2002-04-29. Indistinguishability of Random Systems in ADVANCES IN CRYPTOLOGY — EUROCRYPT 2002
  • 2002-02-08. Ciphers with Arbitrary Finite Domains in TOPICS IN CRYPTOLOGY — CT-RSA 2002
  • 2005. Merkle-Damgård Revisited: How to Construct a Hash Function in ADVANCES IN CRYPTOLOGY – CRYPTO 2005
  • 2008-01-01. Constructing Cryptographic Hash Functions from Fixed-Key Blockciphers in ADVANCES IN CRYPTOLOGY – CRYPTO 2008
  • 2006. On the Relation Between the Ideal Cipher and the Random Oracle Models in THEORY OF CRYPTOGRAPHY
  • 2006. The Ideal-Cipher Model, Revisited: An Uninstantiable Blockcipher-Based Hash Function in FAST SOFTWARE ENCRYPTION
  • 1990. A Certified Digital Signature in ADVANCES IN CRYPTOLOGY — CRYPTO’ 89 PROCEEDINGS
  • 2009. Indifferentiability of Permutation-Based Compression Functions and Tree-Based Modes of Operation, with Applications to MD6 in FAST SOFTWARE ENCRYPTION
  • 2012. Key-Alternating Ciphers in a Provable Setting: Encryption Using a Small Number of Public Permutations in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2012
  • 2001-01. How to Protect DES Against Exhaustive Key Search (an Analysis of DESX) in JOURNAL OF CRYPTOLOGY
  • 2000-12-01. How To Prove Yourself: Practical Solutions to Identification and Signature Problems in ADVANCES IN CRYPTOLOGY — CRYPTO’ 86
  • 2003-05-13. A Theoretical Treatment of Related-Key Attacks: RKA-PRPs, RKA-PRFs, and Applications in ADVANCES IN CRYPTOLOGY — EUROCRYPT 2003
  • 2013. On the Indifferentiability of Key-Alternating Ciphers in ADVANCES IN CRYPTOLOGY – CRYPTO 2013
  • 2004. Indifferentiability, Impossibility Results on Reductions, and Applications to the Random Oracle Methodology in THEORY OF CRYPTOGRAPHY
  • 2008. On the Indifferentiability of the Sponge Construction in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2008
  • 2008-01-01. Security/Efficiency Tradeoffs for Permutation-Based Hashing in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2008
  • 1995. Optimal asymmetric encryption in ADVANCES IN CRYPTOLOGY — EUROCRYPT'94
  • 2009. Adaptive Zero-Knowledge Proofs and Adaptively Secure Oblivious Transfer in THEORY OF CRYPTOGRAPHY
  • 2014. Minimizing the Two-Round Even-Mansour Cipher in ADVANCES IN CRYPTOLOGY – CRYPTO 2014
  • 1990. A Design Principle for Hash Functions in ADVANCES IN CRYPTOLOGY — CRYPTO’ 89 PROCEEDINGS
  • 2006. The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2006
  • 2013. How to Construct an Ideal Cipher from a Small Set of Public Permutations in ADVANCES IN CRYPTOLOGY - ASIACRYPT 2013
  • 2011. Careful with Composition: Limitations of the Indifferentiability Framework in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2011
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00145-014-9189-6

    DOI

    http://dx.doi.org/10.1007/s00145-014-9189-6

    DIMENSIONS

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


    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 Luxembourg, Luxembourg, Luxembourg", 
              "id": "http://www.grid.ac/institutes/grid.16008.3f", 
              "name": [
                "University of Luxembourg, Luxembourg, Luxembourg"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Coron", 
            "givenName": "Jean-S\u00e9bastien", 
            "id": "sg:person.014122543616.98", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014122543616.98"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland", 
              "id": "http://www.grid.ac/institutes/grid.5801.c", 
              "name": [
                "Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Holenstein", 
            "givenName": "Thomas", 
            "id": "sg:person.015016630125.71", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015016630125.71"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland", 
              "id": "http://www.grid.ac/institutes/grid.5801.c", 
              "name": [
                "Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland"
              ], 
              "type": "Organization"
            }, 
            "familyName": "K\u00fcnzler", 
            "givenName": "Robin", 
            "id": "sg:person.012670633061.15", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012670633061.15"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "University of Versailles-Saint-Quentin, Versailles, France", 
              "id": "http://www.grid.ac/institutes/grid.12832.3a", 
              "name": [
                "University of Versailles-Saint-Quentin, 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"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, University of California, Santa Barbara, Santa Barbara, CA, USA", 
              "id": "http://www.grid.ac/institutes/grid.133342.4", 
              "name": [
                "Department of Computer Science, University of California, Santa Barbara, Santa Barbara, CA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Tessaro", 
            "givenName": "Stefano", 
            "id": "sg:person.014325641465.55", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014325641465.55"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-20465-4_27", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040137381", 
              "https://doi.org/10.1007/978-3-642-20465-4_27"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/0-387-34805-0_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1034359707", 
              "https://doi.org/10.1007/0-387-34805-0_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11681878_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012153018", 
              "https://doi.org/10.1007/11681878_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-78967-3_11", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048096154", 
              "https://doi.org/10.1007/978-3-540-78967-3_11"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-00457-5_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017631368", 
              "https://doi.org/10.1007/978-3-642-00457-5_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-29011-4_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1041647739", 
              "https://doi.org/10.1007/978-3-642-29011-4_5"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-45760-7_9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1002956912", 
              "https://doi.org/10.1007/3-540-45760-7_9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11799313_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030756500", 
              "https://doi.org/10.1007/11799313_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-24638-1_2", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1050815296", 
              "https://doi.org/10.1007/978-3-540-24638-1_2"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-55220-5_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1020563393", 
              "https://doi.org/10.1007/978-3-642-55220-5_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00145-004-0314-9", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1000134872", 
              "https://doi.org/10.1007/s00145-004-0314-9"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-44371-2_3", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008932700", 
              "https://doi.org/10.1007/978-3-662-44371-2_3"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-78967-3_13", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042749994", 
              "https://doi.org/10.1007/978-3-540-78967-3_13"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-85174-5_1", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004027439", 
              "https://doi.org/10.1007/978-3-540-85174-5_1"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-40041-4_29", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1042642282", 
              "https://doi.org/10.1007/978-3-642-40041-4_29"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11535218_26", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015438097", 
              "https://doi.org/10.1007/11535218_26"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11761679_25", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031026722", 
              "https://doi.org/10.1007/11761679_25"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68339-9_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1040493675", 
              "https://doi.org/10.1007/3-540-68339-9_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/0-387-34805-0_39", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026402674", 
              "https://doi.org/10.1007/0-387-34805-0_39"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03317-9_7", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1008198067", 
              "https://doi.org/10.1007/978-3-642-03317-9_7"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s001459900025", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1016356827", 
              "https://doi.org/10.1007/s001459900025"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-540-85174-5_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1012686200", 
              "https://doi.org/10.1007/978-3-540-85174-5_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-39200-9_31", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019544958", 
              "https://doi.org/10.1007/3-540-39200-9_31"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0053428", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1035370576", 
              "https://doi.org/10.1007/bfb0053428"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-47721-7_12", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038535610", 
              "https://doi.org/10.1007/3-540-47721-7_12"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-46035-7_8", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1031413093", 
              "https://doi.org/10.1007/3-540-46035-7_8"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-42033-7_23", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1044227148", 
              "https://doi.org/10.1007/978-3-642-42033-7_23"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s001450010015", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038604760", 
              "https://doi.org/10.1007/s001450010015"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2014-11-01", 
        "datePublishedReg": "2014-11-01", 
        "description": "This paper provides the first provably secure construction of an invertible random permutation (and of an ideal cipher) from a public random function that can be evaluated by all parties in the system, including the adversary. The associated security goal was formalized via the notion of indifferentiability by Maurer et al. (TCC 2004). The problem is the natural extension of that of building (invertible) random permutations from (private) random functions, first solved by Luby and Rackoff (SIAM J Comput 17(2):373\u2013386, 1988) via the four-round Feistel construction. As our main result, we prove that the Feistel construction with fourteen rounds is indifferentiable from an invertible random permutation. We also provide a new lower bound showing that five rounds are not sufficient to achieve indifferentiability. A major corollary of our result is the equivalence (in a well-defined sense) of the random oracle model and the ideal cipher model.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00145-014-9189-6", 
        "isAccessibleForFree": true, 
        "isFundedItemOf": [
          {
            "id": "sg:grant.5226666", 
            "type": "MonetaryGrant"
          }
        ], 
        "isPartOf": [
          {
            "id": "sg:journal.1136278", 
            "issn": [
              "0933-2790", 
              "1432-1378"
            ], 
            "name": "Journal of Cryptology", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "29"
          }
        ], 
        "keywords": [
          "construction", 
          "secure construction", 
          "paper", 
          "random permutation", 
          "random function", 
          "parties", 
          "goal", 
          "notion", 
          "model", 
          "permutations", 
          "function", 
          "system", 
          "security goals", 
          "Maurer et al", 
          "et al", 
          "problem", 
          "natural extension", 
          "extension", 
          "Luby", 
          "Rackoff", 
          "main results", 
          "results", 
          "rounds", 
          "corollary", 
          "equivalence", 
          "random oracle model", 
          "oracle model", 
          "public random function", 
          "adversary", 
          "indifferentiability", 
          "al", 
          "cipher model", 
          "ideal cipher", 
          "cipher", 
          "notion of indifferentiability", 
          "Feistel construction", 
          "major corollary", 
          "ideal cipher model"
        ], 
        "name": "How to Build an Ideal Cipher: The Indifferentiability of the Feistel Construction", 
        "pagination": "61-114", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1025760766"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00145-014-9189-6"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00145-014-9189-6", 
          "https://app.dimensions.ai/details/publication/pub.1025760766"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-12-01T06:32", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20221201/entities/gbq_results/article/article_629.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00145-014-9189-6"
      }
    ]
     

    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/s00145-014-9189-6'

    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/s00145-014-9189-6'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00145-014-9189-6'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00145-014-9189-6'


     

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

    256 TRIPLES      21 PREDICATES      90 URIs      54 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00145-014-9189-6 schema:about anzsrc-for:08
    2 anzsrc-for:0804
    3 schema:author N09ffebc4a4c24090b51f26da70c21449
    4 schema:citation sg:pub.10.1007/0-387-34805-0_21
    5 sg:pub.10.1007/0-387-34805-0_39
    6 sg:pub.10.1007/11535218_26
    7 sg:pub.10.1007/11681878_10
    8 sg:pub.10.1007/11761679_25
    9 sg:pub.10.1007/11799313_21
    10 sg:pub.10.1007/3-540-39200-9_31
    11 sg:pub.10.1007/3-540-45760-7_9
    12 sg:pub.10.1007/3-540-46035-7_8
    13 sg:pub.10.1007/3-540-47721-7_12
    14 sg:pub.10.1007/3-540-68339-9_34
    15 sg:pub.10.1007/978-3-540-24638-1_2
    16 sg:pub.10.1007/978-3-540-78967-3_11
    17 sg:pub.10.1007/978-3-540-78967-3_13
    18 sg:pub.10.1007/978-3-540-85174-5_1
    19 sg:pub.10.1007/978-3-540-85174-5_24
    20 sg:pub.10.1007/978-3-642-00457-5_12
    21 sg:pub.10.1007/978-3-642-03317-9_7
    22 sg:pub.10.1007/978-3-642-20465-4_27
    23 sg:pub.10.1007/978-3-642-29011-4_5
    24 sg:pub.10.1007/978-3-642-40041-4_29
    25 sg:pub.10.1007/978-3-642-42033-7_23
    26 sg:pub.10.1007/978-3-642-55220-5_19
    27 sg:pub.10.1007/978-3-662-44371-2_3
    28 sg:pub.10.1007/bfb0053428
    29 sg:pub.10.1007/s00145-004-0314-9
    30 sg:pub.10.1007/s001450010015
    31 sg:pub.10.1007/s001459900025
    32 schema:datePublished 2014-11-01
    33 schema:datePublishedReg 2014-11-01
    34 schema:description This paper provides the first provably secure construction of an invertible random permutation (and of an ideal cipher) from a public random function that can be evaluated by all parties in the system, including the adversary. The associated security goal was formalized via the notion of indifferentiability by Maurer et al. (TCC 2004). The problem is the natural extension of that of building (invertible) random permutations from (private) random functions, first solved by Luby and Rackoff (SIAM J Comput 17(2):373–386, 1988) via the four-round Feistel construction. As our main result, we prove that the Feistel construction with fourteen rounds is indifferentiable from an invertible random permutation. We also provide a new lower bound showing that five rounds are not sufficient to achieve indifferentiability. A major corollary of our result is the equivalence (in a well-defined sense) of the random oracle model and the ideal cipher model.
    35 schema:genre article
    36 schema:isAccessibleForFree true
    37 schema:isPartOf N7e12eb39b27b4023a0a0e6c48fff324b
    38 Na9383afb9020463db470c9f15286e31b
    39 sg:journal.1136278
    40 schema:keywords Feistel construction
    41 Luby
    42 Maurer et al
    43 Rackoff
    44 adversary
    45 al
    46 cipher
    47 cipher model
    48 construction
    49 corollary
    50 equivalence
    51 et al
    52 extension
    53 function
    54 goal
    55 ideal cipher
    56 ideal cipher model
    57 indifferentiability
    58 main results
    59 major corollary
    60 model
    61 natural extension
    62 notion
    63 notion of indifferentiability
    64 oracle model
    65 paper
    66 parties
    67 permutations
    68 problem
    69 public random function
    70 random function
    71 random oracle model
    72 random permutation
    73 results
    74 rounds
    75 secure construction
    76 security goals
    77 system
    78 schema:name How to Build an Ideal Cipher: The Indifferentiability of the Feistel Construction
    79 schema:pagination 61-114
    80 schema:productId Nb28d151bbcbd4b89982cd3c437d5e21e
    81 Nb8c03a939eef44d9a855350d68328c6c
    82 schema:sameAs https://app.dimensions.ai/details/publication/pub.1025760766
    83 https://doi.org/10.1007/s00145-014-9189-6
    84 schema:sdDatePublished 2022-12-01T06:32
    85 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    86 schema:sdPublisher Nf271740332d4441ba37c7df514e85868
    87 schema:url https://doi.org/10.1007/s00145-014-9189-6
    88 sgo:license sg:explorer/license/
    89 sgo:sdDataset articles
    90 rdf:type schema:ScholarlyArticle
    91 N09ffebc4a4c24090b51f26da70c21449 rdf:first sg:person.014122543616.98
    92 rdf:rest Nacf1c40d29884b2d87ba768510b3f5f4
    93 N42149b47412b4141bffead623fd6f81f rdf:first sg:person.012670633061.15
    94 rdf:rest N995e01980f8a4f1e94cebd7b523586c4
    95 N6107b74992574586bdd528a4304f3cdf rdf:first sg:person.011724731171.01
    96 rdf:rest Nd125d2f959f04c5982e0bcdaac2edeed
    97 N7e12eb39b27b4023a0a0e6c48fff324b schema:volumeNumber 29
    98 rdf:type schema:PublicationVolume
    99 N995e01980f8a4f1e94cebd7b523586c4 rdf:first sg:person.012254315647.07
    100 rdf:rest N6107b74992574586bdd528a4304f3cdf
    101 Na9383afb9020463db470c9f15286e31b schema:issueNumber 1
    102 rdf:type schema:PublicationIssue
    103 Nacf1c40d29884b2d87ba768510b3f5f4 rdf:first sg:person.015016630125.71
    104 rdf:rest N42149b47412b4141bffead623fd6f81f
    105 Nb28d151bbcbd4b89982cd3c437d5e21e schema:name dimensions_id
    106 schema:value pub.1025760766
    107 rdf:type schema:PropertyValue
    108 Nb8c03a939eef44d9a855350d68328c6c schema:name doi
    109 schema:value 10.1007/s00145-014-9189-6
    110 rdf:type schema:PropertyValue
    111 Nd125d2f959f04c5982e0bcdaac2edeed rdf:first sg:person.014325641465.55
    112 rdf:rest rdf:nil
    113 Nf271740332d4441ba37c7df514e85868 schema:name Springer Nature - SN SciGraph project
    114 rdf:type schema:Organization
    115 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    116 schema:name Information and Computing Sciences
    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:grant.5226666 http://pending.schema.org/fundedItem sg:pub.10.1007/s00145-014-9189-6
    122 rdf:type schema:MonetaryGrant
    123 sg:journal.1136278 schema:issn 0933-2790
    124 1432-1378
    125 schema:name Journal of Cryptology
    126 schema:publisher Springer Nature
    127 rdf:type schema:Periodical
    128 sg:person.011724731171.01 schema:affiliation grid-institutes:None
    129 schema:familyName Seurin
    130 schema:givenName Yannick
    131 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724731171.01
    132 rdf:type schema:Person
    133 sg:person.012254315647.07 schema:affiliation grid-institutes:grid.12832.3a
    134 schema:familyName Patarin
    135 schema:givenName Jacques
    136 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012254315647.07
    137 rdf:type schema:Person
    138 sg:person.012670633061.15 schema:affiliation grid-institutes:grid.5801.c
    139 schema:familyName Künzler
    140 schema:givenName Robin
    141 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012670633061.15
    142 rdf:type schema:Person
    143 sg:person.014122543616.98 schema:affiliation grid-institutes:grid.16008.3f
    144 schema:familyName Coron
    145 schema:givenName Jean-Sébastien
    146 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014122543616.98
    147 rdf:type schema:Person
    148 sg:person.014325641465.55 schema:affiliation grid-institutes:grid.133342.4
    149 schema:familyName Tessaro
    150 schema:givenName Stefano
    151 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014325641465.55
    152 rdf:type schema:Person
    153 sg:person.015016630125.71 schema:affiliation grid-institutes:grid.5801.c
    154 schema:familyName Holenstein
    155 schema:givenName Thomas
    156 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015016630125.71
    157 rdf:type schema:Person
    158 sg:pub.10.1007/0-387-34805-0_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1034359707
    159 https://doi.org/10.1007/0-387-34805-0_21
    160 rdf:type schema:CreativeWork
    161 sg:pub.10.1007/0-387-34805-0_39 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026402674
    162 https://doi.org/10.1007/0-387-34805-0_39
    163 rdf:type schema:CreativeWork
    164 sg:pub.10.1007/11535218_26 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015438097
    165 https://doi.org/10.1007/11535218_26
    166 rdf:type schema:CreativeWork
    167 sg:pub.10.1007/11681878_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012153018
    168 https://doi.org/10.1007/11681878_10
    169 rdf:type schema:CreativeWork
    170 sg:pub.10.1007/11761679_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031026722
    171 https://doi.org/10.1007/11761679_25
    172 rdf:type schema:CreativeWork
    173 sg:pub.10.1007/11799313_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030756500
    174 https://doi.org/10.1007/11799313_21
    175 rdf:type schema:CreativeWork
    176 sg:pub.10.1007/3-540-39200-9_31 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019544958
    177 https://doi.org/10.1007/3-540-39200-9_31
    178 rdf:type schema:CreativeWork
    179 sg:pub.10.1007/3-540-45760-7_9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1002956912
    180 https://doi.org/10.1007/3-540-45760-7_9
    181 rdf:type schema:CreativeWork
    182 sg:pub.10.1007/3-540-46035-7_8 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031413093
    183 https://doi.org/10.1007/3-540-46035-7_8
    184 rdf:type schema:CreativeWork
    185 sg:pub.10.1007/3-540-47721-7_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038535610
    186 https://doi.org/10.1007/3-540-47721-7_12
    187 rdf:type schema:CreativeWork
    188 sg:pub.10.1007/3-540-68339-9_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040493675
    189 https://doi.org/10.1007/3-540-68339-9_34
    190 rdf:type schema:CreativeWork
    191 sg:pub.10.1007/978-3-540-24638-1_2 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050815296
    192 https://doi.org/10.1007/978-3-540-24638-1_2
    193 rdf:type schema:CreativeWork
    194 sg:pub.10.1007/978-3-540-78967-3_11 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048096154
    195 https://doi.org/10.1007/978-3-540-78967-3_11
    196 rdf:type schema:CreativeWork
    197 sg:pub.10.1007/978-3-540-78967-3_13 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042749994
    198 https://doi.org/10.1007/978-3-540-78967-3_13
    199 rdf:type schema:CreativeWork
    200 sg:pub.10.1007/978-3-540-85174-5_1 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004027439
    201 https://doi.org/10.1007/978-3-540-85174-5_1
    202 rdf:type schema:CreativeWork
    203 sg:pub.10.1007/978-3-540-85174-5_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012686200
    204 https://doi.org/10.1007/978-3-540-85174-5_24
    205 rdf:type schema:CreativeWork
    206 sg:pub.10.1007/978-3-642-00457-5_12 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017631368
    207 https://doi.org/10.1007/978-3-642-00457-5_12
    208 rdf:type schema:CreativeWork
    209 sg:pub.10.1007/978-3-642-03317-9_7 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008198067
    210 https://doi.org/10.1007/978-3-642-03317-9_7
    211 rdf:type schema:CreativeWork
    212 sg:pub.10.1007/978-3-642-20465-4_27 schema:sameAs https://app.dimensions.ai/details/publication/pub.1040137381
    213 https://doi.org/10.1007/978-3-642-20465-4_27
    214 rdf:type schema:CreativeWork
    215 sg:pub.10.1007/978-3-642-29011-4_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041647739
    216 https://doi.org/10.1007/978-3-642-29011-4_5
    217 rdf:type schema:CreativeWork
    218 sg:pub.10.1007/978-3-642-40041-4_29 schema:sameAs https://app.dimensions.ai/details/publication/pub.1042642282
    219 https://doi.org/10.1007/978-3-642-40041-4_29
    220 rdf:type schema:CreativeWork
    221 sg:pub.10.1007/978-3-642-42033-7_23 schema:sameAs https://app.dimensions.ai/details/publication/pub.1044227148
    222 https://doi.org/10.1007/978-3-642-42033-7_23
    223 rdf:type schema:CreativeWork
    224 sg:pub.10.1007/978-3-642-55220-5_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020563393
    225 https://doi.org/10.1007/978-3-642-55220-5_19
    226 rdf:type schema:CreativeWork
    227 sg:pub.10.1007/978-3-662-44371-2_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008932700
    228 https://doi.org/10.1007/978-3-662-44371-2_3
    229 rdf:type schema:CreativeWork
    230 sg:pub.10.1007/bfb0053428 schema:sameAs https://app.dimensions.ai/details/publication/pub.1035370576
    231 https://doi.org/10.1007/bfb0053428
    232 rdf:type schema:CreativeWork
    233 sg:pub.10.1007/s00145-004-0314-9 schema:sameAs https://app.dimensions.ai/details/publication/pub.1000134872
    234 https://doi.org/10.1007/s00145-004-0314-9
    235 rdf:type schema:CreativeWork
    236 sg:pub.10.1007/s001450010015 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038604760
    237 https://doi.org/10.1007/s001450010015
    238 rdf:type schema:CreativeWork
    239 sg:pub.10.1007/s001459900025 schema:sameAs https://app.dimensions.ai/details/publication/pub.1016356827
    240 https://doi.org/10.1007/s001459900025
    241 rdf:type schema:CreativeWork
    242 grid-institutes:None schema:alternateName ANSSI, Paris, France
    243 schema:name ANSSI, Paris, France
    244 rdf:type schema:Organization
    245 grid-institutes:grid.12832.3a schema:alternateName University of Versailles-Saint-Quentin, Versailles, France
    246 schema:name University of Versailles-Saint-Quentin, Versailles, France
    247 rdf:type schema:Organization
    248 grid-institutes:grid.133342.4 schema:alternateName Department of Computer Science, University of California, Santa Barbara, Santa Barbara, CA, USA
    249 schema:name Department of Computer Science, University of California, Santa Barbara, Santa Barbara, CA, USA
    250 rdf:type schema:Organization
    251 grid-institutes:grid.16008.3f schema:alternateName University of Luxembourg, Luxembourg, Luxembourg
    252 schema:name University of Luxembourg, Luxembourg, Luxembourg
    253 rdf:type schema:Organization
    254 grid-institutes:grid.5801.c schema:alternateName Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland
    255 schema:name Department of Computer Science, ETH Zurich, 8092, Zurich, Switzerland
    256 rdf:type schema:Organization
     




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


    ...