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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

   There is no way to authenticate a program running remotely.  
   In fact, there's no way to authenticate a program running locally
   to not be receiving instructions through some covert channel.

No,  actually we can  authenticate   programs  remotely, it's only   a
question of how practical is this.  First of all,  we have to view the
game played  as a kind of "signature"  identifying a program.   In the
same way that a cryptographic signature  is based on the very unlikely
possibility that  two keys will  "sign" to the  same value, we can say
that  a program's signature    is  based  on the  extremely   unlikely
possibility that any other  program will play  ALL the same   moves as
some other program will.  This is EXTREMELY unlikely, so the rest is a
"small" matter of protocol but how do you set this up?

First of all, you must checksum your executable (in a crytographically
secure way.)  Your program must be deterministic in the sense that you
can identify  and checksum the state of  your  program BEFORE you have
access to  each of your   opponents replies.  Taken together,  with  a
move,  you have encapsulated  everything needed  to (weakly) sign each
move.   Each move your   program   makes is a cryptographically   weak
"signature."  But 100  moves   put together is  an   incredibly strong
signature, which is (at least in the cryptographical sense) proof that
the set of moves indeed belong to your program.

In practice, this is a royal pain  to implement, and it seems unlikely
we will be seeing  it done.  It may  be much more difficult with  some
programs that others   due to several technical  implementation issues
that I won't go into but it's certainly not an impossible task either,
any good programmer  could implement  the protocol  if the  effort was
deemed worthwhile.

The programs would not have to be sent to an arbiter, unless a disptue
occured.   Then the program  itself along with  any and  all the state
captured in  advance by the  referee  program watching  the game  will
prove or disprove whether a program is authentic.

There are other problems this doesn't neccesarly address.  One of them
is that we have to view the hardware a program runs on  as part of the
programs "state" if  the program itself  takes advantage of additional
memory (for instance.)  And what if I take  YOUR program and represent
it as my  own?  Using  the method I   just  outlined, I can give   the
arbiters a version that checks out fine in every way.  However if this
was every suspsected, then other methods could  be used to resolve the
matter (like, let's see your source code you cheater!!)

In practice, I don't see this as ever happening unless the process can
be greatly simplified.  In principle, however, full authentication can
be achieved and requires no technology we don't  already have, so it's
implementable right now.

Don