Fast Algorithms for the Free Riders Problem in Broadcast Encryption View Full Text


Ontology type: schema:Chapter      Open Access: True


Chapter Info

DATE

2006

AUTHORS

Zulfikar Ramzan , David P. Woodruff

ABSTRACT

We provide algorithms to solve the free riders problem in broadcast encryption. In this problem, the broadcast server is allowed to choose some small subset F of the revoked set R of users to allow to decrypt the broadcast, despite having been revoked. This may allow the server to significantly reduce network traffic while only allowing a small set of non-privileged users to decrypt the broadcast.Although there are worst-case instances of broadcast encryption schemes where the free riders problem is difficult to solve (or even approximate), we show that for many specific broadcast encryption schemes, there are efficient algorithms. In particular, for the complete subtree method [25] and some other schemes in the subset-cover framework, we show how to find the optimal assignment of free riders in O(|R||F|) time, which is independent of the total number of users. We also define an approximate version of this problem, and study specific distributions of R for which this relaxation yields even faster algorithms.Along the way we develop the first approximation algorithms for the following problem: given two integer sequences a1 ≥a2 ≥⋯≥an and b1 ≥b2 ≥⋯≥bn, output for all i, an integer j′ for which aj′ + b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$_{i--{\it j}\prime}$\end{document} ≤(1+ε) min j (aj + b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$_{i--{\it j}}$\end{document}). We show that if the differences ai – ai + 1, bi–bi + 1 are bounded, then there is an O(n4/3/ε2/3)-time algorithm for this problem, improving upon the O(n2) time of the naive algorithm. More... »

PAGES

308-325

Book

TITLE

Advances in Cryptology - CRYPTO 2006

ISBN

978-3-540-37432-9
978-3-540-37433-6

Author Affiliations

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/11818175_18

DOI

http://dx.doi.org/10.1007/11818175_18

DIMENSIONS

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


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": "Symantec, Inc.", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "Symantec, Inc."
          ], 
          "type": "Organization"
        }, 
        "familyName": "Ramzan", 
        "givenName": "Zulfikar", 
        "id": "sg:person.012452306554.31", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012452306554.31"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Tsinghua University", 
          "id": "http://www.grid.ac/institutes/grid.12527.33", 
          "name": [
            "MIT", 
            "Tsinghua University"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Woodruff", 
        "givenName": "David P.", 
        "id": "sg:person.012727410605.86", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86"
        ], 
        "type": "Person"
      }
    ], 
    "datePublished": "2006", 
    "datePublishedReg": "2006-01-01", 
    "description": "We provide algorithms to solve the free riders problem in broadcast encryption. In this problem, the broadcast server is allowed to choose some small subset F of the revoked set R of users to allow to decrypt the broadcast, despite having been revoked. This may allow the server to significantly reduce network traffic while only allowing a small set of non-privileged users to decrypt the broadcast.Although there are worst-case instances of broadcast encryption schemes where the free riders problem is difficult to solve (or even approximate), we show that for many specific broadcast encryption schemes, there are efficient algorithms. In particular, for the complete subtree method [25] and some other schemes in the subset-cover framework, we show how to find the optimal assignment of free riders in O(|R||F|) time, which is independent of the total number of users. We also define an approximate version of this problem, and study specific distributions of R for which this relaxation yields even faster algorithms.Along the way we develop the first approximation algorithms for the following problem: given two integer sequences a1 \u2265a2 \u2265\u22ef\u2265an and b1 \u2265b2 \u2265\u22ef\u2265bn, output for all i, an integer j\u2032 for which aj\u2032 + b\\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}$_{i--{\\it j}\\prime}$\\end{document} \u2264(1+\u03b5) min j (aj + b\\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}$_{i--{\\it j}}$\\end{document}). We show that if the differences ai \u2013 ai\u2009+\u20091, bi\u2013bi\u2009+\u20091 are bounded, then there is an O(n4/3/\u03b52/3)-time algorithm for this problem, improving upon the O(n2) time of the naive algorithm.", 
    "editor": [
      {
        "familyName": "Dwork", 
        "givenName": "Cynthia", 
        "type": "Person"
      }
    ], 
    "genre": "chapter", 
    "id": "sg:pub.10.1007/11818175_18", 
    "isAccessibleForFree": true, 
    "isPartOf": {
      "isbn": [
        "978-3-540-37432-9", 
        "978-3-540-37433-6"
      ], 
      "name": "Advances in Cryptology - CRYPTO 2006", 
      "type": "Book"
    }, 
    "keywords": [
      "broadcast encryption scheme", 
      "broadcast encryption", 
      "encryption scheme", 
      "fast algorithm", 
      "non-privileged users", 
      "subset cover framework", 
      "complete subtree method", 
      "worst-case instances", 
      "first approximation algorithm", 
      "broadcast server", 
      "network traffic", 
      "naive algorithm", 
      "efficient algorithm", 
      "approximation algorithm", 
      "optimal assignment", 
      "time algorithm", 
      "users", 
      "algorithm", 
      "encryption", 
      "decrypt", 
      "server", 
      "small set", 
      "approximate version", 
      "broadcast", 
      "scheme", 
      "free riders", 
      "traffic", 
      "integer j", 
      "rider problem", 
      "framework", 
      "set", 
      "instances", 
      "free-rider problem", 
      "version", 
      "subset F", 
      "assignment", 
      "time", 
      "output", 
      "way", 
      "method", 
      "problem", 
      "specific distribution", 
      "sequence a1", 
      "riders", 
      "number", 
      "total number", 
      "relaxation", 
      "distribution", 
      "differences", 
      "A1", 
      "B1"
    ], 
    "name": "Fast Algorithms for the Free Riders Problem in Broadcast Encryption", 
    "pagination": "308-325", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1050473338"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/11818175_18"
        ]
      }
    ], 
    "publisher": {
      "name": "Springer Nature", 
      "type": "Organisation"
    }, 
    "sameAs": [
      "https://doi.org/10.1007/11818175_18", 
      "https://app.dimensions.ai/details/publication/pub.1050473338"
    ], 
    "sdDataset": "chapters", 
    "sdDatePublished": "2022-11-24T21:14", 
    "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
    "sdPublisher": {
      "name": "Springer Nature - SN SciGraph project", 
      "type": "Organization"
    }, 
    "sdSource": "s3://com-springernature-scigraph/baseset/20221124/entities/gbq_results/chapter/chapter_263.jsonl", 
    "type": "Chapter", 
    "url": "https://doi.org/10.1007/11818175_18"
  }
]
 

