New combinatorial designs and their applications to authentication codes and secret sharing schemes. (Q1428540)

New types of combinatorial designs are introduced in the paper, namely external difference families (EDF), external balanced incomplete blocks designs (EBIBDs), and splitting BIBD, and their applications in cryptography are discussed. First, EDF as an extension of difference sets and difference families and EBIBD as a generalization of a BIBD are defined. Also it is proved that an EDF is equivalent to an EBIBD with a particular automorphism. Then it is shown that EDF can be used to obtain splitting authentication codes (A-codes) with perfect secrecy which meet both the known lower bound on cheating probabilities as well as the lower bound on the size of keys. After that an application to secret sharing schemes is discussed. First, a new lower bound on the size of shares in the case of \(k - 1\) cheating participants is given. Then it is shown that secret sharing schemes which meet the new lower bound can be obtained by using EDF. Also a weak converse theorem is proved, i.e. that if there exists a secret sharing scheme which meets the bound, then there exists an EBIBD. In the last section the notion of splitting BIBD is introduced and a Fisher-type inequality for splitting BIBDs is derived. Weak equivalence between splitting BIBDs and splitting A-codes is proved there, and the paper ends with a proof that an EDF implies a splitting BIBD.