A sender A wants to send N messages xi, i =1,…,N, chosen from a set containing M different possible messages, M >N, to a receiver B. Every xi has to pass through the hands of a dishonest messenger C. Therefore A and B agree on a mathematical transformation f and a secret parameter, or key k, that will be used to produce the authenticator yi=f(xi,k), which is sent together with xi. The key is chosen at random from a set of L elements. C knows f and can find all elements in the set G(xoyd= (k/f(xj,k)= yi) given enough time and computer resources. C wants to change xiinto x’ without B suspecting. This means that C must find the new authenticator y’ = (x‘, k). Since G(xi, yi) can be found for any (xi,yi), it is obvious that C will always succeed unless G(xi,yi) contains more than one element. Here it is proved that the average probability of success for C is minimized if (a) G(xi,yi) contains L(N-1)/N elements and (b) each new known pair (xjyj) will diminish this set of solutions by a factor of L-1/N. The minimum average probability will then be L -1/N. © 1979 IEEE
