Introduction to Cryptography

For every string s, let S be the string formed by taking the bitwise complement of the string s. For example 101 010 and 0010 1101. Suppose that G is a cryptographically secure psuedorandom number generator (PRG) with expansion factor I (lambda). Which amongst the following functions are cryptographically secure psuedorandom number generators? Either find a successful test, or prove security from the security of G. I put the security proof of the first as an example. tyfom the secuit (ambda) whics (a) G1(s) G(s) for every string s. Solution: G1 is secure: If G1 were not secure then there would be an algorithm A that given the first i bits of output of G1 predicts the i +1-st bit with non-negligible probability. Now, we can turn A breaking the security of G1 into a prediction algorithm B for G. The new algorithm B, when given the first bits of G, complements them, runs A on the complemented bits, and outputs the complement of the output of A. If A predicts the i+1-st bit with non-negligible probability, then B also predicts the i+ 1-st bit with non-negligible probability because the advantage of B is exactly. the same as the advantage of A. Since such B cannot exist as we assumed G was cryptographically secure, no such A can exist either, and so G1 is also cryptographically secure. (b) G2(s) G(S) for every string s c) G3(s) G(s)G (s) (concatenation of G(s) and G(s)) for every string s (d) G4(s)-res(G(s)) where res(G(s)) is the string obtained from the bitstring G(s) by removing the first and last digits of the bitstring G(s). For every string s, let S be the string formed by taking the bitwise complement of the string s. For example 101 010 and 0010 1101. Suppose that G is a cryptographically secure psuedorandom number generator (PRG) with expansion factor I (lambda). Which amongst the following functions are cryptographically secure psuedorandom number generators? Either find a successful test, or prove security from the security of G. I put the security proof of the first as an example. tyfom the secuit (ambda) whics (a) G1(s) G(s) for every string s. Solution: G1 is secure: If G1 were not secure then there would be an algorithm A that given the first i bits of output of G1 predicts the i +1-st bit with non-negligible probability. Now, we can turn A breaking the security of G1 into a prediction algorithm B for G. The new algorithm B, when given the first bits of G, complements them, runs A on the complemented bits, and outputs the complement of the output of A. If A predicts the i+1-st bit with non-negligible probability, then B also predicts the i+ 1-st bit with non-negligible probability because the advantage of B is exactly. the same as the advantage of A. Since such B cannot exist as we assumed G was cryptographically secure, no such A can exist either, and so G1 is also cryptographically secure. (b) G2(s) G(S) for every string s c) G3(s) G(s)G (s) (concatenation of G(s) and G(s)) for every string s (d) G4(s)-res(G(s)) where res(G(s)) is the string obtained from the bitstring G(s) by removing the first and last digits of the bitstring G(s)