[Cryptography] Email and IM are ideal candidates for mix networks

[Jerry Leichter]

On Aug 28, 2013, at 4:24 AM, danimoth wrote:

> On 27/08/13 at 10:05pm, Christian Huitema wrote:
>>> Suppose, as in Bitcoin, my email address *is* my public key
>> 
>> You can even use some hash compression tricks so you only need 9 or 10 
>> characters to express the address as hash of the public key. 
>> 
>> That works very well, until you have to change the public key.
> 
> .. and until someone want to find a public key which shares the first 
> 10 digits of the hash with yours.
9 or 10 *characters*, not *digits*.  You need enough bits that, even given the birthday paradox, the probability of this occurring is low enough not to matter.  Since the birthday paradox will lead to a 50% probability of collision after about the square root of the number of possible values, given a 10-character signature, that's at about 5 characters.  Way too low, for digits.  If "characters" are full bytes, 2^40 generated public keys is plausible, though perhaps uncomfortably small; and if the "characters" have to be printable - then I agree, way too low.

You could use hash compression, but the retained compressed values will have to be rather larger.  Say 150 bits worth, at least.

On the underlying matter of changing my public key:  *Why* would I have to change it?  It's not, as today, because I've changed my ISP or employer or some other random bit of routing information - presumably it's because my public key has been compromised.  That's a disaster no matter how I identify myself, one that's very difficult to recover from - pretty much impossible unless (a) there's some way to revoke a key (yes, we've had problems with getting that to work even in the current PKI environment, but there's no real alternative); (b) I've prepared for the eventuality.  Given (a), I can send out a signed revocation message.  (So can the attacker, but presumably he had bigger plans for the key than just killing it.)  Given (b), I have pre-shared one or more replacement keys that I still trust, and my revocation can name the one to put into use.  (Of course, it cannot introduce a brand new key!)  Done this way, my response to key compromise is no different from normal key rollover.

                                                        -- Jerry