5. (18 points) Suppose Alice and Bob live in a country with 50 states. Alice is currently in state a {1,...,50} and Bob is currently in state b {1...,50). They can com- municate with one another and Alice wants to test if she is currently in the same state as Bob. If they are in the same state, Alice should learn that fact, but if not th en she should learn nothing else about Bob's location. Bob should learn nothing about Alice's location. They agree on the following scheme: As in the ElGamal encryption scheme, They fix a group G of prime order q and generator g of G. Alice chooses random r and y in Zg and sends to Bob (A0, A1, A2) = (g*, g, gry+a). Bob chooses random r and s in Z, and sends to Alice (B1, B2) = (Ag*, (A2/9) A.). (a) (6 points) What should Alice do now to test if they are in the same state (i.e. to test if a =b) (Hint: compare Bf and B2.)? (b) (6 points) Explain why Bob learns nothing from this protocol. 8 (C) (6 points) Explain why, if a +b, Alice also learns nothing else (other than a + b) from this protocol. 5. (18 points) Suppose Alice and Bob live in a country with 50 states. Alice is currently in state a {1,...,50} and Bob is currently in state b {1...,50). They can com- municate with one another and Alice wants to test if she is currently in the same state as Bob. If they are in the same state, Alice should learn that fact, but if not th en she should learn nothing else about Bob's location. Bob should learn nothing about Alice's location. They agree on the following scheme: As in the ElGamal encryption scheme, They fix a group G of prime order q and generator g of G. Alice chooses random r and y in Zg and sends to Bob (A0, A1, A2) = (g*, g, gry+a). Bob chooses random r and s in Z, and sends to Alice (B1, B2) = (Ag*, (A2/9) A.). (a) (6 points) What should Alice do now to test if they are in the same state (i.e. to test if a =b) (Hint: compare Bf and B2.)? (b) (6 points) Explain why Bob learns nothing from this protocol. 8 (C) (6 points) Explain why, if a +b, Alice also learns nothing else (other than a + b) from this protocol