Impagliazzo and Levin demonstrated [IL90] that the average-case hardness of any NP-search problem under any P-samplable distribution implies that of another NP-search problem under the uniform distribution. For this they developed a way to define a reduction from an NP-search problem F with ``mild hardness'' under any P-samplable distribution H; more specifically, F is a problem with positive hard instances with probability 1/poly(n) under H. In this paper we show a similar reduction for an NP-search problem $F$ with ``strong hardness'', that is, F with positive hard instances with probability 1-1/poly(n) under H in its positive domain (i.e., the set of positive instances). Our reduction defines from this pair of F and H, some NP-search problem $G$ with a similar hardness under the uniform distribution U; more precisely, (i) G has positive hard instances with probability 1-1/poly(n) under U in its positive domain, and (ii) the positive domain itself occupies 1/poly(n) of {0,1}^n.
