7
$\begingroup$

Lagrange interpolation seems to be affected by the so-called Runge phenomenon when one tries to interpolate polynomials of high degree from a set of equidistant points.

Lagrange interpolation is used in some secret sharing schemes like Shamir's secret sharing, in which the polynomial being interpolated is not continuous but defined over a finite field.

Does any of you know whether this Runge phenomenon also exists or could also affect the accuracy of the interpolation done in Shamir's secret sharing scheme?

$\endgroup$
10
$\begingroup$

No, the Runge phenomenon is known not to affect Shamir's scheme.

Remember, the point of Shamir's scheme is not actually to form an approximation over an interval; instead, it's to encode a secret in a randomly chosen polynomial, and then divide up clues to that polynomial so that, with enough clues (shares), someone can reconstruct the entire polynomial (and hence recover the secret).

(Now, in practice, we don't bother reconstructing the entire polynomial; instead, we just recover the coefficient that is the secret. However, that's just a detail; we could, if we wanted to, recover the entire polynomial).

So, in terms of accuracy, the question is "do we recover the polynomial with sufficient accuracy so that we can uniquely identify the secret". And, the answer to that is, yes, we can (because computation in Finite Fields are done precisely, with no rounding errors).

$\endgroup$
  • 5
    $\begingroup$ We might note that the polynomial used in Shamir secret sharing is not an approximation to another function. Also, the polynomial is not interpolated. It's defined only on a finite set of arguments (typically integers modulo something) with, as poncho notes, no rounding errors. $\endgroup$ – Brock Hansen Feb 20 '14 at 23:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.