ERRATA FOR "On Basing One-Way Functions on NP-Hardness" [AGGM] [We refer to the version dated Feb 28 (2006), which is the basis for our STOC'06 extended abstract.] There is a gap in the proof of our results regarding adaptive reductions, and we currently do not know whether THM 3 (as stated in Sec 2) holds. The source of trouble is the implicit assumption that the expected size of $$T_i^{(k)} = f^{-1}(y_i^{(k)}) \cap h_{k,i,\ell_i^{(k)}}(0^{\ell_i^{(k)}})$$ is $2^{\ell_i^{(k)}}\cdot|f^{-1}(y_i^{(k)})|$ (cf., also Eq (2)). This would have been true if $y_i^{(k)}$ is fixed independently of $h_{k,i,\ell_i^{(k)}}$ (or, in other words, if $h_{k,i,\ell_i^{(k)}}$ is uniformly distributed given $y_i^{(k)}$). Indeed, $y_i^{(k)}$ is fixed if the prover did not cheat in prior rounds of copy $k$ (i.e., $A_j^{(k)} = T_j^{(k)}$ for every $j < i$). However, if such a cheating occurs with respect to copy $k$ in round $j