Completeness (cryptography)

In cryptography, a boolean function is said to be complete if the value of each output bit depends on all input bits.

This is a desirable property to have in an encryption cipher, so that if one bit of the input (plaintext) is changed, every bit of the output (ciphertext) has an average of 50% probability of changing. The easiest way to show why this is good is the following: consider that if we changed our 8-byte plaintext's last byte, it would only have any effect on the 8th byte of the ciphertext. This would mean that if the attacker guessed 256 different plaintext-ciphertext pairs, he would always know the last byte of every 8byte sequence we send (effectively 12.5% of all our data). Finding out 256 plaintext-ciphertext pairs is not hard at all in the internet world, given that standard protocols are used, and standard protocols have standard headers and commands (e.g. "get", "put", "mail from:", etc.) which the attacker can safely guess. On the other hand, if our cipher has this property (and is generally secure in other ways, too), the attacker would need to collect 264 (~1020) plaintext-ciphertext pairs to crack the cipher in this way.

Famous quotes containing the word completeness:

    Poetry presents indivisible wholes of human consciousness, modified and ordered by the stringent requirements of form. Prose, aiming at a definite and concrete goal, generally suppresses everything inessential to its purpose; poetry, existing only to exhibit itself as an aesthetic object, aims only at completeness and perfection of form.
    Richard Harter Fogle, U.S. critic, educator. The Imagery of Keats and Shelley, ch. 1, University of North Carolina Press (1949)