1. If the i-th packet is corrupted, the packet (c_i, f_i, r) might be
replaced by some other triple (c'_i, f'_i, r) such that f'_i is a valid
fingerprint on c'_i (i.e., F(c'_i,r) = f'_i).  If it just so happens
that the i-th packet is corrupted in this way, then everything will be
all messed up: the recipient will think that he has received c'_i
correctly (even though it is actually erroneous) and use it in his
polynomial interpolation.  If you include one erroneous point in the
input to the polynomial interpolation, the polynomial you get out will
be all messed up.

Alternative answer: The i-th packet might just happen to be corrupted
from (c_i, f_i, r) into (c'_i, f_i, r) where it just so happens that
f_i is a valid fingerprint on c'_i, i.e., F(c_i,r) = F(c'_i,r).  That
screws everything up, as described above.

Alternative answer: The i-th packet might just happen to be corrupted
from (c_i, f_i, r) into (c'_i, f'_i, r') where all three values appear
(to the recipient) to be consistent, i.e., F(c'_i,r') = f'_i, and then
the recipient is hosed.

Alternative answer: There is a very small chance (say, a probability
of 1/2^100) that the fingerprint fails to detect an error in c_i.
  Comment: In fact, it's worse than that: if someone is tampering
  maliciously with the data that's being sent, they can guarantee
  that their modification will be undetected, no matter what value
  of r the sender chooses.  This is because the sender has to choose
  r first; then the malicious individual gets to see c_i, f_i, r,
  and at that point it is easy to find another value c'_i such that
  F(c'_i,r) = F(c_i,r).


2. Computing the sequence of values 1, i, i^2, .., i^n mod q takes
n multiplications mod q (each number in the sequence is obtained by
multiplying the prior number in the sequence by i and reducing mod q),
and each multiplication mod q requires O((lg q)^2) bit operations, so
computing this sequence takes O(n (lg q)^2) bit operations.  Then
we multiply 1 * a_0, i * a_1, i^2 * a_2, ..., i^n * a_n, and reduce
modulo q.  This requires n more multiplications, so O(n (lg q)^2) more
bit operations.  Finally we add these up, which takes n-1 additions
modulo q, or O(n lg q) bit operations.  In total, we have done
O(n (lg q)^2) + O(n (lg q)^2) + O(n lg q) = O(n (lg q)^2) bit operations.

Alternative answer: In the k-th iteration of the loop, we compute
i^k mod q (which takes O(k (lg q)^2) bit operations, since it involves
k multiplications modulo q), then multiply that by a_k (which takes
O((lg q)^2) bit operations).  Therefore each iteration requires
O(k (lg q)^2) + O((lg q)^2) = O(k (lg q)^2) bit operations.  Adding
these up for k=1,2,...,n gives O((1+2+..+n) (lg q)^2), i.e.,
O(n^2 (lg q)^2) bit operations.  Finally we sum up the result of each
iteration, which adds another O(n lg q) bit operations.  In total this
is O(n^2 (lg q)^2) bit operations.

See Discussion Section 7 for more discussion of this problem and
yet another alternative answer.


General comment: This quiz was probably the hardest one I have given
so far.  If you had some difficulties, you're not alone!