Sunday, November 19, 2017

Cryptography course notes

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);
    echo $newCipherText;

Stream cipher with scure PRG is semantically secure - 

No comments:

Blog Archive