On Fri, 21 Dec 2001, Len Sassaman wrote:

Publishing failure notifications with sender-provided keys, as Steve Schear suggests, seems likely to have large implementation and usage hurdles. (A separate user's public key for each remailer in the chain would have to be sent along with each message, and managing this would become quite difficult for the user.)

One way around this management issue might be to use a public-key cryptosystem which supports "key blinding." (Note - A Google search reveals that this term seems to be used in other places as well, and it looks like the usage there is not quite consistent with the way it is used in this message. Caveat lector.) David Hopwood has done some amazing work on formalizing the concept, which informally goes something like this: A public-key cryptosystem supports "blinded keys" if there is an efficient randomized algorithm which takes a public key PK and outputs a new public key PK' such that * [Key compatibility] Messages encrypted with PK' can be decrypted by the secret key associated with PK. (Ideally with no extra state required to decrypt these messages, unlike blinded signatures, which must be "unblinded" to be useful.) * [Key unlinkability] Given PK', an adversary cannot determine that PK' was created by blinding PK. for this application, we also need something perhaps stronger * Many many PK' can be created from the same PK and none of them can be linked with each other (as well as not linked with the original PK) This is somewhat like Ross Anderson's "compatible weak keys," except that it does not require that a new private key be created along with the new public key. With blinded keys, the management issue you mention becomes much simpler, I think. Instead of managing dozens of public-private key pairs, you have only one pair (PK,SK). To create a one-use public key for the purpose of status notification, you create a blinded key PK'. Anything encrypted with PK' can be decrypted by your SK, but the key unlinkability properties prevent the remailers from correlating messages based on PK'. One way to create a key-blinded cryptosystem is to consider Elgamal public keys as the pair (g, y), where y = g^x for private key x. Then to blind a public key, pick a random blinding factor b and let the blinded key be (g^b, y^b). With this, you do not need to keep track of the blinding factor b; the change in generator to g^b will do that for you. So you can get away without keeping any state on your end beyond your private key x. For more detail, currently the best thing to do is a groups.google.com search for David Hopwood and "BRH-DHAES." We keep meaning to write this up, but never get around to it. -David