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.
[No spaces and no dashes.]
Login ID :
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., ci = P(i)
mod q). Then, the sender will append a fingerprint of ci to
the end of each packet, so that the i-th packet consists of
the triple (ci, F(ci,r), r).
The receiver will check, for each received packet (ci,
fi, r), that fi is a valid fingerprint of
ci. 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).