Learning Character Strings via Mastermind Queries, With a Case Study Involving mtDNA
Michael T. Goodrich · IEEE Transactions on Information Theory · 2012
We study the degree to which a character stringQleaks details about itself any time it engages in comparison protocols with a strings provided by a querier, Bob, even if those protocols are cryptographically guaranteed to produce no additional information other than the scores that assess the degree to whichQmatches strings offered by Bob. We show that such scenarios allow Bob to play variants of the game of Mastermind withQso as to learn the complete identity ofQ. We show that there are a number of efficient implementations for Bob to employ in these Mastermind attacks, depending on knowledge he has about the structure ofQ, which show how quickly he can determineQ. Indeed, we show that Bob can discoverQusing a number of rounds of test comparisons that is much smaller than the length ofQ, under reasonable assumptions regarding the types of scores that are returned by the cryptographic protocols and whether he can use knowledge about the distribution thatQcomes from. We also provide the results of a case study we performed on a database of mitochondrial DNA, showing the vulnerability of existing real-world DNA data to the Mastermind attack.