GENERATION OF SET COVERINGS WITH FREE RIDERS, AND GENERATION OF ORDERED SETS OF MEETING POINTS, IN SYSTEMS WHICH INCLUDE, BUT ARE NOT LIMITED TO, SYSTEMS FOR BROADCAST ENCRYPTION AND SYSTEMS FOR CERTIFICATE REVOCATION

摘要

PROBLEM TO BE SOLVED: To compute an optimal or near-optimal set covering in a broadcast encryption scheme.;SOLUTION: An optimal or near-optimal set covering CV(f, P) is computed for a set P of privileged users and at most a predetermined number (f) of revoked users ("free riders"). The covering consists of elements of a predefined set cover CC(U) for the set of all users U. The covering is computed by finding optimal or near-optimal coverings for privileged users for CC(U) elements that are proper subsets of U. In some embodiments, only "meeting point" elements of CC(U) are fully examined. A meeting point is an element containing at least two "immediate child" elements each of which contains a revoked user. An immediate child of a "parent" element is a proper subset of the parent with no intermediate elements. An ordered list MP of meeting points is computed efficiently.;COPYRIGHT: (C)2010,JPO&INPIT