Repeated use of codes which detect deception (Corresp.)
Viiveke Fåk · IEEE Transactions on Information Theory · 1979
A senderAwants to sendNmessagesx_{i} = 1 , \ldots ,N, chosen from a set containingMdifferent possible messages,M > N, to a receiverB. Everyx_{i}has to pass through the hands of a dishonest messengerC. ThereforeAandBagree on a mathematical transformationfand a secret parameter, or keyk, that will be used to produce the authenticatory_{i} = f(x_{i} , k ), which is sent together withx. The key is chosen at random from a set ofLelements.Cknowsfand can find all elements in the setG(x_{i},y_{i}) = \{k|f(x_{i}, k) = y_{i}\}given enough time and computer resources.Cwants to changex_{i} \into x^{\prime}withoutBsuspecting. This means thatCmust find the new anthenticatory^{\prime} = f(x^{\prime} , k). SinceG(x_{i},y_{i})can be found for any(x_{i},y_{i}), it is obvious thatCwill always succeed unlessG(x_{i},y_{i})contains more than one element. Here it is proved that the average probability of success forCis minimized if (a)G(x_{i}, y_{i})containsL^{(N-1)/N}elements and (b) each new known pair(x_{j}, y_{j})will diminish this set of solutions by a factor ofL^{-l/N}. The minimum average probability will then beL^{-l/N}.