Handout 7: Zero KnowledgeBoaz BarakTotal of 110 points.Exercises due November 15th, 2005 1:30pm.Exercise 1 (Interaction is necessary, 15 points). Let L be a language that is not decidable bypolynomial-sized circuits. Show that there is no non-interactive zero knowledge proof system forL. That is, show that if a language L has a proof system that consists of a single message from theprover to the verifier then L is decidable by polynomial-sized circuits.Exercise 2 (Randomness is necessary, 15 points). Let L be a language that is not decidable bypolynomial-sized circuits. Show that there is no deterministic zero knowledge proof system for L.That is, show that if a language L has a proof system where the verifier is deterministic then L isdecidable by polynomial-sized circuits.Exercise 3 (80 points). Consider the following more sophisticated identification problem: we wantto have a box that decides whether or not to allow people inside a building but every person maybe authorized to enter the building at different times.Design and prove security for an identification protocol with the following properties: (If youdesign a correct protocol but can’t or don’t have time to prove everything, you will still get partialcredit)• Assume that each person is authorized for a particular range of hours every day. That is, therange of each person is two numbers t1≤ t2between 0 and 24. For simplicity assume thatevery one has access to perfectly synchronized clocks.• There is some central trusted algorithm that provides each person with some secret datacorresponding to her authorized range. She can use this secret data when interacting withthe box. This algorithm also provides the public information for the box.• The box contains only a clock and some public information. The box does not contain thelist of authorized people and their authorized time periods.• Even if a cheating box interacts with a person authorized to enter at a particular time, itshould not learn anything about her secret information. It should not even learn anythingabout the range of that person (other than that this range contains that particular time).• A person that has authorization for a particular time period can not (with non-negligibleprobability) convince an honest box to allow her to enter in another time period. This holdseven if that p erson is given the contents of data in the box and even in previous days managedto install a cheating box that interacted with other people that are authorized for that period.1See footnote for hint1Clarification: You should try to design your system to achieve all the above security goals.However, to keep things simple when proving security, consider only the following simplified attackscenario: we have Alice a user that is authorized to enter the building at all hours (e.g., range 0 to23) and Bob a user that is authorized to enter the building only at specified times (say between 1and 2). We think of the following attack: Bob gets all the information contents of the valid b ox.Then he has Alice interact once with a fake box of its own design. Then, he needs to interact withthe real box and convince it to let him in at a time that is not in his range. We say the system issecure of the probability of Bob’s success is at most 1/nω(1).1Hint: For starters you might want to think how you would do that if you could put secret information in the box, but did not want tostore there the long list of all people and their time ranges. Use the following components: zero-knowledge proofs for NP, commitment schemes,message authentication codes. Note that if you have some secret information, you can make a commitment to that secret