Please fill out this quiz, and press the "Submit" button at the end. Don't collaborate with anyone on quiz exercise solutions.

Please answer all questions.

SID: [No spaces and no dashes.]

Login ID :

1. Alice proposes the following method for sending a polynomial P(x) of degree ≤ n-1 over an unreliable channel, where up to k packets could be corrupted arbitrarily. She proposes that the sender should compute n+k encoded values using the standard erasure coding scheme we saw in class (i.e., c_{i} = P(i) mod q). Then, the sender will append a fingerprint of c_{i} to the end of each packet, so that the i-th packet consists of the triple (c_{i}, F(c_{i},r), r). The receiver will check, for each received packet (c_{i}, f_{i}, r), that f_{i} is a valid fingerprint of c_{i}. The receiver discards every packet where the fingerprint is invalid (treating those packets as "lost"), and then applies the standard method we saw in class on Wednesday for decoding the erasure code (namely, Lagrange interpolation on the packets that remain).

Explain why this scheme isn't guaranteed to work, even if we're guaranteed that no more than k out of the n+k packets sent will be corrupted (i.e., even if we're guaranteed that at least n out of the n+k packets will be received correctly).