Cryptography course notes

https://www.coursera.org/learn/crypto

Stream Ciphers 4 - What is a secure cipher?

PRG Security Definitions - 

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.

Quiz

<?php 

    $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 -