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.
Goodrich @cite_9 studies the problem of discovering a single DNA string from a series of genomic Mastermind queries. All his methods are sequential and adaptive, however, so the only way they could be applied to the data-cloning attack on an entire biological database is if Bob were to focus on each string @math in @math in turn. That is, he would have to gear his queries to specifically discovering each @math in @math distinct rounds'' of computation, each of which uses a lot of string-comparison queries. Such an adaptation of Goodrich's Mastermind attacks to perform data cloning, therefore, would be prohibitively expensive for Bob. Our approach, instead, is based on performing a nonadaptive Mastermind attack on the entire database at once.
@cite_9
2154357802
In this paper, we study the degree to which a genomic string, @math ,leaks details about itself any time it engages in comparison protocolswith a genomic querier, Bob, even if those protocols arecryptographically guaranteed to produce no additional information otherthan the scores that assess the degree to which @math matches stringsoffered by Bob. We show that such scenarios allow Bob to play variantsof the game of Mastermind with @math so as to learn the complete identityof @math . We show that there are a number of efficient implementationsfor Bob to employ in these Mastermind attacks, depending on knowledgehe has about the structure of @math , which show how quickly he candetermine @math . Indeed, we show that Bob can discover @math using anumber of rounds of test comparisons that is much smaller than thelength of @math , under various assumptions regarding the types of scoresthat are returned by the cryptographic protocols and whether he can useknowledge about the distribution that @math comes from, e.g., usingpublic knowledge about the properties of human DNA. We also providethe results of an experimental study we performed on a database ofmitochondrial DNA, showing the vulnerability of existing real-world DNAdata to the Mastermind attack.