Foundations of Computer Science: Honors
Homework 1B
Problem 4 Boolean algebra operations can be expressed as arithmetic operations mod 2. Let 1 be true, and 0 false. (a) Show that A ∧ B = (A · B mod 2). (b) What is ¬A? (c) What is A ∨ B?
Problem 5 Over lunch at the faculty club, n professors are expressing their concerns over their salaries. Each professor wants to know how his/her salary compares to the average salary of the group, but no professor wants to divulge any information about his/her salary to the other n - 1.
(a) Devise a scheme that allows the professors to compute the average of their salaries, while preserving their privacy. You may assume that all the professors will adhere to the rules of the protocol, although they will try to extract as much information from the protocol as possible. You may also assume that it is public knowledge that the professors’ salaries together don’t exceed $1 trillion.
(b) Now extend the protocol to be robust even when groups of professors collude. Specifically, if i professors collude, naturally they can learn the average salary of the remaining n - i. Your protocol should reveal no additional information.
