Guessing secrets with inner product questions. (English) Zbl 1058.94006

Chung, Fan; Graham, Ronald; Lu, Linyuan

Proceedings of the thirteenth annual ACM-SIAM symposium on discrete algorithms, San Francisco, CA, USA, January 6–8, 2002. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM) (ISBN 0-89871-513-X/pbk). 247-253 (2002).

Summary: Suppose we are given some fixed (but unknown) subset \(X\) of a set \(\Omega=\mathbb{F}^n_2\), where \(\mathbb{F}_2\) 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 \(\Omega\), and the “answer” to \(Q\) is just the inner product \(Q\cdot x\) (in \(\mathbb{F}_2)\) for some \(x\in 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^3)\) algorithm for an optimal strategy. However, for the case that \(| X|\geq 3\), we show that no such polynomial-time algorithm can exist, unless P = NP.
For the entire collection see [Zbl 1029.00035].

MSC:

94A15	Information theory (general)
91A43	Games involving graphs
05C90	Applications of graph theory
68R05	Combinatorics in computer science
68W01	General topics in the theory of algorithms