motivation is the following. Alice may have some data that she wants to

“back up” on some ¬le servers, who play the role of the parties P1 , . . . , Pm .

18.4 Computing modular inverses and Chinese remaindering 409

To do this, Alice gives each server a share of her secret data (if she has a

lot of data, she can break it up into many small blocks, and process each

block separately). If at a later time, Alice wants to restore her data, she

contacts any k servers who will give Alice their shares, from which Alice

can reconstruct the original data. In using a secret sharing scheme in this

way, Alice trusts that the servers are reliable to the extent that they do

not modify the value of their shares (as otherwise, this would cause Alice to

reconstruct the wrong data). We shall discuss later in this chapter how one

can relax this trust assumption. But even with this trust assumption, Alice

does gain something above and beyond the simpler solution of just backing

up her data on a single server, namely:

• even if some of the servers crash, or are otherwise unreachable, she

can still recover her data, as long as at least k are available at the

time she wants to do the recovery;

• even if the data on some (but strictly less than k) of the servers is

“leaked” to some outside attacker, the attacker gains no information

about Alice™s data.

Exercise 18.8. Suppose that Alice shares secrets s1 , . . . , st ∈ F with parties

P1 , . . . , Pm , so that each Pi has one share of each sj . At a later time,

Alice obtains all the shares held by k of the parties. Show how Alice can

reconstruct all of the secrets s1 , . . . , st using O(k 2 + tk) operations in F .

Exercise 18.9. Suppose that Alice shares secrets s1 , . . . , st ∈ F with parties

P1 , . . . , Pm , so that each Pi has one share of each sj . Moreover, Alice does

not want to trust that the parties do not maliciously (or accidentally) modify

their shares. Show that if Alice has a small amount of secure storage, namely,

space for O(m) elements of F that cannot be read or modi¬ed by the other

parties, then she can e¬ectively protect herself from malicious parties, so

that if any particular party tries to give her modi¬ed shares, Alice will

fail to detect this with probability at most t/|F |. If |F | is very large (say,

|F | = 2128 ), and t is any realistic value (say, t ¤ 240 ), this failure probability

will be acceptably small for all practical purposes. Hint: see Exercise 9.12.

18.4.3 Speeding up algorithms via modular computation

In §4.4, we discussed how the Chinese remainder theorem could be used to

speed up certain types of computations involving integers. The example we

gave was the multiplication of integer matrices. We can use the same idea to

speed up certain types of computations involving polynomials. For example,

410 Polynomial arithmetic and applications

if one wants to multiply two matrices whose entries are elements of F [X], one

can use the Chinese remainder theorem for polynomials to speed things up.

This strategy is most easily implemented if F is su¬ciently large, so that we

can use polynomial evaluation and interpolation directly, and do not have

to worry about constructing irreducible polynomials. We leave the details

as an exercise.

Exercise 18.10. You are give two matrices A, B ∈ F [X] — . All entries of

A and B are polynomials of degree at most M . Assume that |F | ≥ 2M + 1.

Using polynomial evaluation and interpolation, show how to compute the

product matrix C = A · B using O( 2 M 2 + 3 M ) operations in F . Compare

this to the cost of computing C directly, which would be O( 3 M 2 ).

18.5 Rational function reconstruction and applications

We next state and prove the polynomial analog of Theorem 4.6. As we are

now “reconstituting” a rational function, rather than a rational number,

we call this procedure rational function reconstruction. Because of

the relative simplicity of polynomials compared to integers, the rational

reconstruction theorem for polynomials is a bit “sharper” than the rational

reconstruction theorem for integers. Throughout this section, F denotes a

¬eld.

Theorem 18.7. Let r— , t— be non-negative integers, and let n, y ∈ F [X] be

polynomials such that r— + t— ¤ deg(n) and deg(y) < deg(n). Suppose we

run the extended Euclidean algorithm with inputs a := n and b := y. Then,

adopting the notation of Theorem 18.4, the following hold:

(i) There exists a unique index i = 1, . . . , + 1, such that deg(ri ) < r— ¤

deg(ri’1 ), and for this i, we have ti = 0.

Let r := ri , s := si , and t := ti .

