Patent ID: 7721089

Claim:
A method for encrypting a digital message between a broadcast source and a plurality of n users including r revoked users, such that a coalition of r<n/3 revoked users cannot decrypt the message, but each member of a selected subset of n−r privileged users can decrypt the message, the method comprising: allocating at least one primary key to each user; generating at least one secondary key; generating ciphertexts by encrypting the digital message using the at least one secondary key; and communicating the generated ciphertexts to the privileged users, wherein the number of generated ciphertexts is at most r(log a (n/r)+1) and the product of the key derivation cost and the number of primary keys for each user is at most (2a−log(a)−2) log a (n) when a=2 b , 1≦b≦log n, and a≧3; wherein the method further comprises forming a binary tree, with the broadcast source being associated with the root of the binary tree, and the plurality of n users being associated with the leaf nodes n u of the binary tree, wherein n i is an ancestor of n j , and n i is on the path from n i , to the root, and wherein the primary key K n i ,n j εK u is generated for each of the leaf nodes n u , such that n i is an ancestor of n u , but n j is not an ancestor of n u , wherein K u is the set of primary keys; wherein the method further comprises generating a key K n i ,n j εK for a node pair (n i ,n j ) such that └l(n i )/b┘=└(l(n i )−1/b┘, wherein l(n i ) and l(n j ) are the depth of nodes i , and n j from the root, 1≦b≦log 2 n, and K is the set of all secondary keys; wherein the method further comprises selecting a set of keys K p εK, wherein P is a set of privileged users, so that each user in P knows at least one key in K p , but no revoked user does; wherein the method further comprises generating a node-pair set {(n i , n j ): n i is an ancestor of n j }, such that each privileged user u, but no revoked user, has a node-pair in the set, wherein n i is an ancestor of n u , but n j , is not an ancestor of n u ; wherein the method further comprises decomposing each node pair into a node-pair key-set k n i ,N l , k N 1 ,N 2 , . . . , k N z ,n j εK, wherein n i is an ancestor of N1, N1 is an ancestor of N2, and so on, such that └l(n i )/b┘=└(l(N 1 )−1)/b┘.