Codes Which Detect Deception

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 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">−1</sup> . Several encoding functions Φ(.,.) are given, some of which achieve this bound.