Professor Itkis' Scheme

Home ] Wallner's Scheme ] [ Professor Itkis' Scheme ] Implementation ]

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

Node Numbers

We assign a number to every node as follows:

History Definition

Here's how this History is stored:

User Revocation

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:

Please Note

Home ] Wallner's Scheme ] [ Professor Itkis' Scheme ] Implementation ]