Improved upper bounds for parent-identifying set systems and separable codes
- PDF / 342,264 Bytes
- 14 Pages / 439.37 x 666.142 pts Page_size
- 71 Downloads / 130 Views
Improved upper bounds for parent-identifying set systems and separable codes Xin Wang1 Received: 25 March 2020 / Revised: 26 September 2020 / Accepted: 30 September 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Parent-identifying set systems and separable codes are useful combinatorial structures which were introduced, respectively, for traitor tracing in broadcast encryption and collusionresistant fingerprints for copyright protection. Determining the maximum size of such structures is the main research objective. New upper bounds are presented in this paper. Specifically, for parent-identifying set systems, we determine the order of magnitude of 2 I2 (4, v) and prove an exact bound when w ≤ t4 + t. For q-ary separable codes, we give a new upper bound by estimating the distance distribution of such codes, improving the existing upper bound when q is relatively small. Keywords Parent-identifying set systems · Separable codes · B2 codes · Distance distribution Mathematics Subject Classification 94A60 · 94B25
1 Introduction Traitor tracing [5,6] allows a content distributor to trace the source of a pirate decoder. Collusion-resistant fingerprints [2,4] are used for copyright protection. Several combinatorial structures have been introduced to those ends [2,4–6,8]. In this paper, we focus on two kinds of such combinatorial structures, namely parent-identifying set systems [8] and non-binary separable codes [4]. We now briefly introduce the definitions and some known results about these two structures.
Communicated by C. Padro. Research supported by National Natural Science Foundation of China under Grant 11801392 and the Natural Science Foundation of Jiangsu Province under Grant BK20180833.
B 1
Xin Wang [email protected] Department of Mathematics, Soochow University, Suzhou 215006, China
123
X. Wang
1.1 Parent-identifying set systems Several users of a content distribution service can collude and combine their keys to produce a pirate decoder. A number of tools have been proposed to trace at least one of the traitors from the pirate decoder, such as parent-identifying set systems [8]. Definition 1.1 A t-parent-identifying set system, denoted as t-IPPS(w, v), is a pair (X , B) such that |X | = v, B ⊂ X w with the property that for any w-subset T ⊂ X , either Pt (T ) is empty, or P = ∅, P ∈Pt (T )
where
Pt (T ) := P ⊂ B : |P | ≤ t, T ⊂ B . B∈P
The number of blocks B ∈ B is called the size of this t-IPPS(w, v). Denote It (w, v) as the maximum size of a t-IPPS(w, v). In the literature, the best upper bounds for It (w, v) were introduced in [10]. Theorem 1.2 [10] Let v ≥ w ≥ 2, t ≥ 2 be integers. Then v . It (w, v) ≤ w
t 2 /4+t General lower bounds for It (w, v) were established in [12] via the probabilistic method. Theorem 1.3 [12] Let w and t be positive integers such that t ≥ 2. Then there exists a constant c, depending only on w and t, with the following property. For any sufficiently large w
integer v, there exists a t-IPPS(w, v) with size at l
Data Loading...
