Usage of Zero-knowledge proofs for NP-complete languages
If one-way functions exist, then there is a distribution over graphs (or SAT formulas, or ...) having the property you're asking for.  In short, just put the OWF through the Cook-Levin reduction.

In a little more detail, Cook-Levin transforms the NP witness-finding question "what is a preimage of $y = f(x)$?" (for random unknown $x$) into the NP witness-finding question "what is a 3-coloring of this graph $G$?", by converting $y$ into a graph $G$ such that any 3-coloring of $G$ can be efficiently converted back to a preimage of $y$ under $f$.