2- Perfect and practical secrecy Flashcards
Perfect secrecy
an attacker does not get extra information about ptext from seeing the ctext
1 time pad
a table for keys, ctext and ptext
Properties of 1 time pad
1) #key >= #ptexts
2) key is uniformly selected from the kspace
3) key is used once
Why keys shouldn’t be reused for a 1time pad (3)
attacker may deduce information from the messages encrypted with the same key
Latin square 1time pad properties (3)
1) n rows, n keys
2) n cols, n ptexts
3) n entries with n ctexts
Vernam cipher
P-bit XOR K-bit
Practical security
no known attack can be conducted in a time shorter than cover time
1 time pad limitations
1) key length -> key storage and establishment
2) randomness (deterministic generators)
3) 1-time use of keys
Cover time
Length of time for which info must be secret
Computational complexity from a security viewpoint
1) processes required for an attack
2) how long it takes to conduct these processes
Computational complexity
time needed to run the algorithm for a given length of input
Polynomial time
n^r
Exponential time
a^n
Semantic security
if any probabilistic polynomial time algo - ppta - cannot determine additional info about the ptext from ctext with a higher probability than other pptas
Attack time
process complexity / computer speed (ops/sec)
