Completeness (cryptography)
- 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.
See also
Wikimedia Foundation.
2010.
Look at other dictionaries:
List of computer scientists — Expand list|date=August 2008This is a list of well known computer scientists, people who do work in computer science, in particular researchers and authors.Some persons notable as programmers are included here because they work in research as… … Wikipedia
P versus NP problem — Unsolved problems in computer science Is P = NP ? … Wikipedia
EPR paradox — In quantum mechanics, the EPR paradox is a thought experiment which challenged long held ideas about the relation between the observed values of physical quantities and the values that can be accounted for by a physical theory. EPR stands for… … Wikipedia
Non-interactive zero-knowledge proof — Non interactive zero knowledge proofs are a variant of zero knowledge proofs. Blum, Feldman, and Micali [1] showed that a common reference string shared between the prover and the verifier is enough to achieve computational zero knowledge without … Wikipedia
Probabilistically checkable proof — In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm… … Wikipedia
Knapsack problem — BKP redirects here. For other uses, see BKP (disambiguation). Example of a one dimensional (constraint) knapsack problem: which boxes should be chosen to maximize the amount of money while still keeping the overall weight under or equal to… … Wikipedia
Oded Goldreich — Born 1957 Tel Aviv, Israel … Wikipedia
Discrete mathematics — For the mathematics journal, see Discrete Mathematics (journal). Graphs like this are among the objects studied by discrete mathematics, for their interesting mathematical properties, their usefulness as models of real world problems, and their… … Wikipedia
Quadratic residue — In number theory, an integer q is called a quadratic residue modulo n if it is congruent to a perfect square modulo n; i.e., if there exists an integer x such that: Otherwise, q is called a quadratic nonresidue modulo n. Originally an abstract… … Wikipedia
Algorithm — Flow chart of an algorithm (Euclid s algorithm) for calculating the greatest common divisor (g.c.d.) of two numbers a and b in locations named A and B. The algorithm proceeds by successive subtractions in two loops: IF the test B ≤ A yields yes… … Wikipedia
