Re: Key Evolving Encryption

From: David Wagner (daw_at_taverner.cs.berkeley.edu)
Date: 10/29/04 

Date: Fri, 29 Oct 2004 05:51:16 +0000 (UTC)

Aldar Chan wrote:
>[...] "timed release encryption" [...] we send
>an encrypted message to a recipient Bob in such a way that he cannot
>open it until the specified release time, as indicated by a passive time
>server, has passed. A generic construction is as follows: I pick two keys
>k_1 and k_2, encrypt k_1 using Bob's public key and k_2 using an identity
>based encryption (with the release time T as the identity and the time
>server as the private key generator). k_1 and k_2 are then combined
>(say XOR) to form a key for encryption. Let's assume we use the
>pairing-based IBE. At any time instant t, the time server releases the
>private key for the identity t, [...]
>
>Now the problem related to key evolution is as follows: Suppose Bob
>missed out the private key release of sH(T), how can he still get back
>sH(T) (or t_2) using any sH(T'), T' > T?

Sure, there is an elegant solution using tree-based (hierarchical) IBE.

Represent each node in a binary tree by a binary string x representing
the path from the root to x, so that the left child of x is x0 and the
right child is x1. A tree-based IBE scheme is one where there is a master
public key PK, and a private key SK_x at each node x with the property
that anyone given SK_x can derive SK_x0 and SK_x1. If c = E(PK,x,m)
denotes encryption of message m to identity x, then D(SK_x,c) yields m.

Binary trees have a useful property. If I want to allow you to compute
SK_x for all leaves x "to the left of" a given leaf y (equivalently,
all leaves x where x <= y, when considered as integers), then I can do so
by revealing the private keys at just O(lg n) internal nodes in the tree.

Now here is the scheme. Express t as a binary number, so that it can
be viewed as a leaf in such a binary tree. Encrypt k2 using identity t.
At time t, the time server releases not just SK_t, but a set of O(lg n)
private keys sufficient to compute SK_u for all u <= t, namely, those
private keys at the O(lg n) internal nodes as mentioned above. This
should solve the problem you referred to, I would think.

Relevant Pages

  • Re: Does W2K hold users email, EFS etc private key securely ?
    ... the location of private keys doesn't depend on how the Encrypted Data ... the file encryption key is not the public key. ... It is the FEK that is encrypted using the user's EFS public key, ... protect your EFS keys by limiting the success of password guessing or theft. ...
    (Focus-Microsoft)
  • Re: Encrypting Email: What do I Need?
    ... > recipients have their own X.509 certificates. ... > all keeping our private keys to ourselves. ... but I am new to encryption. ... - you use the PUBLIC key of any recipientto encrypt THAT the symmetric key bytes ...
    (microsoft.public.dotnet.security)
  • Re: Fortune 50 secure e-mail
    ... >explicitly saying that they *didn't* store any private keys except their ... It's exactly the same thing PGP ... does - using a passphrase to decrypt the key when needed. ...
    (comp.security.misc)
  • Re: Serious EFS Issue
    ... Are private keys that were used to file encryption still in user's profile? ... > scenario where I encrypted an end user's My documents folder (Redirected ... She receives denied because of user access privileges. ...
    (microsoft.public.windows.server.security)
Loading