In this paper, we study sparsity-exploiting Mastermind algorithms for attacking the privacy of an entire database of character strings or vectors, such as DNA strings, movie ratings, or social network friendship data. Based on reductions to nonadaptive group testing, our methods are able to take advantage of minimal amounts of privacy leakage, such as contained in a single bit that indicates if two people in a medical database have any common genetic mutations, or if two people have any common friends in an online social network. We analyze our Mastermind attack algorithms using theoretical characterizations that provide sublinear bounds on the number of queries needed to clone the database, as well as experimental tests on genomic information, collaborative filtering data, and online social networks. By taking advantage of the generally sparse nature of these real-world databases and modulating a parameter that controls query sparsity, we demonstrate that relatively few nonadaptive queries are needed to recover a large majority of each database.
Chv 'a tal @cite_25 studied the combinatorics of the general Mastermind game, showing that it can be solved in polynomial time using @math guesses. Chen @cite_20 showed how this can be improved to @math guesses and Goodrich @cite_43 showed how this bound can be improved to @math . Unfortunately, from the perspective of the cloning problem, all of these algorithms are , in that they use results of previous queries to construct future queries. Adaptive algorithms can only be used effectively for the interactions between a single pair of strings. For a sequence of queries to be used against an entire database of strings, we need a algorithm, that is, an algorithm where queries are not dependent upon answers from previous queries, which is equivalent to the codebreaker making all his guesses in advance.
@cite_43 @cite_25 @cite_20
2045496672 1490551088
In this paper, we study the algorithmic complexity of the Mastermind game, where results are single-color black pegs. This differs from the usual dual-color version of the game, but better corresponds to applications in genetics. We show that it is NP-complete to determine if a sequence of single-color Mastermind results have a satisfying vector. We also show how to devise efficient algorithms for discovering a hidden vector through single-color queries. Indeed, our algorithm improves a previous method of Chvatal by almost a factor of 2. We study the problem of finding a hidden code k in the domain 1, ..., m n in the presence of an oracle which, for any x in the domain, answers a pair of numbers a(x,k) and b(x,k) such that a(x,k) is the number of components coinciding in x and k and, b(x, k) is the sum of a(x, k) and the number of components occurring in both x and k but, not at the same position. We show that ( m n )+ 2nlogn + 2n + 2 queries are sufficient to find any hidden code if m ≥ n.