Consider the following (partially specified) method for transmitting a message securely be...

Consider the following (partially specified) method for transmitting a message securely between a sender and a receiver. The message will be represented as a string of bits. Let , ∑ = {0, 1} and let ∑* denote the set of all strings of 0 or more bits (e.g., 0,00,1110001 ε ∑*). The "empty string," with no bits, will be denoted λ ε ∑*.

The sender and receiver share a secret function  That is, f takes a word and a bit, and returns a bit. When the receiver gets a sequence of bits α ε ∑*, he or she runs the following method to decipher it.

One could view this is as a type of "stream cipher with feedback." One problem with this approach is that, if any bit α1 gets corrupted in transmission, it will corrupt the computed value of βj for all j ≥ i.

We consider the following problem. A sender S wants to transmit the same (plain-text) message P to each of k receivers R1,…,Rk. With each one, he shares a different secret function f<i>. Thus he sends a different encrypted message α<i> to each receiver, so that α<i> decrypts to P when the above algorithm is run with the function f.

Unfortunately, the communication channels are very noisy, so each of the n bits in each of the k transmissions is independently corrupted (i.e., flipped to its complement) with probability 1/4. Thus no single receiver on his or her own is likely to be able to decrypt the message correctly. Show, however, that if k is large enough as a function of n, then the k receivers can jointly reconstruct the plain-text message in the following way. They get together, and without revealing any of the α>i> or the f, they interactively run an algorithm that will produce the correct P with probability at least 9/10. (How large do you need k to be in your algorithm?)