Stream Ciphers 4 - What is a secure cipher?
Statistical tests - given an input it will tell how random it is.
Advantage - |Pr(A(PRG) = 1) - Pr(A(R) = 1)| A is statistical test which will return 1 if it thinks input is random enough. Advantage is close to 1 if A can distinguish very well between a truly random number and PRG random number else it's close to 0.
A PRG is secure if ADV_PRG[A,G] is negligible. It means it's difficult to distinguish between PRG and truly random.
Are there provably secure PRGs? We don't know. It's linked to P = NP.
Secure PRGs are unpredictable. Given first i bits if an algo can predict the i+1 bit with prob > 1/2 + epsilon where epsilon is non-neg then PRGs is predictable and Advantage > epsilon.
Theorem => if for all i in (0 to n-1) PRG G is unpredictable at position i then G is secure PRG.
If next bit predictors can't distinguish G from random then no statistical test can.
Semantic Security - if attacker can't distinguish between Exp(0) and Exp(1) - i.e. m0 and m1. Definition similar to advantage.
$cipherText = '6c73d5240a948c86981bc294814d';
$originalText = 'attack at dawn';
$newText = 'attack at dusk';
$otpInAscii = pack('H*',$cipherText) ^ $originalText;
$newCipherText = bin2hex($otpInAscii ^ $newText);
Stream cipher with scure PRG is semantically secure -