Codes Which Detect Deception

Authors:
  • EGE. N. Gilbert
    E. N. Gilbert
  • FMF. J. MacWilliams
    F. J. MacWilliams
  • NSN. J. A. Sloane
    N. J. A. Sloane
Publisher website
Google Scholar
Abstract
We consider a new kind of coding problem, which has applications in a variety of situations. A message x is to be encoded using a key m to form an encrypted message y = Φ(x, m), which is then supplied to a user G. G knows m and so can calculate x. It is desired to choose Φ(.,.) so as to protect G against B, who knows x, y, and Φ(.,.) (but not m); B may substitute a false message y' for y. It is shown that if the key can take K values, then an optimal strategy for B secures him a probability of an undetected substitution ≪ K −1 . Several encoding functions Φ(.,.) are given, some of which achieve this bound.

This publication has 4 references indexed in Scilit: