On 2-parent-identifying set systems of block size 4
- PDF / 310,852 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 13 Downloads / 154 Views
On 2-parent-identifying set systems of block size 4 Yujie Gu1 · Shohei Satake2 Received: 10 August 2019 / Revised: 15 February 2020 / Accepted: 20 April 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract Parent-identifying set system is a kind of combinatorial structures with applications to broadcast encryption. In this paper we investigate the maximum number of blocks I2 (n, 4) in a 2-parent-identifying set system with ground set size n and block size 4. The previous bestknown lower bound states that I2 (n, 4) = Ω(n 4/3+o(1) ). We improve this lower bound by showing that I2 (n, 4) = Ω(n 3/2−o(1) ) using techniques in additive number theory. Keywords Parent-identifying set system · Broadcast encryption · Construction Mathematics Subject Classification 94B25 · 05D05
1 Introduction Traitor tracing was introduced for broadcast encryption in order to protect the copyrighted digital contents [3,4]. Over the recent decades, several kinds of combinatorial structures which could be applied for the key-distribution schemes against the piracy were proposed and extensively investigated, see [2,4,5,11,16] for example. In this paper our discussion is based on the combinatorial model introduced in [16], which could be briefly described in the following. A dealer, who possesses the copyright of the data, has a set X of n base decryption keys. The dealer would assign each authorized user, who purchased the copyright of data, k based keys (i.e. a k-subset of X ), which, based on a threshold secret sharing scheme, could be used to decrypt the encrypted contents [16]. In this setting, we could assume an (n, k) set system (X , B) where X is the ground set of n base keys, and B is a family of k-subsets of X representing all the authorized users. In a set system (X , B), each element of X is called a point, and each element of B is referred to as a block. A t-collusion means that t dishonest
Communicated by M. Paterson.
B
Shohei Satake [email protected] Yujie Gu [email protected]
1
Department of Electrical Engineering–Systems, Tel Aviv University, Tel Aviv 6997801, Israel
2
Graduate School of System Informatics, Kobe University, Kobe 657-8501, Japan
123
Y. Gu, S. Satake
users (traitors) B1 , . . . , Bt ∈ B work together to generate a k-subset (pirate) T ⊆ ∪1≤i≤t Bi and illegally redistribute T to the unauthorized users. To hinder the illegal redistribution of the decryption key, once such pirate T is confiscated, the dealer would like to trace back to at least one or more traitors in the coalition. This requires that the set system (X , B) should have some desired properties. Parent-identifying set system, which was proposed in [5] as a variant of codes with the identifiable parent property (i.e. parent-identifying codes) in [11], could provide a kind of traceability as follows. Definition 1 A t-parent-identifying set system, denoted as t-IPPS(n, k), is a pair (X , B) such that |X | = n, B ⊆ Xk = {F ⊆ X : |F| = k}, with the property that for any k-subset T ⊆ X , either Pt (T
Data Loading...
