Re: Key Evolving Encryption
From: Aldar Chan (I_love_Nora_at_Nora.and.Aldar.net)
Date: 10/18/04
 Next message: Aldar Chan: "Re: Key Evolving Encryption"
 Previous message: vedaal_at_hush.com: "Re: HELP...posting "selfdecrypting" PGP message question???"
 In reply to: David Wagner: "Re: Key Evolving Encryption"
 Next in thread: David Wagner: "Re: Key Evolving Encryption"
 Reply: David Wagner: "Re: Key Evolving Encryption"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Date: Mon, 18 Oct 2004 21:37:18 GMT
"David Wagner" <daw@taverner.cs.berkeley.edu> wrote in message
news:cl13kj$2qs6$1@agate.berkeley.edu...
>>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 subtree? What I mean is: Now in BTE, we start from
the root, build a tree and assign keys from a topdown direction. Can
we do it in a bottomup manner to grow an existing tree upwards by
adding a new leftsibling 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
pairingbased 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.
 Next message: Aldar Chan: "Re: Key Evolving Encryption"
 Previous message: vedaal_at_hush.com: "Re: HELP...posting "selfdecrypting" PGP message question???"
 In reply to: David Wagner: "Re: Key Evolving Encryption"
 Next in thread: David Wagner: "Re: Key Evolving Encryption"
 Reply: David Wagner: "Re: Key Evolving Encryption"
 Messages sorted by: [ date ] [ thread ] [ subject ] [ author ] [ attachment ]
Relevant Pages
