Size of broadcast in threshold schemes with disenrollment

Abstract

Threshold schemes are well-studied cryptographic primitives for distributing information among a number of entities in such a way that the information can only be recovered if a threshold of entities co-operate. Establishment of a threshold scheme involves an initialisation overhead. Threshold schemes with disenrollment capability are threshold schemes that enable entities to be removed from the initial threshold scheme at less communication cost than that of establishing a new scheme. We prove a revised version of a conjecture of Blakley, Blakley, Chan and Massey by establishing a bound on the size of the broadcast information necessary in a threshold scheme with disenrollment capability that has minimal entity information storage requirements. We also investigate the characterisation of threshold schemes with disenrollment that meet this bound.