unforgeable optical tokens?

[John S. Denker]

"Perry E. Metzger" wrote:
> 
> But if you can't simulate the system, that implies that the challenger
> has to have stored the challenge-response pairs because he can't just
> generate them, right? That means that only finitely many are likely to
> be stored. 

Those observations are true, but they don't nullify
the main feature of the system.

Forget about optics for a moment.  Model the token as a
gigantic ROM with 10^12 cells of one bit each.  The ROM
will need 40-bit addresses just to address all those cells.

Before the token is issued, the issuer will choose a few 
million addresses at random and probe the ROM at the 
corresponding locations, and store the results in a table.

After the token is issued, it can be challenged.  A
challenge consists of 60 or so addresses, taken at random
from the aforementioned table.  An impostor would have
one chance in 2^60 of guessing the correct responses.

To clone the token would require the bad guys to do a
million times more work than the legitimate issuer, because
the cloner would need to copy all cells of the ROM,
whereas the issuer needs only to probe (and remember)
only enough for a lifetime's worth of challenges (or
even less than a lifetime, if you want to return the
token to the issuer every so often to 'freshen' the
table).  The point being that the cloner doesn't know
which addresses will be probed by challenges.

Finally, all you need is a way to cheaply create a ROM
with many, many bits of quenched randomness.  Microbeads
in epoxy is one way of doing that.

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at wasabisystems.com