A main tool: Pseudorandom functions [GrGwMi]

A function family {fk}k in {0,1}* where fk:{0,1}*_{0,1}* is pseudo-random if any polytime oracle machine has only negligible advantage in telling whether its oracle is a random function or fk for random k:

For all polytime A, A _ A

A function family {fk}k in {0,1}* where fk:{0,1}*_{0,1}* is pseudo-random if any polytime oracle machine has only negligible advantage in telling whether its oracle is a random function or fk for random k: