More on remailers.

dmolnar dmolnar at hcs.harvard.edu
Fri Dec 21 15:01:06 PST 2001


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





More information about the cypherpunks-legacy mailing list