[freehaven-dev] "just in time encryption"

[dmolnar <dmolnar@hcs.harvard.edu>]

This message outlines the notion of "just in time encryption", why
freehaven could use it, and some not very deep examples of the notion. 

1) "Just In Time Encryption"

Just in Time Encryption refers to an encryption scheme in which either

	a) much of the computation involved can be done independently of
	the final message to be sent

	b) much of the computation involved can be done independently of
	the final identity of the recipient

	or both! 

We could probably invent terms to distinguish between a) and b) , but
let's figure out if the notion is useful first...

oh, and we should also find out if this has been covered before (somehow I
suspect the notion of precomputation for encryption is *not* new)

2) Why freehaven might care

Freehaven broadcasts require sending the same message to many different
destinations individually. Even though these messages are passing through
a mix-net, we may wish to encrypt such messages. This requires a lot
of processing power. As has been previously pointed out, if we can spread
that power out over time, we can better respond to sudden needs for
broadcasts. 

Alternatively, we could investigate just in time encryption for sending
mix net messages. This will have to be the subject of a separate 
message, since now we are trying to make both the encryption and the
mix-net formatting have the "just in time" property. In particular, 
I have to go look at the Mixmaster format in detail to see what happens.

3) Examples for freehaven

These examples do not actually modify any cryptosystems. Instead they
just notice that we can do the public-key operations at once. This saves
time because public-key stuff is more expensive than symmetric key.

Creating a just in time symmetric algorithm would be kind of cool, but
short of pre-agreeing on one time pads or something I'm not sure what
you would do. Creating a just in time public key algorithm might be more
doable, but maybe not worth the bother ?

In the freehaven setting, a message to a particular servnet node 
consists of these parts :

	a) the message itself, encrypted with a symmetric algorithm
	and checked with a message authentication code.
	
	b) the key used to encrypt part a), encrypted with the public
	key of the destination node

	c) the formatting for the mix-net of parts a and b (which may
	involve many more public keys and encryptions and whatever)

freehaven just in time encryption independent of message :

The idea is that we compute many part b) in advance, for each possible
destination node. Alternatively, we could agree on a _persistent_ shared
key for each node and refresh it fairly infrequently. This persistent
solution has the major drawback that it requires keeping state, so I 
don't like it. 

So now we have a lot of different symmetric keys encrypted to different
destinations. When we want to send a message, we grab an encrypted key, 
look up its decryption in a table, and then use that to symmetrically
encrypt something. Then we send the result. 

Since symmetric crypto is fast, this cuts down our time to send messages.
The drawback is that now we must cache lots of pre-encrypted keys. and
we have to estimate demand for keys. 

freehaven just in time encryption, precomputation independent of destination :

Precompute lots of symmetric keys. Use these to encrypt messages which
we know we will send before we know the destination (are there any of
these? buddy checkup requests?). At send time, take the symmetric key and
encrypt with the public key of each and every destination. 

freehaven just in time encryption independent of dest or message :

Pre-agree on lots of one time pads with everyone. Then when it comes
time to send message, we just do an XOR of the pad with the message
for the appropriate pad. 

Something about these distinctions doesn't seem quite right yet. comments
and better examples appreciated.

Thanks, 
-David