Coding constructions for blacklisting problems without computational assumptions

摘要

We consider the broadcast exclusion problem: how to transmit a message over a broadcast channel shared by N chemical bounds 2~n users so that all but some specified coalition of k excluded users can understand the contents of the message. Using error-correcting codes, and avoiding any computational assumptions in our constructions, we construct natural schemes that completely avoid any dependence on n in the transmission overhead.