CS 70 Discrete Mathematics for CS

Fall 2004  Rao  Problem 11

Solution to Problem 11

11. Applications of Polynomials

(a) Let \overline{a_{1}a_{2}a_{3}...a_{b}} be the secret, where a_{i} are bits and \overline{a_{1}...a_{b}} denotes the number represented by the bit-string. Using Lagrange interpolation we find a polynomial on GF (p) of degree k − 1 for which:

P(1) = \overline{a_{1}a_{2}...a_{⌈b/k⌉}}
P(2) = \overline{a_{⌈b/k⌉+1} ...a_{2⌈b/k⌉}}
... = ...
P(k) = \overline{a_{(k−1)⌈b/k⌉+1} ...a_{b}}

Then we give P(k + i) to person i for i = 1,2,...n. If any k people get together they can reconstruct the polynomial and the whole secret, since k points completely determine a polynomial of degree k − 1. Any k − 1 people won’t be able to reconstruct any chunk of the secret, and in particular the first ⌈b/k⌉ bits. This is true because for any value of the first ⌈b/k⌉ bits c_{1},c_{2},...c_{⌈b/k⌉} there exists a polynomial Q with Q(1) = \overline{c_{1}c_{2}...c_{⌈b/k⌉}} and the k − 1 values of the present people. The size of the field p has to be such that most of its elements are written using ⌈b/k⌉ bits. So choose a prime p such that 2^{⌈b/k⌉−1} < p < 2^{⌈b/k⌉}.

(b) To correct k errors using an n − 1 degree polynomial, it suffices to send n + 2k points. One way to decode is to try all combinations of k errors, and check if there is a degree n − 1 polynomial that matches the remaining n + k of the points. To prove that we’ll never go wrong (assuming there are in fact only ≤ k error), suppose there are two different polynomials that work. Then they agree on n + k points with the original set, and therefore they overlap on at least n points. Since they are degree n − 1 that would make them identical. In the next part we show that n + 2k points are the best we can do.

(c) i. First we look at the possible messages before any errors occur.

Suppose we increase the message by c, so the message consists of n+c elements of the field. The field is of size f (for GF (p) the size of the field is f = p). Therefore one may think that there are f^{n+c} messages that can be sent. However since the message is generated using a degree n − 1 polynomial, and there are only f^{n} such polynomials (think of the possible values of the coefficients), in fact there are only f^{n} legal messages.

ii. Next we look at the possible events in the channel. The channel introduces k errors, and it can choose any k locations for them. There are \binom{n+c}{k} such possibilities (\binom{a}{b} = \frac{a!}{b!(a−b)!} is the number of ways to choose b objects out of a set of a objects). Each error consists of changing the value to some other element of the field, so the channel has f choices. The channel gets to do this for every of the k errors, so overall the number of actions the channel can take is \binom{n+c}{k}f^{k}.

iii. If we received the corrupted message and are able to recover the original, we can recover

both the polynomial and the action of the channel. iv. If we are able to decode, we can recover all this information - the polynomial and the action

of the channel. So the message we received must have been long enough to carry this information. Notice that a message that tells us which of N things happened has to be at least logN bits long (this is a basic fact of information theory, that takes half a minute of thought). In our case, since the message told us which of f^{n}\binom{n+c}{k}f^{k} things happened it must have been at least log(f^{n}\binom{n+c}{k}f^{k}) bits long.

log(f^{n}\binom{n + c}{k} f^{k}) = (n + k)logf + log\binom{n + c}{k}
≈ (n + k)logf + logn^{k}
= (n + k)logf + klogn
≈ (n + k)logf + klogf
≈ (n + 2k)logf

Which is exactly how long a message of n + 2k elements of the field is.