(ii) Furthermore, for any polynomials r, s, t ∈ F [X] such that

r = sn + ty, deg(r) < r— , 0 ¤ deg(t) ¤ t— , (18.1)

we have

r = r ±, s = s ±, t = t ±,

for some non-zero polynomial ± ∈ F [X].

Proof. By hypothesis, 0 ¤ r— ¤ deg(n) = deg(r0 ). Moreover, since

= ’∞

deg(r0 ), . . . , deg(r ), deg(r +1 )

18.5 Rational function reconstruction and applications 411

is a decreasing sequence, and ti = 0 for i = 1, . . . , + 1, the ¬rst statement

of the theorem is clear.

Now let i be de¬ned as in the ¬rst statement of the theorem. Also, let

r, s, t be as in (18.1).

From part (iv) of Theorem 18.4 and the inequality r— ¤ deg(ri’1 ), we

have

deg(ti ) = deg(n) ’ deg(ri’1 ) ¤ deg(n) ’ r— .

From the equalities ri = si n + ti y and r = sn + ty, we have the two congru-

ences:

r ≡ ty (mod n),

ri ≡ ti y (mod n).

Subtracting ti times the ¬rst from t times the second, we obtain

rti ≡ ri t (mod n).

This says that n divides rti ’ri t; however, using the bounds deg(r) < r— and

deg(ti ) ¤ deg(n) ’ r— , we see that deg(rti ) < deg(n), and using the bounds

deg(ri ) < r— , deg(t) ¤ t— , and r— + t— ¤ deg(n), we see that deg(ri t) <

deg(n); it immediately follows that

deg(rti ’ ri t) < deg(n).

Since n divides rti ’ ri t and deg(rti ’ ri t) < deg(n), the only possibility is

that

rti ’ ri t = 0.

The rest of the proof runs exactly the same as the corresponding part of

the proof of Theorem 4.6, as the reader may easily verify. 2

18.5.1 Application: polynomial interpolation with errors

We now discuss the polynomial analog of the application in §4.5.1.

If we “encode” a polynomial z ∈ F [X], with deg(z) < k, as the sequence

(a1 , . . . , ak ) ∈ F —k , where ai = z(bi ), then we can e¬ciently recover z from

this encoding, using an algorithm for polynomial interpolation. Here, of

course, the bi are distinct elements of F , and F is a ¬nite ¬eld (which must

have at least k elements, of course).

Now suppose that Alice encodes z as (a1 , . . . , ak ), and sends this encoding

to Bob, but that some, say at most , of the ai may be corrupted during

transmission. Let (˜1 , . . . , ak ) denote the vector actually received by Bob.

a ˜

412 Polynomial arithmetic and applications

Here is how we can use Theorem 18.7 to recover the original value of z

from (˜1 , . . . , ak ), assuming:

a ˜

• the original polynomial z has degree less than k ,

• at most errors occur in transmission, and

• k ≥2 +k.

Let us set ni := (X ’ bi ) for i = 1, . . . , k, and n := n1 · · · nk . Now, suppose

Bob obtains the corrupted encoding (˜1 , . . . , ak ). Here is what Bob does to

a ˜

recover z:

1. Interpolate, obtaining a polynomial y, with deg(y) < k and y(bi ) = ai

˜

for i = 1, . . . , k.

2. Run the extended Euclidean algorithm on a := n and b := y, and let

r , t be the values obtained from Theorem 18.7 applied with r— :=

k + and t— := .

3. If t | r , output r /t ; otherwise, output “error.”

We claim that the above procedure outputs z, under the assumptions

listed above. To see this, let t be the product of the ni for those values of i

where an error occurred. Now, assuming at most errors occurred, we have

deg(t) ¤ . Also, let r := tz, and note that deg(r) < k + . We claim that

r ≡ ty (mod n). (18.2)

To show that (18.2) holds, it su¬ces to show that

tz ≡ ty (mod ni ) (18.3)

for all i = 1, . . . , k. To show this, consider ¬rst an index i at which no

error occurred, so that ai = ai . Then tz ≡ tai (mod ni ) and ty ≡ t˜i ≡

˜ a