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

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