Rotating file-lockbox keys

Whenever a user's access is revoked, the file owner generates a new version of the file-lockbox key. For this discussion, let $v$ denote the version of the file-lockbox key. The owner generates the next version file-lockbox key from the current key by exponentiating the current key with the owner's private key $(d,N)$: $K_{v+1} = K_v^d\ \mbox{mod}\ N$. This way only the owner can generate valid new file-lockbox keys.

Authorized readers get the appropriate version of the file-lockbox key as follows. (Figure 2 illustrates the relation between the different file-lockbox key versions.) Let $w$ be the current version of the file-lockbox key that a user has.

• If $w = v$ then the reader has the right file-lockbox key to access the file.
  
• If $w < v$ then the reader has an older version of the key and needs to request the latest file-lockbox key from the owner.
  
• If $w > v$ then the reader needs to generate the older version of the file-lockbox key using the following recursion. If $K_w$ is the file-lockbox key associated with version $w$, then $K_{w-1} = K_w^e\ \mathrm{mod}\ N$, where $(e,N)$ is the owner's public key. Readers can recursively generate all previous file-lockbox key from the current key.

In the above protocol, we use RSA encryption as a pseudorandom number generator; repeated encryption is not likely to result in cycling, for otherwise, it can be used to factor the RSA modulus $N$ [33]. Though we use RSA for our key rotation, the property we need is that there be separate encryption and decryption keys, and that the sequence of encryptions is a pseudorandom sequence with a large cycle; most asymmetric cryptosystems have this property.

Though this scheme resembles Lamport's password scheme [27], our scheme is more general. Our scheme provides for specific users (owners) to rotate the key forward, while allowing some other users (readers) to rotate keys backwards.