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

[Don Dailey <drd@xxxxxxxxxxxxxxxxxxxxx>]

I think  I  was  accused of  over-engineering,  but I   think  Nicol's
solution is more than good enough.  It's one of  many possible ways to
handle time control,  there are also  ones that can be managed locally
that won't severly cripple your program.

If  we really wanted  to get paranoid,  we  could use secure protocols
that are in common use already for network communication.

No one claimed any of  this was easy, but  it's easy to  make it a lot
more  commplicated than   it needs  to be by   requiring  more than is
necessary.


Don



   From: Mika Kojo <mkojo@xxxxxxxxxxxxxxxxx>

   Nicol N. Schraudolph writes:
   > On Sun, 10 Dec 2000, William Harold Newman wrote:
   > 
   > > If you have a proposal for preventing [cheating] without making it
   > > impossible for programs to use real-time clocks for time management,
   > > bring it on.
   > 
   > Easy enough:
   > 
   > 1) Managing your own time: require that the program measures time solely
   > by querying a game clock on the tournament server (make that part of the
   > communications protocol).  This is not limiting since the game clock is
   > indeed the only time that matters - just like "true randomness", "real
   > time" is quite irrelevant here.  During tournament play, the server
   > records all the program's time queries together with its own answers
   > to them.  During verification, the server expects the same sequence of
   > queries, and responds with the same recorded answers, regardless of the
   > actual timing.

   As I mentioned before any such trace can contain secret information,
   also this. The problem is that to keep this provably secure you would
   need to make sure that both the tournament program and the program
   sent to the verifiers are exactly same. Otherwise one could encode
   information into the recording and cheat.


   > 2) Using your opponent's time: if your program does this, it's bound to be
   > organized such that its computation can be interrupted by the opponent's
   > move at certain well-defined points.  At these points, have the program
   > poll the server "has opponent moved yet?".  The tournament server relies
   > on your polling to communicate the opponent's moves (no interrupts).
   > During tournament play, it records the number of polls received from
   > you for each opponent move.  For verification, server reproduces its
   > responses to your polls faithfully, regardless of the actual timing.

   Seems to be as troubling as the previous case. 

   Nicol's approach works only if we guarantee that the recordings are
   applied to the exactly same program that was used in the tournament. I
   have not written out explicit proof for this, but I'm sure it can be
   done. If the programs differ (that is, there is any chance for that)
   then such recodings make it possible for programs to cheat.

   -- 
   Mika Kojo
   SSH Communications Security Corp