Re: Key Evolving Encryption

From: Aldar Chan (
Date: 10/18/04

Date: Mon, 18 Oct 2004 21:37:18 GMT

"David Wagner" <> wrote in message
>>David Wagner wrote:
>>> I guess I'm lost. Were we talking about forward secrecy, or
>>> something else? What do you mean by timed release encryption?

I'm sorry that I didn't track closely to reponse timely. I had posted
another message before the one you looked at yesterday to describe
the detail why and how I need key evolution for the timed release
encryption problem. It's attached below. In fact, you've got
most of what I posted.

The only question that is still my concern is how we can extend the
scheme in Canetti's paper to infinite N efficiently if we transverse the
tree in an opposite direction as time goes by, i.e. the root is associated
to epoch N. Is there a simple way that we can add a new root and a
new left sibling sub-tree? What I mean is: Now in BTE, we start from
the root, build a tree and assign keys from a top-down direction. Can
we do it in a bottom-up manner to grow an existing tree upwards by
adding a new left-sibling subtree and a new root while evolving
the new public key (for the new tree) in a deterministic way?

Sorry for the confusion; I should have filled in more details. I am
considering the "timed release encryption" problem in which 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, which is of the form sH(t) where s is the
server's private key and H() is some hash function. To decrypt a
ciphertext, Bob can compute k_1 using his private key but have to wait
for the time server to release sH(T) to get k_2. Of course we could
optimize this scheme by merging the two public keys and T in a single
pairing, so that the ciphertext is 50% less. For simplicity, let's ignore
that optimization.

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?

As can be seen, the private keys evolve in the opposite direction,
compared to the forward secrecy problem. Given any private key for
T, we should be able to find all previous private keys for any t < T but
not those in the future for any T' > T. Of course we also need a
constant public key for the time server, just augmenting it with different
T for different release time.

A naive solution may be sending all sH(t), for all t < T, with sH(T). But
this require O(N) message size for N time steps. I was thinking if there
is any way to link those sH(t) together to reduce the message size but it
seems to violate the security property needed. Another way may be
let the sender to specify in the encryption how many missing time server
updates is allowed to recover k_2, but it seems to have O(n) overhead
in the ciphertext. Any suggestions and comments are very appreciated.

Relevant Pages

  • Re: RSA breaking vs. factoring
    ... affects the two possible usages of RSA both for encryption (first public, ... then private key) and for signing ... are identical to encryption, in reverse order. ... Digital signature generation takes an input message (which may be quite ...
  • Re: CryptAPI(encryption/decryption)
    ... It seems like you're missing the Base64 decode step when trying to decrypt ... I misspelled the Private Key as Primary Key. ... Is there any variation in the encryption format in openssl compared to ... "Dylan DSilva " wrote: ...
  • Re: RSACryptoServiceProvider decrypt with public key
    ... private key which my programs could decipher using a public key I've ... But since private key encryption and public key decryption isn't ... > If Alice gives Bob her public key, ...
  • Re: CryptAPI(encryption/decryption)
    ... The openssl encrypted data format is in bigendian ... Is there any way I can import the PEM formated private key to the MS CSP ... I'm decoding the base64 encoded data before trying to decrypt. ... Is there any variation in the encryption format in openssl compared ...
  • RE: PGP scripting...
    ... cryptosystems, ... In these systems divulging your private key compromises the public ... Here is a quick over view of the public key encryption routines (the ...