Arguments for existence of one-way functions I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-way functions?
Here's an argument that one-way functions should be hard to invert. Suppose there is a class of 3-SAT problems with planted solutions that are hard to solve. Consider the following map:

$$(x, r) \rightarrow s$$

where $x$ is any string of bits, $r$ is a string of bits (you could use these to seed a random number generator, or you can ask for as many random bits as you need) and $s$ is a $k$-SAT problem having $x$ as a planted solution, where the random number generator determines exactly which $k$-SAT problem you choose. To invert this one-way function, you need to solve a $k$-SAT problem with a planted solution. 

This argument shows that inverting a one-way function is as hard as solving $k$-SAT problems with planted solutions. And since $k$-SAT is an NP-complete problem, if you can figure out how to construct hard instances with planted solutions for any NP problem, you can plant solutions in $k$-SAT formulas. 

It has not been proven that it's possible to come up with a class of NP-complete problems with planted solutions that are just as hard as arbitrary NP-complete problems (and even if this is true, it's going to be incredibly hard to prove), but people definitely know how to plant solutions in $k$-SAT problems in ways that nobody currently knows how to solve. 

ADDED: I now realize that this connection was already given (in more detail) in Abadi, Allender, Broder, Feigenbaum, and Hemachandra; they point out that one-way functions can give solved hard instances of SAT, and vice versa.

Putting it in more informal language, the non-existence of one-way functions shows that truly hard puzzles can't exist. If there is a type of puzzle where somebody can come up with both a puzzle and its solution algorithmically, then there is also a polynomial-time algorithm for finding a solution to the puzzle. This seems very counter-intuitive to me. Of course, a polynomial gap could exist; it might be the case that if creating the puzzle took $n$ steps, then solving it might take $O(n^3)$ steps. However, my intuition says that there should be a superpolynomial gap.