Authentication schemes, perfect local randomizers, perfect secrecy and secret sharing schemes (Q1910425): Difference between revisions

Shannon showed in his classic theory that if a cipher system provides perfect secrecy the number of keys is greater than the number of messages. In the 1980's Simmons developed the theory of authentication, relating the size of the key space to the probability of deception. In 1990 \textit{M. Walker} [J. Cryptology 2, No. 3, 131-143 (1990; Zbl 0705.94008)] gave information-theoretic bounds relating the entropy of the key space to the probability of deception for cartesian authentication schemes. This paper shows how to apply Walker's result to other cryptographic concepts such as perfect local randomness in pseudo-random sequences, perfect secrecy against known plaintext attacks on block ciphers, and secret sharing schemes. When Walker's bounds are met, the probability of success of an eavesdropper or spoofer is reduced to guessing the key stream or the authentic encoded messages. Applying bounds of Walker on authentication schemes, a bound on the number of keys required of a block cipher providing perfect secrecy against known plaintext attacks is given. Finally, a relationship between secret sharing schemes and authentication schemes is established.