TY - GEN
T1 - A combinatorial approach to anonymous membership broadcast
AU - Wang, Huaxiong
AU - Pieprzyk, Josef
PY - 2002
Y1 - 2002
N2 - A set system (X,F) with X = {x1,..., xm) and F = {B1,..., Bn}, where Bi ⊆ X, is called an (n,m) cover-free set system (or CF set system) if for any 1 ≤ i, j, k ≤ n and j ≠ k, |Bi| ≥ 2 |Bj ∩ Bk| + 1. In this paper, we show that CF set systems can be used to construct anonymous membership broadcast schemes (or AMB schemes), allowing a center to broadcast a secret identity among a set of users in a such way that the users can verify whether or not the broadcast message contains their valid identity. Our goal is to construct (n,m) CF set systems in which for given m the value n is as large as possible. We give two constructions for CF set systems, the first one from error-correcting codes and the other from combinatorial designs. We link CF set systems to the concept of cover-free family studied by Erdös et al in early 80’s to derive bounds on parameters of CF set systems. We also discuss some possible extensions of the current work, motivated by different application.
AB - A set system (X,F) with X = {x1,..., xm) and F = {B1,..., Bn}, where Bi ⊆ X, is called an (n,m) cover-free set system (or CF set system) if for any 1 ≤ i, j, k ≤ n and j ≠ k, |Bi| ≥ 2 |Bj ∩ Bk| + 1. In this paper, we show that CF set systems can be used to construct anonymous membership broadcast schemes (or AMB schemes), allowing a center to broadcast a secret identity among a set of users in a such way that the users can verify whether or not the broadcast message contains their valid identity. Our goal is to construct (n,m) CF set systems in which for given m the value n is as large as possible. We give two constructions for CF set systems, the first one from error-correcting codes and the other from combinatorial designs. We link CF set systems to the concept of cover-free family studied by Erdös et al in early 80’s to derive bounds on parameters of CF set systems. We also discuss some possible extensions of the current work, motivated by different application.
UR - http://www.scopus.com/inward/record.url?scp=23044533746&partnerID=8YFLogxK
U2 - 10.1007/3-540-45655-4_19
DO - 10.1007/3-540-45655-4_19
M3 - Conference proceeding contribution
AN - SCOPUS:23044533746
SN - 354043996X
SN - 9783540439967
VL - 2387
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 162
EP - 170
BT - Computing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings
A2 - Ibarra, Oscar H.
A2 - Zhang, Louxin
PB - Springer, Springer Nature
CY - New York
T2 - 8th Annual International Conference on Computing and Combinatorics, COCOON 2002
Y2 - 15 August 2002 through 17 August 2002
ER -