One way functions and pseudorandomness

Question 1

Invert experiment

Question 2

Definition of one way function

Question 3

One way function from the factoring assumption

Question 4

Definition of function/permutation family

Question 5

Invert experiment for a function family

Question 6

Definition of one way function family

Question 7

One way function family from the Factoring Assumption

Question 8

One way permutation family from the RSA assumption

Question 9

One way permutation family from the DL assumption

Question 10

Definition of hard core predicate and Goldreich Levin theorem and Universal one way function theorem

Question 11

Definition of hash function

Question 12

Definition of collision, experiment about collision and definition of collision resistant hash function

Question 13

Collision resistant hash function from DL: construction and proof or resistance

Question 14

Theorem about collision resistance of Hash function from DL and proof

Question 15

Lemmas about collision resistance and one wayness and proofs

Question 16

Definition of pseudo random generators

Question 17

PRG with minimal expansion factor

Question 18

PRG with arbitrary polynomial expansion

Question 19

PRG from one way permutations and functions

Question 20

Theorem: one way functions from PRG

Question 21

Second preimage resistance and preimage resistance + implications

Question 22

Exercise 2.
Let (Gen, H) be a collision-resistant hash function. Is (Gen, Hˆ ) defined by
Hˆ (k, x) = H(k, H(k, x)) necessarily collision-resistant?