[6937] in cryptography@c2.net mail archive
Re: The difficulty of making non-hashable tokens
daemon@ATHENA.MIT.EDU (Bram Cohen)
Tue Apr 18 15:42:00 2000
Date: Tue, 18 Apr 2000 11:16:32 -0700 (PDT)
From: Bram Cohen <bram@gawth.com>
To: cryptography@c2.net,
People who supposedly write code <coderpunks@toad.com>
In-Reply-To: <Pine.LNX.4.10.10004172311400.6815-100000@ultra.gawth.com>
Message-ID: <Pine.LNX.4.10.10004181034160.2317-100000@ultra.gawth.com>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
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
