On the XOR of Multiple Random Permutations View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2015

AUTHORS

Bart Mennink , Bart Preneel

ABSTRACT

A straightforward way of constructing an n-bit pseudorandom function is to XOR two or more pseudorandom permutations: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_1\oplus \ldots \oplus p_k$$\end{document}. This XOR construction has gained broad attention over the last two decades. In this work, we revisit the security of this well-established construction. We consider the case where the underlying permutations are considered secret, as well as the case where these permutations are publicly available to the adversary. In the secret permutation setting, we present a simple reduction showing that the XOR construction achieves optimal \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^n$$\end{document} security for all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 2$$\end{document}, therewith improving a recent result of Cogliati et al. (FSE 2014). Regarding the public permutation setting, Mandal et al. (INDOCRYPT 2010) proved \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} security for the case \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=2$$\end{document}, but we point out the existence of a non-trivial flaw in the proof. We re-establish and generalize the claimed security bound for general \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 2$$\end{document} using a different proof approach. More... »

PAGES

619-634

Book

TITLE

Applied Cryptography and Network Security

ISBN

978-3-319-28165-0
978-3-319-28166-7

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/978-3-319-28166-7_30

DOI

http://dx.doi.org/10.1007/978-3-319-28166-7_30

DIMENSIONS

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


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": "Department of Electrical Engineering, ESAT/COSIC, KU Leuven, and iMinds, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "Department of Electrical Engineering, ESAT/COSIC, KU Leuven, and iMinds, Leuven, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Mennink", 
        "givenName": "Bart", 
        "id": "sg:person.012130641461.76", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012130641461.76"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Electrical Engineering, ESAT/COSIC, KU Leuven, and iMinds, Leuven, Belgium", 
          "id": "http://www.grid.ac/institutes/grid.5596.f", 
          "name": [
            "Department of Electrical Engineering, ESAT/COSIC, KU Leuven, and iMinds, Leuven, Belgium"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Preneel", 
        "givenName": "Bart", 
        "id": "sg:person.011115044357.39", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2015", 
    "datePublishedReg": "2015-01-01", 
    "description": "A straightforward way of constructing an n-bit pseudorandom function is to XOR two or more pseudorandom permutations: \\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_1\\oplus \\ldots \\oplus p_k$$\\end{document}. This XOR construction has gained broad attention over the last two decades. In this work, we revisit the security of this well-established construction. We consider the case where the underlying permutations are considered secret, as well as the case where these permutations are publicly available to the adversary. In the secret permutation setting, we present a simple reduction showing that the XOR construction achieves optimal \\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^n$$\\end{document} security for all \\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}$$k\\ge 2$$\\end{document}, therewith improving a recent result of Cogliati et al.\u00a0(FSE 2014). Regarding the public permutation setting, Mandal et al.\u00a0(INDOCRYPT 2010) proved \\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} security for the case \\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}$$k=2$$\\end{document}, but we point out the existence of a non-trivial flaw in the proof. We re-establish and generalize the claimed security bound for general \\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}$$k\\ge 2$$\\end{document} using a different proof approach.", 
    "editor": [
      {
        "familyName": "Malkin", 
        "givenName": "Tal", 
        "type": "Person"
      }, 
      {
        "familyName": "Kolesnikov", 
        "givenName": "Vladimir", 
        "type": "Person"
      }, 
      {
        "familyName": "Lewko", 
        "givenName": "Allison Bishop", 
        "type": "Person"
      }, 
      {
        "familyName": "Polychronakis", 
        "givenName": "Michalis", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/978-3-319-28166-7_30", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-319-28165-0", 
        "978-3-319-28166-7"
      ], 
      "name": "Applied Cryptography and Network Security", 
      "type": "Book"
    }, 
    "keywords": [
      "construction", 
      "broad attention", 
      "way", 
      "attention", 
      "work", 
      "setting", 
      "decades", 
      "straightforward way", 
      "two", 
      "existence", 
      "therewith", 
      "permutations", 
      "flaws", 
      "approach", 
      "security", 
      "cases", 
      "adversary", 
      "et al", 
      "al", 
      "proof", 
      "results", 
      "function", 
      "simple reduction", 
      "random permutation", 
      "recent results", 
      "reduction", 
      "XOR", 
      "pseudorandom functions", 
      "Mandal et al", 
      "proof approach", 
      "pseudorandom permutation", 
      "underlying permutation"
    ], 
    "name": "On the XOR of Multiple Random Permutations", 
    "pagination": "619-634", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1036699508"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/978-3-319-28166-7_30"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/978-3-319-28166-7_30", 
      "https://app.dimensions.ai/details/publication/pub.1036699508"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-10-01T07:00", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221001/entities/gbq_results/chapter/chapter_44.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/978-3-319-28166-7_30"
  }
]
 

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-319-28166-7_30'

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-319-28166-7_30'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/978-3-319-28166-7_30'

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-319-28166-7_30'


 

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

