What is a minimal worst-case complexity assumption that implies non-trivial average-case hardness of NP or PH? This question is well motivated by the theory of fine-grained average-case complexity and fine-grained cryptography. In this paper, we show that several standard worst-case complexity assumptions are sufficient to imply non-trivial average-case hardness of NP or PH:

1. NTIME[$n$] cannot be solved in quasi-linear time on average if UP is not in DTIME[$2^{\widetilde{O}\left(\sqrt{n}\right)}$].

2. $\Sigma_2$TIME[$n$] cannot be solved in quasi-linear time on average if $\Sigma_k$SAT cannot be solved in time $2^{\widetilde{O}\left(\sqrt{n}\right)}$ for some constant $k$. Previously, it was not known if even average-case hardness of $\Sigma_3$SAT implies the average-case hardness of $\Sigma_2$TIME[$n$].

3. Under the Exponential-Time Hypothesis (ETH), there is no average-case $n^{1+\varepsilon}$-time algorithm for NTIME[$n$] whose running time can be estimated in time $n^{1+\varepsilon}$ for some constant $\varepsilon > 0$.

Our results are given by generalizing the non-black-box worst-case-to-average-case connections presented by Hirahara (STOC 2021) to the settings of fine-grained complexity. To do so, we construct quite efficient complexity-theoretic pseudorandom generators under the assumption that the nondeterministic linear time is easy on average, which may be of independent interest.