Analysis of the single-permutation encrypted Davies–Meyer construction View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2018-03-05

AUTHORS

Benoît Cogliati, Yannick Seurin

ABSTRACT

We consider the so-called Encrypted Davies–Meyer (EDM) construction, which turns a permutation P on {0,1}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,1\}^n$$\end{document} into a function from {0,1}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,1\}^n$$\end{document} to {0,1}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,1\}^n$$\end{document} defined as P(P(x)⊕x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(P(x)\oplus x)$$\end{document}. A similar construction using two independent permutations, namely P′(P(x)⊕x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P'(P(x)\oplus x)$$\end{document}, was previously analyzed by Cogliati and Seurin (Advances in cryptology—CRYPTO 2016 (Proceedings, Part I). LNCS, vol 9814, pp. 121–149, 2016) who showed that when P and P′\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P'$$\end{document} are secret and random, then any black-box adversary needs at least roughly 22n/3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{2n/3}$$\end{document} queries to distinguish the construction from a uniformly random function from {0,1}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,1\}^n$$\end{document} to {0,1}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,1\}^n$$\end{document}. In this paper, we focus on the single-permutation variant of the construction. Our main result is that the PRF-security of the single-permutation EDM construction is also (at least) roughly 22n/3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{2n/3}$$\end{document}, in the sense that any black-box adversary needs at least this number of queries to distinguish the construction from a uniformly random function. This yields the first PRP-to-PRF conversion method which uses a single permutation, does not shrink the original domain nor range of the permutation, and provides security beyond the birthday bound. More... »

PAGES

2703-2723

