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.)

The paper can be found in the proceedings of Eurocrypt '91, D.W. Davies (Ed.), Springer-Verlag. The author is Hideki IMAI, <tsutomu@mlab.dnj.ynu.ac.jp>. I found the above paper very interesting, and I am actually going to code it up. Eventually, I would be highly interested in giving a glance at your code. Is your code available? Ciao, David