Secret Sharing is an important class of protocols in cryptography. In this problem we take a look at some simple implementations using SS ciphers. a) We start with the case of 2 parties who want to be able to decrypt a ciphertext only if they are both present and not individually. Think of the following protocol. A random member of the key-space (bit-strings) re K is picked. Two keys are generated ka = r and kb = r ka. Now if encryption is done using r both parties must be present to compute kak, for decryption. Show that the advantage of an attacker in breaking the semantic security of E(r, m) given k is related to the semantic security advantage of breaking E in general. b) We can then do the same for 2-out-of-3. We have 3 parties and we want any 2 of them to be able to decrypt. Think of the following approach. We randomly pick (ko, k) and (ko, k) that fit the equations kok = k k = k. How should we distribute the 4 ki, ki among 3 parties to make it such that no one party can learn but any 2 parties can learn k? c) We now implement this key splitting scheme with encryption in a way so that the construction of k on a single machine is not necessary. Using semantically secure E we build the following encryption over 4 keys (ko, k, k2, k3) K4: c (E(k, E(ko, m)), E(k3, E(k2, m))) How should we distribute the 4 keys to allow for 2-out-of-3?