At, I believe, the cypherpunks physical meeting before last I gave a technique for making tokens which can be compared but not canonicalized. Rather than try to define this precisely, which is rather hard to follow, I'll give my (broken) technique, and explain what's wrong with it. A common prime p is universally settled on. To generate a token, Alice picks some random values b and c and constructs the ordered pair (c^b (mod p), b (mod p-1)). Every time she wants to use it again, she picks some random value r and brings the first number to the r power and multiplies the second number by r. To compare two tokens (c^b, b) and (d^e, e), she computes (c^b)^e and (d^e)^b and compares them - they'll be the same if and only if c and d are equal. The problem with that scheme (and I'm a little embarassed for not having seen this immediately) is that it's possible to compute 1/b (mod p-1) and compute c^b to that power, resulting in c, which can of course be hashed. I've been trying to come up with a fixed version and cannot for the life of me find one. I'm inclined at this point to conjecture that it's impossible, which makes it by far the most plausible-sounding yet probably impossible cryptographic primitive I know of. If anybody can come up with a non-hashable tokens technique I'll be very impressed. If anybody can find a proof that there is none I'll be even more impressed (since proving things impossible seems to be out of the reach of complexity theory these days.) Just thought I'd throw that out. Had to vent. Not being able to find one is getting on my nerves. -Bram Cohen
