Is the polynomial reconstruction problem really "intractable"? In the family of the believed (experts haven't come yet with a solution) intractable problems in cryptography belongs the  Polynomial Reconstruction problem in which an attacker is given $n$ points in which at least $t$ belong to the evaluation of a polynomial $p$ of degree $k$ and the attacker wishes to reconstruct $p$. (where $n&gt;t&gt;k$) The problem has been the basing building block for crypto primitives as public key encryption, block cipher, and oblivious polynomial evaluation. 

The reduction for the security proof comes from decoding random reed-solomon codes. My question is the following: Why this is treated as an intractable problem as a very naive idea is to reconstruct the polynomial $p$ by simple Lagrange interpolation after picking up all the ${t} \choose{n}$ elements ?
The polynomial $p$ of degree $k$ can be reconstructed if at least $k+1$ correct points 
are known (that is, we know that $(x_i,y_i), 0 \leq i \leq k$ are correct meaning that
$y_i = p(x_i), 0 \leq i \leq k$), and in this
case, Lagrangian interpolation works. If the points are being made available one at
a time instead of all at once, Newtonian interpolation is an even better method for
on-line interpolation.

If an adversary finds out $n$ points of which at least $t &gt; k$
points are correct (though the adversary does not know which
$t$ points are correct), then the adversary can use Reed-Solomon
decoding techniques to determine
$p$ as long as $t \geq \frac{n-(k+1)}{2}$, that is, among the
$n-(k+1)$ "extra points", there are
at least as many correct points as there are incorrect points.
The Reed-Solomon decoding process will also tell the adversary
which of the points are incorrect. Note that the adversary 
knows the values of $k$ and $n$ but not necessarily the value
of $t$ but can still use the Reed-Solomon decoding process,
and this process is guaranteed to find $p$ (as well as $t$)
and to identify the incorrect points as long as there are
at least as many correct extra points as incorrect points.

What happens when there are fewer correct extra points than incorrect points?
Well, the adversary does not know this and can launch the
Reed-Solomon decoding process but the process will recover $p$
only in extraordinarily rare circumstances. The process will
find some polynomial $\hat{p}$ but the adversary can readily
determine that this is not the right answer by checking whether
$\hat{p}(x_i)$ equals $y_i$ for most of the points (as it should
for the correct $p$).