Implementing an Electronic Notary Public

Many communication security problems admit both “physical” and “mathematical” solutions. For example sending a message from A to B without exposing it to C, can be accomplished physically by means of secure courier, or mathematically by means of encryption. With the advent of public key cryptography, many problems originally believed to be solvable only by physical means have been shown to have mathematical solutions (e.g. key distribution [DB], secret sharing [S], coin flipping [B], mental poker playing [SRA]), In this paper we describe a mathematical solution to a communication security problem, which arose in connection with the Nuclear Test Ban Treaty, and for which only physical solutions were known, The problem concerns the implementation of an electronic notary public - a device which can certify information for a group of mutually distrusting parties - among which may be builder of the device.