Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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?

share|improve this question
add comment

1 Answer

up vote 7 down vote accepted

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).

share|improve this answer
5  
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. –  Brock Hansen Feb 20 at 23:06
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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