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