Polynomials, Secret Sharing, And Error-Correcting CodesPolynomials in one variable over the realsRepresenting a polynomialAre we working over the reals?The Set Zp for prime pSimple Facts about PolynomialsEvaluating a polynomialThe roots of a polynomialSlide 9A Crucial ImplicationSlide 11Slide 12Lagrange Interpolationk-th “Switch” polynomialSlide 15Adding them togetherThe Lagrange PolynomialExampleSlide 19Two different representationsConverting between the two representationsSome representations are better for some operationsSlide 23And some representations are better for other operationsThe value-representation is tolerant to “erasures”Slide 26Slide 27But is it tolerant to “corruption” ?Error-Detecting RepresentationAlso Error Correcting RepresentationNow for something quite different…Secret SharingA k-out-of-n secret sharing schemeOur k-out-of-n S.S.S.Slide 35Slide 36Slide 37Study BeePolynomials, Secret Sharing, And Error-Correcting CodesGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2005Lecture 14 October 13, 2005 Carnegie Mellon University X3 X2 + + X1 + P(X) =Polynomials in one variable over the realsP(x) = 3 x2 + 7 x – 2Q(x) = x123 – ½ x25 + 19 x3 – 1R(y) = 2y + √2S(z) = z2 – z - 1T(x) = 0 W(x) = πNo Formal Power Seriesthis time, just finite polynomials.Representing a polynomialA degree-d polynomial is represented by its (d+1) coefficients:P(x) = ad xd + ad-1 xd-1 + … + a1 x1 + a0The numbers ad, ad-1, …, a0 are the coefficients.E.g. P(x) = 3x4 – 7x2 + 12x – 19Coefficients are:Are we working over the reals?We could work over any “field”(set with addition, multiplication, division defined.)E.g., we could work with the rationals, or the reals.Or with Zp, the integers mod prime p.In this lecture, we will work with ZpThe Set Zp for prime pZp = {0, 1, 2, …, p-1}Zp* = {1, 2, 3, …, p-1}Simple Facts about PolynomialsLet P(x), Q(x) be two polynomials.The sum P(x)+Q(x) is also a polynomial.(i.e., polynomials are “closed under addition”)Their product P(x)Q(x) is also a polynomial.(“closed under multiplication”)P(x)/Q(x) is not necessarily a polynomial.Evaluating a polynomialSuppose:P(x) = ad xd + ad-1 xd-1 + … + a1 x1 + a0E.g. P(x) = 3x4 – 7x2 + 12x – 19P(5) = 3×54 – 7×52 + 12×5 – 19P(-1) = 3×(-1)4 – 7×(-1)2 + 12×(-1) – 19P(0) = -19The roots of a polynomialSuppose:P(x) = ad xd + ad-1 xd-1 + … + a1 x1 + a0Definition: r is a “root” of P(x) if P(r) = 0E.g., P(x) = 3x + 7 root = -(7/3).P(x) = x2 – 2x + 1 roots = 1, 1P(x) = 3x3 -10x2 + 10x – 2 roots = 1/3, 1, 2.The Single Most Important Fact About Low-degree PolynomialsA non-zero degree-d polynomial P(x) hasat most d roots.A Crucial ImplicationTwo polynomials P(x) and Q(x) of degree at most d.Suppose x1, x2, …, xd+1 are d+1 points such thatP(xk) = Q(xk) for all k = 1,2,…,d+1Then P(x) = Q(x) for all values of x.Proof:If you give me pairs(x1, y1), (x2, y2), …, (xd+1, yd+1)then there is at most onedegree-d polynomial P(x) such thatP(xk) = yk for all kHmm: at most one.So perhaps there are no such degree-d polynomials with P(xk) = yk for all the d+1 values of kLagrange InterpolationGiven any (d+1) pairs (x1, y1), (x2, y2), …, (xd+1, yd+1)then there is exactly onedegree-d polynomial P(x) such thatP(xk) = yk for all kk-th “Switch” polynomialk-th “Switch” polynomialAdding them togetherThe Lagrange PolynomialExampleInput: (0,1), (1,2), (2,9)Switch polynomials h1(x) = (x-1)(x-2)/(0-1)(0-2) = ½ (x-1)(x-2) h2(x) = (x-0)(x-2)/(1-0)(1-2) = x(x-2)/(-1) h3(x) = (x-0)(x-1)/(2-0)(2-1) = ½ x(x-1)P(x) = 1 × h1(x) + 2 × h2(x) + 9 × h3(x)= 3x2 – 2x + 1To recap:If you give me pairs(x1, y1), (x2, y2), …, (xd+1, yd+1)then there is exactly onedegree-d polynomial P(x) such thatP(xk) = yk for all k(And I can find this polynomial P(x)using Lagrange interpolation.)Two different representationsP(x) = ad xd + ad-1 xd-1 + … + a1 x1 + a0can be represented either bya) d+1 coefficientsad, ad-1, …, a2, a1, a0b) Its value at any d+1 pointsP(x1), P(x2), …, P(xd), P(xd+1)(e.g., P(0), P(1), P(2), …, P(d+1).)Converting between the two representationsCoefficients to Evaluation:Evaluation to Coefficients:Some representations are better for some operations Adding two polynomials:P(x) can be represented bya) d+1 coefficientsad, ad-1, …, a2, a1, a0b) Its value at any d+1 pointsP(x1), P(x2), …, P(xd), P(xd+1)(e.g., P(0), P(1), P(2), …, P(d+1).)Some representations are better for some operations Multiplying two polynomials:P(x) can be represented bya) d+1 coefficientsad, ad-1, …, a2, a1, a0b) Its value at any d+1 pointsP(x1), P(x2), …, P(xd), P(xd+1)(e.g., P(0), P(1), P(2), …, P(d+1).)And some representations are better for other operationsEvaluating the polynomial at some other point:P(x) can be represented bya) d+1 coefficientsad, ad-1, …, a2, a1, a0b) Its value at any d+1 pointsP(x1), P(x2), …, P(xd), P(xd+1)(e.g., P(0), P(1), P(2), …, P(d+1).)The value-representation is tolerant to “erasures”I want to send you a polynomial P(x) of degree d.Suppose your mailer drops my emails once in a while.Now hang on a minute!Why would I ever want to send you a polynomial?The value-representation is tolerant to “erasures”I want to send you a polynomial P(x) of degree d.Suppose your mailer drops my emails once in a while.Say, I wanted to send you a message“hello”I could write it as“8 5 12 12 15”and hence as8 x4 + 5 x3 + 12 x2 + 12 x + 15The value-representation is tolerant to “erasures”I want to send you a polynomial P(x) of degree d.Suppose your mailer drops my emails once in a while.I could evaluate P(x) at (say) n > d+1 points and send<k, P(k)> to you for all k = 1, 2,…,d, …,n.As long you get at least (d+1) of these, choose any (d+1) of the ones you got, and reconstruct P(x).But is it tolerant to “corruption” ?I want to send you a polynomial P(x).Suppose your mailer corrupts my emails once in a while.E.g., suppose P(x) = 2x2 + 1, and I chose n = 4. I evaluated P(0) = 1, P(1) = 3, P(2) = 9, P(3) = 19.So I sent you <0,1>, <1, 3>, <2, 9>, <3,19>Corrupted email says <0,1>, <1, 2>, <2, 9>, <3, 19>You choose <0,1>, <1,2>, <2,9>and get Q(x) =Error-Detecting RepresentationThe above scheme does detect errors!If we send the value of degree-d polynomial P(x) at n ≥ d+1 different points, <x1, P(x1)>, <x2, P(x2)>, … , <xn, P(xn)>then we can detect corruptions as long as there fewer
View Full Document
Unlocking...