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_2TIME[n] cannot be solved in quasi-linear time on average if \Sigma_kSAT 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_3SAT implies the average-case hardness of \Sigma_2TIME[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.