The difficult part of basing a one-way function around NP-hardness isn't so much the reduction itself as it is the ability to sample from the "hard core" core t

The difficult part of basing a one-way function around NP-hardness isn't so much the reduction itself as it is the ability to sample from the "hard core" core the distribution. For example, say you base the hardness of your OWF on the NP-hard problem of finding a Hamiltonian Cycle in an n-node graph. Your reduction could be completely valid and sound, meaning that pre-imaging your function would require solving an NP-hard problem. But, maybe suprisingly, HamCycle is actually extraordinarily easy for an overwhelming majority of n-node graphs. This is the result of a phase transition that happens when the degree of a random graph passes O(log n) or so, where suddenly the probability of such a graph having a HamCycle becomes 1-o(1) > 0.999999 for n sufficiently large, and a simple greedy algorithm can find them (ref. Pósa '76). And most graphs have average degree closer to n/2 than log(n), meaning that finding a HamCycle is trivial. The crux, finally, is that basing your problem on an overwhelmingly trivial problem, even if technically NP-hard, is still not going to work for security. It will be little consolation that perhaps one customer's account was not broken into when the other hundred million accounts were cracked in milliseconds. A solution to this problem would require researchers to find an NP-hard problem that is hard on average when sampled from an efficiently-sampleable distribution (plus a couple other techcnical caveats). Whether or not there is a good way to do that, for any NP-hard problem, is still mostly a major open question, and not for lack of trying.