Combinatorial Bounds and Design of Broadcast Authentication
Hiroshi Fujii, Wattanawong Kachen, Kaoru Kurosawa · 1996
This paper presents a combinatorial characterization of broadcast authentication in which a transmitter broadcasts v messages e 1 (s); \\Delta \\Delta \\Delta ; e v (s) to authenticate a source state s to all n receivers so that any k receivers cannot cheat any other receivers, where e i is a key. Suppose that each receiver has l keys. First, we prove that k ! l if v ! n. Then we show an upper bound of n such that n v(v \\Gamma 1)=l(l \\Gamma 1) for k = l \\Gamma 1 and n ` v dl=ke ' = ` l dl=ke ' + ` v dl=ke ' for k ! l \\Gamma 1. Further, a scheme for k = l \\Gamma 1 which meets the upper bound is presented by using a BIBD and a scheme for k ! l \\Gamma 1 such that n = ` v dl=ke ' = ` l dl=ke ' is presented by using a Steiner system. Some other efficient schemes are also presented.