Codes Which Detect Deception

The gambling casino has often supplied a vivid and concrete setting for problems in probability theory, 1 stochastic processes,2 hypothesis testing, 3 information theory, 4 and coding theory, 6 and we shall use it to describe our problem. There are two main participants, the owner of the casino G (standing for good guy) and the manager B (the bad guy). B has been reporting the daily takings from the slot machines to be less than they actually arc and keeping the difference for himself. To prevent this, G proposes to install in each slot machine a key generator of which he possesses an exact duplicate and an encoder which will encrypt the 405 day's takings x using a key m to produce an encrypted message y = m). (1) (See Figs. 1 and 2.) The device will punch y onto a paper tape. At suitable intervals B will mail the tape to G, who will calculate x from y and m. From time to time G will visit the casino to change the key generator. We assume that B knows x and $(·,·) (but cannot change them), and y (which he can change), but does not know m. G knows y, m, and $(·,·)· If B attempts to give G a false message y'0) there may be no x' satisfying y,, = $(x', m), and then G will discover B's deception. But if B can solve (1) for m, then he can successfully substitute a false message x' by giving G the correctly encrypted message y' = , m). The problem is to design $(·,·) so as to make it as difficult as possible for B to deceive G without being caught. Clearly, the problem is applicable to other situations (vending machines, cash registers, etc.) and in fact was first presented to us by G.