The early work on cryptography introduced many surprising feasibility results on secure computation based on very minimal assumptions on the hardness of certain computational problems. The natural goal thereafter is to improve the efficiency and security guarantees of these constructions while maintaining the same minimal assumptions. However, there is a limit to what can be achieved, and it is important to understand the gap between known constructions and fundamental limitations. In this talk, I will present lower bounds on the efficiency of two cryptographic constructions: hardness amplification of one-way functions and construction of statistically hiding commitments from one-way permutations. (Based on joint work with Henry Lin and Luca Trevisan)