References to SciGraph publications

  • 2006. The Security of Triple Encryption and a Framework for Code-Based Game-Playing Proofs in ADVANCES IN CRYPTOLOGY - EUROCRYPT 2006
  • 2015-04-19. The Indistinguishability of the XOR of Permutations in FAST SOFTWARE ENCRYPTION
  • 2014. Tight Security Bounds for Key-Alternating Ciphers in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2014
  • 1998. Building PRFs from PRPs in ADVANCES IN CRYPTOLOGY — CRYPTO '98
  • 2017-08-02. Encrypted Davies-Meyer and Its Dual: Towards Optimal Security Using Mirror Theory in ADVANCES IN CRYPTOLOGY – CRYPTO 2017
  • 2015-08-01. The Iterated Random Permutation Problem with Applications to Cascade Encryption in ADVANCES IN CRYPTOLOGY -- CRYPTO 2015
  • 2009. The “Coefficients H” Technique in SELECTED AREAS IN CRYPTOGRAPHY
  • 2017-08-02. Information-Theoretic Indistinguishability via the Chi-Squared Method in ADVANCES IN CRYPTOLOGY – CRYPTO 2017
  • 2017-04-07. How Many Queries are Needed to Distinguish a Truncated Random Permutation from a Random Function? in JOURNAL OF CRYPTOLOGY
  • 2014. Minimizing the Two-Round Even-Mansour Cipher in ADVANCES IN CRYPTOLOGY – CRYPTO 2014
  • 2005. Stronger Security Bounds for Wegman-Carter-Shoup Authenticators in ADVANCES IN CRYPTOLOGY – EUROCRYPT 2005
  • 2018-01-16. A note on the chi-square method: A tool for proving cryptographic security in CRYPTOGRAPHY AND COMMUNICATIONS
  • 2015. On the XOR of Multiple Random Permutations in APPLIED CRYPTOGRAPHY AND NETWORK SECURITY
  • 1996. On Fast and Provably Secure Message Authentication Based on Universal Hashing in ADVANCES IN CRYPTOLOGY — CRYPTO ’96
  • 2008-01-01. A Proof of Security in O(2n) for the Xor of Two Random Permutations in INFORMATION THEORETIC SECURITY
  • 1991. Pseudorandom permutations based on the D.E.S. scheme in EUROCODE '90
  • 2016-07-21. EWCDM: An Efficient, Beyond-Birthday Secure, Nonce-Misuse Resistant MAC in ADVANCES IN CRYPTOLOGY – CRYPTO 2016
  • 2010. Indifferentiability beyond the Birthday Bound for the Xor of Two Public Random Permutations in PROGRESS IN CRYPTOLOGY - INDOCRYPT 2010
  • 1998. Luby-Rackoff backwards: Increasing security by making block ciphers non-invertible in ADVANCES IN CRYPTOLOGY — EUROCRYPT'98
  • 2000-05-12. The Sum of PRPs Is a Secure PRF in ADVANCES IN CRYPTOLOGY — EUROCRYPT 2000
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s10623-018-0470-9

    DOI

    http://dx.doi.org/10.1007/s10623-018-0470-9

    DIMENSIONS

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


    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/01", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Mathematical Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "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/0101", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Pure Mathematics", 
            "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": "University of Versailles, Versailles, France", 
              "id": "http://www.grid.ac/institutes/grid.12832.3a", 
              "name": [
                "University of Versailles, Versailles, France"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Cogliati", 
            "givenName": "Beno\u00eet", 
            "id": "sg:person.010731237165.96", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010731237165.96"
            ], 
            "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"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/3-540-45539-6_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1015039510", 
              "https://doi.org/10.1007/3-540-45539-6_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11426639_10", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036409322", 
              "https://doi.org/10.1007/11426639_10"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-46706-0_15", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1019774938", 
              "https://doi.org/10.1007/978-3-662-46706-0_15"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0054132", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049104193", 
              "https://doi.org/10.1007/bfb0054132"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-28166-7_30", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036699508", 
              "https://doi.org/10.1007/978-3-319-28166-7_30"
            ], 
            "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-85093-9_22", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013401685", 
              "https://doi.org/10.1007/978-3-540-85093-9_22"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-04159-4_21", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1004018040", 
              "https://doi.org/10.1007/978-3-642-04159-4_21"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-17401-8_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1013276202", 
              "https://doi.org/10.1007/978-3-642-17401-8_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-68697-5_24", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038146356", 
              "https://doi.org/10.1007/3-540-68697-5_24"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00145-017-9253-0", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1084517296", 
              "https://doi.org/10.1007/s00145-017-9253-0"
            ], 
            "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/978-3-319-63697-9_19", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091024665", 
              "https://doi.org/10.1007/978-3-319-63697-9_19"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-54303-1_131", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1017922293", 
              "https://doi.org/10.1007/3-540-54303-1_131"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-53018-4_5", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1010776336", 
              "https://doi.org/10.1007/978-3-662-53018-4_5"
            ], 
            "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/s12095-017-0276-z", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1100405885", 
              "https://doi.org/10.1007/s12095-017-0276-z"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-319-63697-9_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1091024663", 
              "https://doi.org/10.1007/978-3-319-63697-9_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-662-47989-6_17", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1047706460", 
              "https://doi.org/10.1007/978-3-662-47989-6_17"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0055742", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1027261590", 
              "https://doi.org/10.1007/bfb0055742"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2018-03-05", 
        "datePublishedReg": "2018-03-05", 
        "description": "We consider the so-called Encrypted Davies\u2013Meyer (EDM) construction, which turns a permutation P on {0,1}n\\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}$$\\{0,1\\}^n$$\\end{document} into a function from {0,1}n\\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}$$\\{0,1\\}^n$$\\end{document} to {0,1}n\\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}$$\\{0,1\\}^n$$\\end{document} defined as P(P(x)\u2295x)\\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}$$P(P(x)\\oplus x)$$\\end{document}. A similar construction using two independent permutations, namely P\u2032(P(x)\u2295x)\\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}$$P'(P(x)\\oplus x)$$\\end{document}, was previously analyzed by Cogliati and Seurin (Advances in cryptology\u2014CRYPTO 2016 (Proceedings, Part I). LNCS, vol 9814, pp. 121\u2013149, 2016) who showed that when P and P\u2032\\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}$$P'$$\\end{document} are secret and random, then any black-box adversary needs at least roughly 22n/3\\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^{2n/3}$$\\end{document} queries to distinguish the construction from a uniformly random function from {0,1}n\\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}$$\\{0,1\\}^n$$\\end{document} to {0,1}n\\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}$$\\{0,1\\}^n$$\\end{document}. In this paper, we focus on the single-permutation variant of the construction. Our main result is that the PRF-security of the single-permutation EDM construction is also (at least) roughly 22n/3\\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^{2n/3}$$\\end{document}, in the sense that any black-box adversary needs at least this number of queries to distinguish the construction from a uniformly random function. This yields the first PRP-to-PRF conversion method which uses a single permutation, does not shrink the original domain nor range of the permutation, and provides security beyond the birthday bound.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s10623-018-0470-9", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136552", 
            "issn": [
              "0925-1022", 
              "1573-7586"
            ], 
            "name": "Designs, Codes and Cryptography", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "12", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "86"
          }
        ], 
        "keywords": [
          "PrP", 
          "function", 
          "main results", 
          "variants", 
          "number", 
          "birthday", 
          "analysis", 
          "results", 
          "method", 
          "range", 
          "domain", 
          "permutation P", 
          "sense", 
          "permutations", 
          "Cogliati", 
          "Seurin", 
          "original domain", 
          "single permutation", 
          "construction", 
          "queries", 
          "paper", 
          "number of queries", 
          "similar construction", 
          "conversion method", 
          "security", 
          "random function", 
          "independent permutations", 
          "adversary", 
          "Davies-Meyer construction", 
          "black-box adversary", 
          "PRF-security"
        ], 
        "name": "Analysis of the single-permutation encrypted Davies\u2013Meyer construction", 
        "pagination": "2703-2723", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1101340318"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s10623-018-0470-9"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s10623-018-0470-9", 
          "https://app.dimensions.ai/details/publication/pub.1101340318"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-11-24T21:02", 
        "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/article/article_786.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s10623-018-0470-9"
      }
    ]
     

    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/s10623-018-0470-9'

    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/s10623-018-0470-9'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s10623-018-0470-9'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s10623-018-0470-9'


     

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

    190 TRIPLES      21 PREDICATES      78 URIs      47 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s10623-018-0470-9 schema:about anzsrc-for:01
    2 anzsrc-for:0101
    3 anzsrc-for:08
    4 anzsrc-for:0802
    5 anzsrc-for:0804
    6 schema:author N1ef019b654a94e3494b1cb596e262b38
    7 schema:citation sg:pub.10.1007/11426639_10
    8 sg:pub.10.1007/11761679_25
    9 sg:pub.10.1007/3-540-45539-6_34
    10 sg:pub.10.1007/3-540-54303-1_131
    11 sg:pub.10.1007/3-540-68697-5_24
    12 sg:pub.10.1007/978-3-319-28166-7_30
    13 sg:pub.10.1007/978-3-319-63697-9_17
    14 sg:pub.10.1007/978-3-319-63697-9_19
    15 sg:pub.10.1007/978-3-540-85093-9_22
    16 sg:pub.10.1007/978-3-642-04159-4_21
    17 sg:pub.10.1007/978-3-642-17401-8_6
    18 sg:pub.10.1007/978-3-642-55220-5_19
    19 sg:pub.10.1007/978-3-662-44371-2_3
    20 sg:pub.10.1007/978-3-662-46706-0_15
    21 sg:pub.10.1007/978-3-662-47989-6_17
    22 sg:pub.10.1007/978-3-662-53018-4_5
    23 sg:pub.10.1007/bfb0054132
    24 sg:pub.10.1007/bfb0055742
    25 sg:pub.10.1007/s00145-017-9253-0
    26 sg:pub.10.1007/s12095-017-0276-z
    27 schema:datePublished 2018-03-05
    28 schema:datePublishedReg 2018-03-05
    29 schema:description We consider the so-called Encrypted Davies–Meyer (EDM) construction, which turns a permutation P on {0,1}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,1\}^n$$\end{document} into a function from {0,1}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,1\}^n$$\end{document} to {0,1}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,1\}^n$$\end{document} defined as P(P(x)⊕x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P(P(x)\oplus x)$$\end{document}. A similar construction using two independent permutations, namely P′(P(x)⊕x)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P'(P(x)\oplus x)$$\end{document}, was previously analyzed by Cogliati and Seurin (Advances in cryptology—CRYPTO 2016 (Proceedings, Part I). LNCS, vol 9814, pp. 121–149, 2016) who showed that when P and P′\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P'$$\end{document} are secret and random, then any black-box adversary needs at least roughly 22n/3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{2n/3}$$\end{document} queries to distinguish the construction from a uniformly random function from {0,1}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,1\}^n$$\end{document} to {0,1}n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\{0,1\}^n$$\end{document}. In this paper, we focus on the single-permutation variant of the construction. Our main result is that the PRF-security of the single-permutation EDM construction is also (at least) roughly 22n/3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^{2n/3}$$\end{document}, in the sense that any black-box adversary needs at least this number of queries to distinguish the construction from a uniformly random function. This yields the first PRP-to-PRF conversion method which uses a single permutation, does not shrink the original domain nor range of the permutation, and provides security beyond the birthday bound.
    30 schema:genre article
    31 schema:isAccessibleForFree false
    32 schema:isPartOf Nb4feeb0e2bd74a4cb103ce4ff443e1a1
    33 Nf8e81ef972fd4f7493dc7095cf796f6b
    34 sg:journal.1136552
    35 schema:keywords Cogliati
    36 Davies-Meyer construction
    37 PRF-security
    38 PrP
    39 Seurin
    40 adversary
    41 analysis
    42 birthday
    43 black-box adversary
    44 construction
    45 conversion method
    46 domain
    47 function
    48 independent permutations
    49 main results
    50 method
    51 number
    52 number of queries
    53 original domain
    54 paper
    55 permutation P
    56 permutations
    57 queries
    58 random function
    59 range
    60 results
    61 security
    62 sense
    63 similar construction
    64 single permutation
    65 variants
    66 schema:name Analysis of the single-permutation encrypted Davies–Meyer construction
    67 schema:pagination 2703-2723
    68 schema:productId N7f1c84a420704e6bb54748a269221d3c
    69 Ne1da244aaaba4514be9d7310489c2ee0
    70 schema:sameAs https://app.dimensions.ai/details/publication/pub.1101340318
    71 https://doi.org/10.1007/s10623-018-0470-9
    72 schema:sdDatePublished 2022-11-24T21:02
    73 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    74 schema:sdPublisher N967e4d92c2664a69a6145b5a2a21713a
    75 schema:url https://doi.org/10.1007/s10623-018-0470-9
    76 sgo:license sg:explorer/license/
    77 sgo:sdDataset articles
    78 rdf:type schema:ScholarlyArticle
    79 N1ef019b654a94e3494b1cb596e262b38 rdf:first sg:person.010731237165.96
    80 rdf:rest Nd79381407d0749588aec5187142bde4f
    81 N7f1c84a420704e6bb54748a269221d3c schema:name dimensions_id
    82 schema:value pub.1101340318
    83 rdf:type schema:PropertyValue
    84 N967e4d92c2664a69a6145b5a2a21713a schema:name Springer Nature - SN SciGraph project
    85 rdf:type schema:Organization
    86 Nb4feeb0e2bd74a4cb103ce4ff443e1a1 schema:issueNumber 12
    87 rdf:type schema:PublicationIssue
    88 Nd79381407d0749588aec5187142bde4f rdf:first sg:person.011724731171.01
    89 rdf:rest rdf:nil
    90 Ne1da244aaaba4514be9d7310489c2ee0 schema:name doi
    91 schema:value 10.1007/s10623-018-0470-9
    92 rdf:type schema:PropertyValue
    93 Nf8e81ef972fd4f7493dc7095cf796f6b schema:volumeNumber 86
    94 rdf:type schema:PublicationVolume
    95 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
    96 schema:name Mathematical Sciences
    97 rdf:type schema:DefinedTerm
    98 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
    99 schema:name Pure Mathematics
    100 rdf:type schema:DefinedTerm
    101 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    102 schema:name Information and Computing Sciences
    103 rdf:type schema:DefinedTerm
    104 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    105 schema:name Computation Theory and Mathematics
    106 rdf:type schema:DefinedTerm
    107 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
    108 schema:name Data Format
    109 rdf:type schema:DefinedTerm
    110 sg:journal.1136552 schema:issn 0925-1022
    111 1573-7586
    112 schema:name Designs, Codes and Cryptography
    113 schema:publisher Springer Nature
    114 rdf:type schema:Periodical
    115 sg:person.010731237165.96 schema:affiliation grid-institutes:grid.12832.3a
    116 schema:familyName Cogliati
    117 schema:givenName Benoît
    118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010731237165.96
    119 rdf:type schema:Person
    120 sg:person.011724731171.01 schema:affiliation grid-institutes:None
    121 schema:familyName Seurin
    122 schema:givenName Yannick
    123 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011724731171.01
    124 rdf:type schema:Person
    125 sg:pub.10.1007/11426639_10 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036409322
    126 https://doi.org/10.1007/11426639_10
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/11761679_25 schema:sameAs https://app.dimensions.ai/details/publication/pub.1031026722
    129 https://doi.org/10.1007/11761679_25
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/3-540-45539-6_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1015039510
    132 https://doi.org/10.1007/3-540-45539-6_34
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/3-540-54303-1_131 schema:sameAs https://app.dimensions.ai/details/publication/pub.1017922293
    135 https://doi.org/10.1007/3-540-54303-1_131
    136 rdf:type schema:CreativeWork
    137 sg:pub.10.1007/3-540-68697-5_24 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038146356
    138 https://doi.org/10.1007/3-540-68697-5_24
    139 rdf:type schema:CreativeWork
    140 sg:pub.10.1007/978-3-319-28166-7_30 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036699508
    141 https://doi.org/10.1007/978-3-319-28166-7_30
    142 rdf:type schema:CreativeWork
    143 sg:pub.10.1007/978-3-319-63697-9_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091024663
    144 https://doi.org/10.1007/978-3-319-63697-9_17
    145 rdf:type schema:CreativeWork
    146 sg:pub.10.1007/978-3-319-63697-9_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1091024665
    147 https://doi.org/10.1007/978-3-319-63697-9_19
    148 rdf:type schema:CreativeWork
    149 sg:pub.10.1007/978-3-540-85093-9_22 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013401685
    150 https://doi.org/10.1007/978-3-540-85093-9_22
    151 rdf:type schema:CreativeWork
    152 sg:pub.10.1007/978-3-642-04159-4_21 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004018040
    153 https://doi.org/10.1007/978-3-642-04159-4_21
    154 rdf:type schema:CreativeWork
    155 sg:pub.10.1007/978-3-642-17401-8_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1013276202
    156 https://doi.org/10.1007/978-3-642-17401-8_6
    157 rdf:type schema:CreativeWork
    158 sg:pub.10.1007/978-3-642-55220-5_19 schema:sameAs https://app.dimensions.ai/details/publication/pub.1020563393
    159 https://doi.org/10.1007/978-3-642-55220-5_19
    160 rdf:type schema:CreativeWork
    161 sg:pub.10.1007/978-3-662-44371-2_3 schema:sameAs https://app.dimensions.ai/details/publication/pub.1008932700
    162 https://doi.org/10.1007/978-3-662-44371-2_3
    163 rdf:type schema:CreativeWork
    164 sg:pub.10.1007/978-3-662-46706-0_15 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019774938
    165 https://doi.org/10.1007/978-3-662-46706-0_15
    166 rdf:type schema:CreativeWork
    167 sg:pub.10.1007/978-3-662-47989-6_17 schema:sameAs https://app.dimensions.ai/details/publication/pub.1047706460
    168 https://doi.org/10.1007/978-3-662-47989-6_17
    169 rdf:type schema:CreativeWork
    170 sg:pub.10.1007/978-3-662-53018-4_5 schema:sameAs https://app.dimensions.ai/details/publication/pub.1010776336
    171 https://doi.org/10.1007/978-3-662-53018-4_5
    172 rdf:type schema:CreativeWork
    173 sg:pub.10.1007/bfb0054132 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049104193
    174 https://doi.org/10.1007/bfb0054132
    175 rdf:type schema:CreativeWork
    176 sg:pub.10.1007/bfb0055742 schema:sameAs https://app.dimensions.ai/details/publication/pub.1027261590
    177 https://doi.org/10.1007/bfb0055742
    178 rdf:type schema:CreativeWork
    179 sg:pub.10.1007/s00145-017-9253-0 schema:sameAs https://app.dimensions.ai/details/publication/pub.1084517296
    180 https://doi.org/10.1007/s00145-017-9253-0
    181 rdf:type schema:CreativeWork
    182 sg:pub.10.1007/s12095-017-0276-z schema:sameAs https://app.dimensions.ai/details/publication/pub.1100405885
    183 https://doi.org/10.1007/s12095-017-0276-z
    184 rdf:type schema:CreativeWork
    185 grid-institutes:None schema:alternateName ANSSI, Paris, France
    186 schema:name ANSSI, Paris, France
    187 rdf:type schema:Organization
    188 grid-institutes:grid.12832.3a schema:alternateName University of Versailles, Versailles, France
    189 schema:name University of Versailles, Versailles, France
    190 rdf:type schema:Organization
     




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


    ...