  Starting from a practical use of Reed-Solomon codes in a cryptographic scheme
published in Indocrypt'09, this paper deals with the threshold of linear
$q$-ary error-correcting codes. The security of this scheme is based on the
intractability of polynomial reconstruction when there is too much noise in the
vector. Our approach switches from this paradigm to an Information Theoretical
point of view: is there a class of elements that are so far away from the code
that the list size is always superpolynomial? Or, dually speaking, is
Maximum-Likelihood decoding almost surely impossible?
  We relate this issue to the decoding threshold of a code, and show that when
the minimal distance of the code is high enough, the threshold effect is very
sharp. In a second part, we explicit lower-bounds on the threshold of
Maximum-Distance Separable codes such as Reed-Solomon codes, and compute the
threshold for the toy example that motivates this study.
