US 2007/0168659 A1Published application

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

AssigneeNtt Docomo, Inc.

InventorsCraig Gentry, Zulfikar Ramzan, David Woodruff

Life of this patent

Estimating the term…

Loading patent…

Abstract

In a broadcast encryption scheme, an optimal or near-optimal set covering CV(f,P) is computed for a set P of privileged users and at most a predefined 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. More particularly, possible assignments of free riders to the subsets are examined, and an assignment is selected to fit an optimality criterion for the total set covering. 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 (no elements containing the child as a proper subset and itself being a proper subset of the parent). An ordered list MP of meeting points is computed efficiently. The list is ordered by the number of elements in a chain from the meeting point to the root. The complete-subtree method is used in some embodiments. The methods have applications besides broadcast encryption, e.g. certificate revocation.

Claims22

Dependent claims

A computer-implemented method for selecting data to form messages for transmission, the messages being associated with sets of entities, the method comprising:

(1) obtaining first computer data representing:
(1A) a set U of the entities;
(1B) a target set P which is a subset of U;
(1C) a set system CS(U), the set system being a set of subsets of U;
(1D) a maximum positive number f of free riders to be allowed in constructing an f+-redundant cover CV=CV(f,P) for the target set P, wherein the cover CV(f,P) is to consist of zero or more sets S that are elements of the set system CS(U) such that a union of the sets S comprises the target set P and at most f entities from a set R=U\P, wherein the data to be selected are data pieces associated with the elements of the cover CV;
(2) performing a free-rider assignment by designating at least zero and at most f entities of R as free riders, wherein performing the free-rider assignment comprises, for at least one subset v which is an element of the set system CS(U), and for at least one positive number fv≦f, determining a cost of an fv+-redundant cover of v, wherein a cost of any cover is a non-constant, non-decreasing function of the number of elements in the cover;
wherein determining the cost of the fv+-redundant cover of v comprises:
(2A) determining disjoint non-empty subsets x1, x2, . . . which are subsets of v and are elements of the system CS(U);
(2B) selecting two or more tuples of numbers (f1, f2, . . . ) of non-negative integers f1, f2, . . . , wherein the sum of the numbers in each tuple does not exceed fv, each tuple representing a candidate assignment of at most fi free riders to xi for each i=1, 2, . . . to obtain an fv+-redundant cover of v;
(2C) selecting, from said tuples, a tuple for which the corresponding candidate assignment provides an optimality cost of an fv+-redundant cover of v, wherein an optimality cost is a cost having a predefined optimality relation to a minimum cost.

7 more elements

A computer-implemented method for selecting data to form messages for transmission, the messages being associated with sets of entities, the method comprising:

(1) obtaining computer data representing:
(1A) a set U of the entities;
(1B) a target set P which is a subset of U;
(1C) a set system CS(U), the set system being a set of subsets of U;
(2) determining a cover CV to cover at least the target set P, wherein the cover CV is to consist of zero or more sets S that are elements of the set system CS(U) such that a union of the sets S comprises the target set P, wherein the data to be selected are data pieces associated with the elements of the cover CV;
wherein determining the cover CV comprises:
(2a) computing an ordered set MP of all meeting points in CS(U), with the meeting points being ordered by their heights, a meeting point being an element of system CS(U) such that the element either:
(a) has at least two immediate children in CS(U) each of which comprises an element of R=U\P, or (b) consists of a single entity which is an element of R, wherein any element e1 of CS(U) is called an immediate child of another element e2 of CS(U) if e1 is a proper subset of e2 and there is no element e3 in CS(U) which contains e1 as a proper subset and which is a proper subset of e2, wherein a meeting point's height represents a number of elements of CS(U) in a chain of elements beginning with the meeting point and ending with the chain's last element which is not a subset of any element of CS(U), with each element except the last element in the chain being an immediate child of the chain's next element;
and
(2b) determining the cover CV from the meeting points.

7 more elements

Dependencies are inferred from the claim text.

Facts

Application: 11/561,096Filed 17 Nov 2006
Priority: 22 Nov 2005
Published: 19 Jul 2007
Term ends: Not estimatedThe source records don’t support an estimate.

Classification5 codes

H04L 9/0822
Key transport or distribution, i.e. key establishment techniques where one party creates or otherwise obtains a secret value, and securely…: using…
H04L 9/3265
Involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements: using…
H04L 9/3268
Involving certificates, e.g. public key certificate [PKC] or attribute certificate [AC]; Public key infrastructure [PKI] arrangements: using…
H04L 2209/601
Digital content management, e.g. content distribution: broadcast encryption