A combinatorial approach to anonymous membership broadcast

Huaxiong Wang, Josef Pieprzyk

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

4 Citations (Scopus)


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.

Original languageEnglish
Title of host publicationComputing and Combinatorics - 8th Annual International Conference, COCOON 2002, Proceedings
EditorsOscar H. Ibarra, Louxin Zhang
Place of PublicationNew York
PublisherSpringer, Springer Nature
Number of pages9
ISBN (Electronic)9783540456551
ISBN (Print)354043996X, 9783540439967
Publication statusPublished - 2002
Event8th Annual International Conference on Computing and Combinatorics, COCOON 2002 - Singapore, Singapore
Duration: 15 Aug 200217 Aug 2002

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


Other8th Annual International Conference on Computing and Combinatorics, COCOON 2002


Dive into the research topics of 'A combinatorial approach to anonymous membership broadcast'. Together they form a unique fingerprint.

Cite this