Title :
The Shannon cipher system with a guessing wiretapper
Author :
Merhav, Neri ; Arikan, Erdal
Author_Institution :
Dept. of Electr. Eng., Technion-Israel Inst. of Technol., Haifa, Israel
fDate :
9/1/1999 12:00:00 AM
Abstract :
The Shannon theory of cipher systems is combined with recent work on guessing values of random variables. The security of encryption systems is measured in terms of moments of the number of guesses needed for the wiretapper to uncover the plaintext given the cryptogram. While the encrypter aims at maximizing the guessing effort, the wiretapper strives to minimize it, e.g., by ordering guesses according to descending order of posterior probabilities of plaintexts given the cryptogram. For a memoryless plaintext source and a given key rate, a single-letter characterization is given for the highest achievable guessing exponent function, that is, the exponential rate of the pth moment of the number of guesses as a function of the plaintext message length. Moreover, we demonstrate asymptotically optimal strategies for both encryption and guessing, which are universal in the sense of being independent of the statistics of the source. The guessing exponent is then investigated as a function of the key rate and related to the large-deviations guessing performance
Keywords :
cryptography; information theory; probability; random processes; Shannon cipher system; asymptotically optimal strategies; cryptogram; encryption systems security; guessing wiretapper; highest achievable guessing exponent function; key rate; large-deviations guessing performance; memoryless plaintext source; plaintext message length; random variables; Cryptography; Databases; Distortion measurement; Entropy; Internet; Random variables; Security; Statistics; Terminology; Testing;
Journal_Title :
Information Theory, IEEE Transactions on