Re: computer-go: Authenticating the identity of a remote go-playing computer program

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

> Your method would not detect cheating; it would provide a somewhat
> reasonable means to resolve a challenge if cheating were suspected.
> Unfortunately, I can easily meet the challenge while cheating as
> much as I want.  I simply remember the moves supplied by my secret
> 7 dan, and always present those moves if I'm ever presented with
> the same position again.

Yes, my method  is not designed to detect cheating  as it happens, but
could be extended to detect all cheating after the fact (but of course
it would be quite unweildly to do this!)

Here is a typical scenario that I think would be well covered: 

Before the tournament  begins,  you provide the  tournament organizers
with a  crytographically secure checksum of  the program you intend to
run.  During the tournament, your program beats my program, I turn out
to be a  sore loser and accuse you  of really using a  7 dan player to
make your  moves.  I  complain to the  arbiters,  and now now  you are
given an opportunity to clear your good name.

The arbiters  don't have a copy of  your program, but because  of this
dispute you are now required to forward a copy to them.

They recieve your program and run their own checksum against it.

Now, one of two things will happen:

  1.  You cannot give them an executable with the checksum you
      originally provided.

  2.  You give them an executable that they can verify is the
      one you claimed to have run.


In the first case,  since you cannot  produce a verifiable executable,
you cannot produce evidence that your program actually played the game
and the arbiters rule in my favor.

In case 2, nothing has yet been proved EXCEPT  that they have in their
possession,  the very same executable  that  you CLAIMED to have  used
during the tournament.

There is   only  2 ways  for you  to   "beat this rap."  If   you were
completely  honest about everything,  they will do  a test and quickly
learn that the program in their  possession plays exactly the same way
the program  in the tournament  played, and  I  will be  chastised for
making  false accusations  against   you.   

But if  in fact you  had been dishonest,  your last recourse (assuming
you don't want  to admit your  dishonesty) is to  produce a brand  new
executable  that remembers all the moves  the  7 dan player played and
spits them out faithfully.  However, this is probably a more difficult
challenge than actually writing a 7 dan program because your are going
to have a difficult time making the md5 fingerprint (that you provided
before  knowing what  moves would   be played)  match up   to this new
executable!

In principle, all of this  is very difficult to  get right, and as was
mentioned before, getting everyone to implement the protocol correctly
would be such a problem I don't think it would fly!



Don