From: David Vincenzetti <vince@dsi.unimi.it>
Date: Sun, 7 Jan 1996 02:17:43 +0800
To: hfinney@shell.portal.com
Subject: (cpx) Re: mental cryptography (fwd)
Message-ID: <199601061748.AA216460533@idea.sec.dsi.unimi.it>
MIME-Version: 1.0
Content-Type: text


> 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