Download the RDF metadata as:  json-ld nt turtle xml License info

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/11818175_18'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/11818175_18'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/11818175_18'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/11818175_18'


 

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

121 TRIPLES      22 PREDICATES      76 URIs      69 LITERALS      7 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/11818175_18 schema:about anzsrc-for:08
2 anzsrc-for:0804
3 schema:author Nd9109c87bd9848aca2ea6ff6e6ee61e2
4 schema:datePublished 2006
5 schema:datePublishedReg 2006-01-01
6 schema:description We provide algorithms to solve the free riders problem in broadcast encryption. In this problem, the broadcast server is allowed to choose some small subset F of the revoked set R of users to allow to decrypt the broadcast, despite having been revoked. This may allow the server to significantly reduce network traffic while only allowing a small set of non-privileged users to decrypt the broadcast.Although there are worst-case instances of broadcast encryption schemes where the free riders problem is difficult to solve (or even approximate), we show that for many specific broadcast encryption schemes, there are efficient algorithms. In particular, for the complete subtree method [25] and some other schemes in the subset-cover framework, we show how to find the optimal assignment of free riders in O(|R||F|) time, which is independent of the total number of users. We also define an approximate version of this problem, and study specific distributions of R for which this relaxation yields even faster algorithms.Along the way we develop the first approximation algorithms for the following problem: given two integer sequences a1 ≥a2 ≥⋯≥an and b1 ≥b2 ≥⋯≥bn, output for all i, an integer j′ for which aj′ + b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$_{i--{\it j}\prime}$\end{document} ≤(1+ε) min j (aj + b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$_{i--{\it j}}$\end{document}). We show that if the differences ai – ai + 1, bi–bi + 1 are bounded, then there is an O(n4/3/ε2/3)-time algorithm for this problem, improving upon the O(n2) time of the naive algorithm.
7 schema:editor N2ee9d2053c464b36b6d6f096fa851cdd
8 schema:genre chapter
9 schema:isAccessibleForFree true
10 schema:isPartOf Nf2fecdc3f476490e8980636e04b98a2a
11 schema:keywords A1
12 B1
13 algorithm
14 approximate version
15 approximation algorithm
16 assignment
17 broadcast
18 broadcast encryption
19 broadcast encryption scheme
20 broadcast server
21 complete subtree method
22 decrypt
23 differences
24 distribution
25 efficient algorithm
26 encryption
27 encryption scheme
28 fast algorithm
29 first approximation algorithm
30 framework
31 free riders
32 free-rider problem
33 instances
34 integer j
35 method
36 naive algorithm
37 network traffic
38 non-privileged users
39 number
40 optimal assignment
41 output
42 problem
43 relaxation
44 rider problem
45 riders
46 scheme
47 sequence a1
48 server
49 set
50 small set
51 specific distribution
52 subset F
53 subset cover framework
54 time
55 time algorithm
56 total number
57 traffic
58 users
59 version
60 way
61 worst-case instances
62 schema:name Fast Algorithms for the Free Riders Problem in Broadcast Encryption
63 schema:pagination 308-325
64 schema:productId N37f3207cd1ed46e590c3671ca122bc2c
65 Nc39373bdf21e47e6972f70792150827e
66 schema:publisher N113c9568e76a437e9f619ef5a8e95e7f
67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1050473338
68 https://doi.org/10.1007/11818175_18
69 schema:sdDatePublished 2022-11-24T21:14
70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
71 schema:sdPublisher N7ca789e6eaeb4dfca590075e2ef92c2c
72 schema:url https://doi.org/10.1007/11818175_18
73 sgo:license sg:explorer/license/
74 sgo:sdDataset chapters
75 rdf:type schema:Chapter
76 N113c9568e76a437e9f619ef5a8e95e7f schema:name Springer Nature
77 rdf:type schema:Organisation
78 N2ee9d2053c464b36b6d6f096fa851cdd rdf:first N414e1ebfd73d495bb32a6dc27b90e8b6
79 rdf:rest rdf:nil
80 N37f3207cd1ed46e590c3671ca122bc2c schema:name dimensions_id
81 schema:value pub.1050473338
82 rdf:type schema:PropertyValue
83 N3e06b2e494244f01b47c8c366477a8fc rdf:first sg:person.012727410605.86
84 rdf:rest rdf:nil
85 N414e1ebfd73d495bb32a6dc27b90e8b6 schema:familyName Dwork
86 schema:givenName Cynthia
87 rdf:type schema:Person
88 N7ca789e6eaeb4dfca590075e2ef92c2c schema:name Springer Nature - SN SciGraph project
89 rdf:type schema:Organization
90 Nc39373bdf21e47e6972f70792150827e schema:name doi
91 schema:value 10.1007/11818175_18
92 rdf:type schema:PropertyValue
93 Nd9109c87bd9848aca2ea6ff6e6ee61e2 rdf:first sg:person.012452306554.31
94 rdf:rest N3e06b2e494244f01b47c8c366477a8fc
95 Nf2fecdc3f476490e8980636e04b98a2a schema:isbn 978-3-540-37432-9
96 978-3-540-37433-6
97 schema:name Advances in Cryptology - CRYPTO 2006
98 rdf:type schema:Book
99 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
100 schema:name Information and Computing Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0804 schema:inDefinedTermSet anzsrc-for:
103 schema:name Data Format
104 rdf:type schema:DefinedTerm
105 sg:person.012452306554.31 schema:affiliation grid-institutes:None
106 schema:familyName Ramzan
107 schema:givenName Zulfikar
108 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012452306554.31
109 rdf:type schema:Person
110 sg:person.012727410605.86 schema:affiliation grid-institutes:grid.12527.33
111 schema:familyName Woodruff
112 schema:givenName David P.
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012727410605.86
114 rdf:type schema:Person
115 grid-institutes:None schema:alternateName Symantec, Inc.
116 schema:name Symantec, Inc.
117 rdf:type schema:Organization
118 grid-institutes:grid.12527.33 schema:alternateName Tsinghua University
119 schema:name MIT
120 Tsinghua University
121 rdf:type schema:Organization
 




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


...