11/15/2004 CSC 486 : Hem-Ogi 2.1 Proof… we find a contradiction With the machine M' in hand, we can easily invert f  M' will find one bit of information with each step  Because f is honest, the inverse of f(z) has to be polynomial with respect to z  Therefore, M' will find the inverse of f(z) in polynomial time, bit by bit However, if we can easily invert f, then f can't possibly be one-way f being a one-way function was one of our basic assumptions  CONTRADICTION
{}