The difficulty of making non-hashable tokens

[Bram Cohen]

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

Re: NTRU Public Key Cryptosystem

[dmolnar]

On Mon, 17 Apr 2000, dmolnar wrote:

 
 Hi,
 Is it known how tightly related NTRU is to the shortest vector problem? Is
 there a reduction known yet from SVP to NTRU, or is it still in a
   ^^^
my mistake -- from NTRU to SVP is what I should have written!

Thanks, 
-David

Re: The difficulty of making non-hashable tokens

[Bram Cohen]

To clarify what I mean by 'non-hashable token' - There is a format for
identifiers, and a function for 'scrambling' them, so that they look very
different, but there's a function which can accurately compare two
identifiers ('tokens') regardless of how scrambled they are. By
'non-hashable' I mean that given a set of n tokens, there should be no
algorithm for determining if there's a pair of identical ones better than
doing all n^2 - n comparisons. 

An example motivation: Say you have a very large database of user logins,
and you would like for users to be able to give you their history and for
you to verify it, but you're worried about an attacker getting access to
your database and analyzing it. What you do then is you give each user an
unhashable token as an identifier, and whenever you store login records
you store a login date and a scrambled version of the login id. Then, if
someone wants to demonstrate their login history they send you the dates
and their id and you can verify it, but analyzing the database as a whole
requires a lot of work.

Well, so that's not a particularly strong motivation, but hopefully it
clarifies.

-Bram Cohen