8. Suppose Alice is broadcasting packets to 12 recipients B_1,,B_12. Privacy is not important but integrity is. In other words, each of B_1,,B_12 should be assured that the packets he is receiving were sent by Alice. Alice decides to use a MAC. Suppose Alice and B_1,,B_12 all share a secret key k. Alice computes a tag for every packet she sends using key k. Each user B_i verifies the tag when receiving the packet and drops the packet if the tag is invalid. Alice notices that this scheme is insecure because user B_1 can use the key k to send packets with a valid tag to users B_2,,B_12 and they will all be fooled into thinking that these packets are from Alice. Instead, Alice sets up a set S of m secret keys S=(k_1,,k_m). She gives each user B_i some subset S_i of the m keys. When Alice transmits a packet she appends m tagsto it by computing the tag with each of her m keys. When user B_i receives a packet he accepts it as valid only if all tags corresponding to his keys in S_i are valid. For example, if user B_1 is given keys (k_1,k_2) he will accept an incoming packet only if the first and second tags are valid. Note that B_1 cannot validate the remaining m-2 tags because he does not have k_3 through k_m. 1. For the scheme to work (i.e., no single user can forge packets on behalf of Alice), at least how many keys should not be shared between every two recipients? 2. At least how many tags Alice needs to append to every packet to satisfy the condition above? m=

8. Suppose Alice is broadcasting packets to 12 recipients B_1,...,B_12. Privacy is not important but integrity is. In other words, each of B_1,...,B_12 should be assured that the packets he is receiving were sent by Alice. Alice decides to use a MAC. Suppose Alice and B_1,...,B_12 all share a secret key k. Alice computes a tag for every packet she sends using key k. Each user B_i verifies the tag when receiving the packet and drops the packet if the tag is invalid. Alice notices that this scheme is insecure because user B_1 can use the key k to send packets with a valid tag to users B_2,..,B_12 and they will all be fooled into thinking that these packets are from Alice. Instead, Alice sets up a set S of m secret keys S=(k_1,,k_m). She gives each user B_i some subset S_i of the m keys. When Alice transmits a packet she appends m tags to it by computing the tag with each of her m keys. When user Bi receives a packet he accepts it as valid only if all tags corresponding to his keys in Si are valid. For example, if user B1 is given keys (k_1,k_2) he will accept an incoming packet only if the first and second tags are valid. Note that B_1 cannot validate the remaining m2 tags because he does not have k_3 through k_m. 1. For the scheme to work (i.e., no single user can forge packets on behalf of Alice), at least how many keys should not be shared between every two recipients? 2. At least how many tags Alice needs to append to every packet to satisfy the condition above? m=