Crypto Flashcards
What is a symmetric encryption system?
One in which two parties share a private key
What is correctness, in the context of a cipher?
D(k, E(k, m)) = m
That is, the decryption of an encryption must be the original message for every message and key.
What defines perfect secrecy?
If for any two messages, it is impossible to distinguish between the two just by looking at their ciphertexts.
In other words, for any two messages m1 and m2 and their corresponding ciphertexts c1 and c2, it is impossible for an algorithm to determine which ciphertext corresponds to which message.
Said yet another way, the probability that an arbitrary ciphertext is the encryption of a message must be uniform.
Finally, there is no information leaked about the plaintext by the ciphertext.
What is the downside of the One-Time Pad?
The key must be as long as the message, and, if you have a way to securely transmit something that long, just securely transmit the message.
What is a Stream Cipher?
A cipher which encrypts one bit at a time.
These use their key as a seed for a generator in order to create a much larger, pseudorandom key, which is then used to encrypt the original message. In this way, they are a more practical (but less secure) form of the One-Time Pad.
What does it mean for a Pseudo-Random Generator to be predictable?
There is an algorithm A and a position i such that if we generate a random value using the generator, the probability that the algorithm can predict the next bit, given the first i bits, is non-negligibly greater than 1/2.
One common cutoff for negligibility is 1/2^30.
Put more simply, a PRG is predictable if the algorithm can ever guess the next value that is generated reliably.
Why is it bad to use the same One-Time Pad key twice?
It’s insecure.
c1 = m1 XOR k c2 = m2 XOR k
c1 XOR c2 = m1 XOR m2
This leaks information about the plaintext.
What does a One-Time Pad fail to guarantee?
Data integrity – messages encrypted with the OTP are still malleable.
For example, say an adversary intercepts the encrypted message m XOR k.
Although they cannot decipher its contents, they can change them by XORing them with another value, p.
They then send the new message, m XOR k XOR p, to the original target, who decrypts it and receives m XOR p, not simply m.
What is a nonce?
A value that has a very low probability of repeating (e.g. system clock, atmospheric data).
With a nonce r, it becomes possible to reuse a key so long as the pair (k, r) never repeats.
What is advantage, in the context of generators?
The ability of an algorithm to distinguish between the generator’s output and truly random output.
An advantage close to 1 means that the algorithm was readily able to differentiate between the two’s output; a value close to 0 indicates it was significantly harder. Any non-negligible value is bad.
What does it mean for a PRG to be secure?
The advantage of every efficient algorithm is negligible.
Note that the definition is unsatisfiable if we fail to restrict ourselves to “efficient” adversaries.
What is Yao’s Theorem?
A secure PRG is unpredictable; an unpredictable PRG is secure.
What does it mean for two distributions to be computationally indistinguishable?
The advantage of every efficient statistical test is negligible. In other words, the two cannot be differentiated between in polynomial time.
What does it mean for a cipher to be semantically secure?
The advantage of every efficient algorithm against the encryption function is negligible.
Note that this is Shannon’s definition of perfect secrecy, but restricted to efficient algorithms to set realistic expectations.
What is a Block Cipher?
A cipher which takes an n-bit message and creates an n-bit ciphertext.
By expanding the key, it is able to be used for multiple rounds of encryption.
