Please enable JavaScript.

Coggle requires JavaScript to display documents.

Cryptography (Homeworks (PRF Proof (How to proof that F' is a PRF or…

- - - - (Expansion:) For every n it holds that l(n) > n)
        
        (Pseudorandomness:) For any PPT alg. D, there is a negl such that
        |Pr [ D (G(S) ) = 1 ] - Pr [D(r) = 1 ] | <= negl(n),
        where the first prob. is taken over unif choice of s in {0, 1}^n and the randomness of D, and the second prob. is taken over unif choice of r in {0, 1}^l(n) and the randomness of D.
      - We call l the expansion factor of G.
      - Usage: Just find a good distinguisher D that can distinct the PG output from the uniform output with the same length in some way.
      - By Kerckhoffs' principle we can use brutal forth to break the PRG too, since D knows the specification of G by that theorem.
      - Setting a seed for PRG is just like setting a password, and you need to keep it secret from anyone else too.
    - - Secure (in the basic sense): if it takes no IV and for any polynomial l with l(n) > n, the function G_l constructed above is a pseudorandom generator with expansion factor l.
      - Proof by Reduction: conclusion: cannot distinct output of G from a uniform string => attacker cannot "break" the encryption scheme.
    - - |K| < |M|
        
        Pseudo-random one-time pad
        
        Gen: The same a a normal Gen that take 1^n unary input and output key: {0, 1}^n
        
        Enc: Given that we have access to any PRG G, and using G(k) to get the Pseudo-One-time Pad with length = l(n) where l is the expansion factor for G. XOR
        
        Dec: similar with G(k) to be the POP and XOR cipher text to get the message.
  - - - If Π is a (stateless4) encryption scheme in which Enc is a deterministic function of the key and the message, then Π cannot have indistinguishable multiple encryptions in the presence of an eavesdropper.
    - - Any private-key encryption scheme that is CPA-secure is also CPA-secure for multiple encryptions.