Tree-based key distribution patterns

Abstract

We revisit a key agreement scheme presented by Leighton and Micali [11], generalize the scheme, and present a new framework of tree-based key distribution pattern (TKDP). We presents a method of constructing TKDPs from cover-free families. We show the existence of TKDPs by probabilistic method. We can reduce the upper bounds on the minimum number of rows of (t,w,T)-TKDPs, which are obtained from probabilistic methods, asymptotically by a factor of w as compared to Leighton and Micali's schemes by choosing optimal trees T instead of chains.