113 TRIPLES      22 PREDICATES      57 URIs      50 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/978-3-319-28166-7_30 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nc33037f5d12c417eb95d3f530c715650
4 schema:datePublished 2015
5 schema:datePublishedReg 2015-01-01
6 schema:description A straightforward way of constructing an n-bit pseudorandom function is to XOR two or more pseudorandom permutations: \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$p_1\oplus \ldots \oplus p_k$$\end{document}. This XOR construction has gained broad attention over the last two decades. In this work, we revisit the security of this well-established construction. We consider the case where the underlying permutations are considered secret, as well as the case where these permutations are publicly available to the adversary. In the secret permutation setting, we present a simple reduction showing that the XOR construction achieves optimal \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$2^n$$\end{document} security for all \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 2$$\end{document}, therewith improving a recent result of Cogliati et al. (FSE 2014). Regarding the public permutation setting, Mandal et al. (INDOCRYPT 2010) proved \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} security for the case \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k=2$$\end{document}, but we point out the existence of a non-trivial flaw in the proof. We re-establish and generalize the claimed security bound for general \documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$k\ge 2$$\end{document} using a different proof approach.
7 schema:editor N6a0a989154444abe86540bbe356f2a05
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf N596b5aa7b7fc449d92d8df25323e390f
11 schema:keywords Mandal et al
12 XOR
13 adversary
14 al
15 approach
16 attention
17 broad attention
18 cases
19 construction
20 decades
21 et al
22 existence
23 flaws
24 function
25 permutations
26 proof
27 proof approach
28 pseudorandom functions
29 pseudorandom permutation
30 random permutation
31 recent results
32 reduction
33 results
34 security
35 setting
36 simple reduction
37 straightforward way
38 therewith
39 two
40 underlying permutation
41 way
42 work
43 schema:name On the XOR of Multiple Random Permutations
44 schema:pagination 619-634
45 schema:productId N7a9386dfbbf54e52be01a96d65bb7551
46 N9f92e8831651462aacd8400664a5b7fd
47 schema:publisher N24d591c8f8c242c1bd50fb8364bab157
48 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036699508
49 https://doi.org/10.1007/978-3-319-28166-7_30
50 schema:sdDatePublished 2022-10-01T07:00
51 schema:sdLicense https://scigraph.springernature.com/explorer/license/
52 schema:sdPublisher N77df35304a1f4ae2824fa735556004a5
53 schema:url https://doi.org/10.1007/978-3-319-28166-7_30
54 sgo:license sg:explorer/license/
55 sgo:sdDataset chapters
56 rdf:type schema:Chapter
57 N00288862f5c04ae7ab8a3beff2ff7a49 rdf:first Ne75a0366c0144963ad4385400c051554
58 rdf:rest rdf:nil
59 N24d591c8f8c242c1bd50fb8364bab157 schema:name Springer Nature
60 rdf:type schema:Organisation
61 N596b5aa7b7fc449d92d8df25323e390f schema:isbn 978-3-319-28165-0
62 978-3-319-28166-7
63 schema:name Applied Cryptography and Network Security
64 rdf:type schema:Book
65 N5ff4e258a7b8449eb7917d188616e0fd schema:familyName Kolesnikov
66 schema:givenName Vladimir
67 rdf:type schema:Person
68 N6540a664e3144621847c608e969ad11b rdf:first N8ea803da2a4c469dbf8dc547559fa344
69 rdf:rest N00288862f5c04ae7ab8a3beff2ff7a49
70 N68f06c4010634101b537046268bc8175 schema:familyName Malkin
71 schema:givenName Tal
72 rdf:type schema:Person
73 N6a0a989154444abe86540bbe356f2a05 rdf:first N68f06c4010634101b537046268bc8175
74 rdf:rest N8f281af7f91044ccaa6a9415ad241b68
75 N77df35304a1f4ae2824fa735556004a5 schema:name Springer Nature - SN SciGraph project
76 rdf:type schema:Organization
77 N7a9386dfbbf54e52be01a96d65bb7551 schema:name doi
78 schema:value 10.1007/978-3-319-28166-7_30
79 rdf:type schema:PropertyValue
80 N8ea803da2a4c469dbf8dc547559fa344 schema:familyName Lewko
81 schema:givenName Allison Bishop
82 rdf:type schema:Person
83 N8f281af7f91044ccaa6a9415ad241b68 rdf:first N5ff4e258a7b8449eb7917d188616e0fd
84 rdf:rest N6540a664e3144621847c608e969ad11b
85 N93a0afc9eebf4f76a4800cd1f3cc4caf rdf:first sg:person.011115044357.39
86 rdf:rest rdf:nil
87 N9f92e8831651462aacd8400664a5b7fd schema:name dimensions_id
88 schema:value pub.1036699508
89 rdf:type schema:PropertyValue
90 Nc33037f5d12c417eb95d3f530c715650 rdf:first sg:person.012130641461.76
91 rdf:rest N93a0afc9eebf4f76a4800cd1f3cc4caf
92 Ne75a0366c0144963ad4385400c051554 schema:familyName Polychronakis
93 schema:givenName Michalis
94 rdf:type schema:Person
95 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
96 schema:name Information and Computing Sciences
97 rdf:type schema:DefinedTerm
98 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
99 schema:name Data Format
100 rdf:type schema:DefinedTerm
101 sg:person.011115044357.39 schema:affiliation grid-institutes:grid.5596.f
102 schema:familyName Preneel
103 schema:givenName Bart
104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011115044357.39
105 rdf:type schema:Person
106 sg:person.012130641461.76 schema:affiliation grid-institutes:grid.5596.f
107 schema:familyName Mennink
108 schema:givenName Bart
109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012130641461.76
110 rdf:type schema:Person
111 grid-institutes:grid.5596.f schema:alternateName Department of Electrical Engineering, ESAT/COSIC, KU Leuven, and iMinds, Leuven, Belgium
112 schema:name Department of Electrical Engineering, ESAT/COSIC, KU Leuven, and iMinds, Leuven, Belgium
113 rdf:type schema:Organization
 




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


...