We develop a couple of new methods to reduce transmission overheads in broadcast encryption. The methods are based on the idea of assigning one key per each partition using one-way key chains after partitioning the users. One method adoptsskippingchainson partitions containing up toprevoked users and the other adoptscascadechainson partitions with layer structure. The scheme using the former has the transmission overhead [(r)/(p+1)]+ [(N-r)/(c)], which is less thanr/pifr>p2N/c. The scheme using the latter keeps the same transmission overhead with the subset difference (SD) scheme whenrapproaches 0, whereris the number of revoked users. Combining the two schemes, we propose a new broadcast encryption scheme whose transmission overhead is the same with that of the SD scheme for smallrand becomes smaller than that of the SD asrgrows. The scheme using skipping chains possesses an advantage that any number of new users can join any time at no cost for current users. Finally, we show that the proposed key assignment scheme satisfieskey-indistinguishabilityassuming pseudorandom generators.

Since broadcast encryption was first introduced in 1993 by Fiat and Naor, many broadcast encryption schemes have been developed. Among these, schemes based on tree structure and linear structure are notable. The subset difference (SD) scheme and layered subset difference (LSD) scheme based on tree structure have small user-key size and small transmission overhead when the number r of revoked users is very small. The punctured interval (PI) scheme based on linear (or circular) structure has better transmission overhead when r is not too small.In this paper, we propose a new broadcast encryption scheme, called the tree-based circle (TC) scheme, combining tree structure and circular structure. In this scheme, the transmission overhead is proportional to r like in the SD scheme for small r and becomes asymptotically same as that of the PI scheme when r grows, keeping the computation cost and the storage size small. The TC scheme also inherits the flexibility of the PI scheme. We further improve the transmission overhead of the TC scheme, when r is very small, by adopting the notion of cascade arc.