Professor Itkis' Scheme
Professor Itkis' scheme is based on Wallner's scheme. It is a
dramatic improvement on the secure and secret storage needed on
the manager. Recall that M needs to store 2n
keys securely and secretly in Wallner's scheme. For large n,
it is probably not difficult to store 2n keys with
today's huge storage devices. However it is difficult to store them securely
and secretly. The larger data grows, the more it gets difficult to
store it securely and secretly. This scheme reduces the secret storage on M,
enough to fit on a
smart card. Secret storage is reduced to 2 keys only! For this
to work, we need to store a History of all the deletions that take place.
However, this history need not be stored secretly. M need not worry about
the secrecy of this History. If it is compromised and read, then that's
perfectly fine, as long as it is read-only. Using this History and the very
small secret at M, we can achieve the same
user-revocation results of Wallner's scheme
We assign a number to every node as follows:
For the root:
The node number is null.
For any other node:
The node number is the binary string representing the path from the root to this node, where 0 is a left move, and 1 is a right move. For example, if the path to some node is LRLRRLRLLL, then its node number is 0101101000.
Here's how this History is stored:
For a leaf node:
M records the number of deletions that took place at this leaf node.
For a non-leaf node:
M records the total number of deletions that took place in this node's subtrees.
(Note that deletions only occur at leaf nodes since users are at leafs only).
When later in the text we refer to "number of deletions at node i", or #di, this number would be defined by the definition we just made.
How do we achieve user revocation?
Recall that upon deletion of a leaf, all the keys on the path up to the root need to be changed. Notice that when a leaf is deleted, the number of deletions recorded (as defined above) at every node on the path up to the root is changed; it is increased by 1. Thus the number of deletions recorded is a property that is naturally changing when we delete a user, for every node on the path up to the root. Therefore, if we can define a node's key in a way that is somehow dependent on the number of deletions at this node, we can automatically get the change we want to the correct keys. This is easier than generating every key randomly at every change needed.
Here's how we define the keys:
As we said above, 2 secrets are stored at M. Let us call the first one s and the second a.
s is a permanent secret, it does not change. a on the other hand changes occasionally as we shall see later. Just keep in mind for now that on M, we talk about s and the current a.
Let Ki be the key at node i (where i is a node number). Define Ki as follows:
Ki = h(s, i, #di) Å a
- h is a hash function.
- #di is the number of deletions at node i (as defined above).
- a is the current secret a at M.
We will see later the use of the a term in this expression.
(Every key in the tree is computed this way, including the group key K whose node number is null.)
Defining the keys this way, spares M from the
storage of keys it needed to do in Wallner's scheme. M
can compute now any key it needs on the fly from s,
a, i and #di.
Now you can see why the #di's need not
be secret. Even if the #di's (the
History) is compromised, the intruder has no way of figuring out any key,
because every key is also dependent on the secrets s
and a. Defining the keys this way also grants us an
easy way of changing keys upon a user deletion. Upon a user deletion, the #di's
on the path from this user up to the root are changed accordingly (incremented
by 1). All that M
needs to do to generate the new keys on this path is apply the formula above for
every node, using the new #di's. When
the new keys are generated this way, re-keying messages are sent *exactly* the
same way as in Wallner's scheme. From the user's point of view *nothing* has
changed from Wallner's scheme so far.
Thus, user revocation is achieved in *exactly* the same way as in Wallner's scheme. What we have changed in this scheme has nothing to do with the method of user revocation. We have only changed the way keys are generated and the amount of data stored at M. And hence the re-keying overhead is still the same, i.e., 2log n - 1, and the user storage is still the same, i.e., log n + 1 keys.
The Use of a
The use of a in this scheme is for
hiding the past. Recall that we might/might not need to hide the past from a,
depending on the application and/or the user. Here's what we do:
Upon addition of a new user:
If hiding the past is a
M generates a new a, say a', and gives the newly added user its initial set of keys computed with the new a, i.e., a'. Then, it broadcasts to the group EK(a Å a') (where K is the group key). Every user then decrypts this message, and XORs every key in its set of keys with the decrypted value, i.e., with a Å a'. Watch the effect of this on a key Ki:
Ki = Ki Å (a Å a')
= (h(s, i, #d) Å a) Å (a Å a')
= h(s, i, #d) Å a Å a Å a'
= h(s, i, #d) Å a' [a Å a = 0; 0 Å a' = a']
This changes Ki to a new value and preserves our definition of Ki. Thus, since all the keys in the tree will be changed, the newly added user has no way of recovering the past.
You might be wondering: why change all the keys in the tree to hide the past from a newly added user? Isn't it enough to change the keys on the path from the corresponding leaf to the root? Well, yes, it is enough, but if we do that, we will have to send 2log n - 1 re-keying messages to the group (the same structure of messaging overhead that we would have sent if this user was being deleted rather than added). In the method we describe above, we broadcast only one single uniform message to the whole group. And the XOR operations at the users are very fast and cheap.
If hiding the past is not a
M behaves exactly the same way as it would have in Wallner's scheme. It just gives the new user its set of keys from the current keys.
Keep in mind that the manager does not store any keys at all. All it stores is the secrets s and a, and the History. This is the whole purpose of this scheme. The manager's access to any key is only through computation, using the formula we described. The manager computes any key it needs on the fly.
As you may have noticed, a leaf's (user's) "view of the tree" is the path from itself up to the root. The user's startup package consists of the list of keys on this path.