cleverly constructing permutations y that isolate bits in x. In fact, for a constant fraction of x, there exists a polynomial time algorithm that lists O(1/&epsilon2) candidates that include all valid x. Thus, an algorithm can invert ƒ(x) in polynomial time for a non-negligible fraction of x, which contradicts the hypothesis. References W. Diffie, M.E. Hellman. "New Directions in Cryptography." IEEE Transactions on Information Theory, IT-22, pp. 644–654, 1976. A.C. Yao. "Theory and Application of Trapdoor Functions." 23rd IEEE Symposium on Foundations of Computer Science, pp. 80–91, 1982. M. Blum and S. Micali "How to Generate Cryptographically Strong Sequences of Pseudo-Random Bits." SIAM Journal on Computing, v13, pp. 850–864, 1984. J. Hastad, R. Impagliazzo, L.A. Levin and M. Luby. "A Pseudorandom Generator from any One-way Function." SIAM Journal on Computing, v28 n4, pp.-1364-1396, 1999. Pseudorandomness Theorems in computational complexity theory