Combinatorial Bounds and Design of Broadcast Authentication

Hiroshi FUJII  Wattanawong KACHEN  Kaoru KUROSAWA  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E79-A   No.4   pp.502-506
Publication Date: 1996/04/25
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
cryptology,  authentication,  combinatorial design,  

Full Text: PDF(403.7KB)>>
Buy this Article

This paper presents a combinatiorial characterization of broadcast authentication in which a transmitter broadcasts v messages e1(s), ・・・, ev(s) to authenticate a source state s to all n receivers so that any k receivers cannot cheat any other receivers, where ei 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 - 1)/l(l - 1) for k = l - 1 and n /+ for k < l - 1. Further, a scheme for k = 1 - 1 which meets the upper bound is presented by using a BIBD and a scheme for k < l - 1 such than n = / is presented by using a Steiner system. Some other efficient schemes are also presented.