Guessing secrets with inner product questions
Fan Chung, Ronald Graham, Linyuan Lü · 2002
Suppose we are given some fixed (but unknown) subset X of a set# 2 , where F2 denotes the field of two elements. We would like to learn as much as possible about the elements of X by asking certain binary questions. Each "question" Q is some element of # and the "answer" to Q is just the inner product Q x (in F2 ) for some x X. However, the choice of x is made by a truthful (but possibly malevolent) adversary A, whom we may assume is trying to choose answers so as to yield as little information as possible about X. In this paper, we study various aspects of this problem. In particular, we are interested in extracting as much information as possible about X from A's answers. Although A can prevent us from learning the identity of any particular element of X, with appropriate questions we can still learn a lot about X. We determine the maximum amount of information that can be recovered and discuss the optimal strategies for selecting questions. For the case that |X| = 2, we give an O(n algorithm for an optimal strategy. However, for the case that |X| # 3, we show that no such polynomial-time algorithm can exist, unless P = NP .