The Mad Scientist in the Middle writes via anonymous-remailer@shell.portal.com:

The answer is doing cryptography in your head. Well not quite, since many cryptographic operations are very computing intensive, and not everyone can do 1000 bit mental modular exponention in a reasonable amount of time. But if you have a piece of secure hardware that you can trust to do some of these operations for you, then all you need is a secure communications channel to this piece of hardware.

There may be other ways, but I suggest that you establish a common key with your crypto server ahead of time, and then simply encrypt all your communications using a symmetric algorithm. RC4 may be a reasonable choice, since the operations are simple and easy to remember, but you need to keep track of a 255-byte state. WAKE is probably better. Although it uses a large key table, you only have to memorize it once, after which the only state that is changing is four 32-bit registers.

I am not familiar with WAKE but I doubt that you could literally hold 128 bits in your head and manipulate them. This is a problem which I have wondered about for some time. Presumably if we went to a digital cash world we would use smart cards to buy things, but how do we make sure that nobody steals and uses our smart cards? Just typing in a PIN doesn't seem very safe to me, especially if the card doesn't have a keypad built in and you're using a keypad in the card reader as is often the case today. Even with a pad on the card you have to worry about eavesdroppers. Biometric ID's (fingerprints, and Senator Feinstein's retina scans that she wants to put on our national ID cards) have been proposed to solve this but they are expensive and unreliable right now. An information based solution would be best if it were possible. I have read one paper which attempts to solve this problem, called "Human Identification through Insecure Channel". Unfortunately my papers are in a mess right now so I don't have the reference handy. It was by some Japnese researchers, published in one of the proceedings books. I believe a follow-on paper was published within the last year or two which had some improvements or corrections to their algorithm. Sorry to be so vague, I'll try to dig out more info over the weekend. Basically they used a challenge-response system which was intended to be simple enough that people could do it in their heads. The card would display a random challenge string, some characters of which were special to the user and others which he would ignore. He would then input a response string, where it didn't matter what corresponded to the "ignore" slots, but in the special slots he had to produce certain symbols corresponding to the other symbols, with the rules changing as you move along. The intention was that even by capturing and analyzing a great many challenge-response pairs you couldn't create a response to a challenge you hadn't seen before. I coded this up, and frankly, I couldn't do the required manipulations in my head, at least not without taking a very, very long time, and thinking very carefully. Maybe it would get easier with practice, I don't know. But my overall feeling was that this would be at the limits of human capability even for fairly bright people. (OTOH I suppose learning to read and write might seem pretty tough if you'd never done it. Maybe the 1st grade classes of the future will spend months training the kids on how to use these kinds of algorithms.)

I am sure better algorithms can be found for this purpose if mental cryptography is made explicit as a design goal. Perhaps it should be?

It's a hard problem to solve in general because you have only a human mind to do the identification algorithm but you have computers to try to break it. But I would like to see the problem get more attention. Hal

Nathan Loofbourrow writes:

C.-H. Wang, T. Hwang, and J.-J. Tsai, "On the Matsumoto and Imai's [sic] human identification scheme." (LNCS 921, 1995)

Uh, silly me, that happens to be the EUROCRYPT '95 proceedings. Boy, and isn't it fun to receive all the bounce messages from every post to cypherpunks? nathan