Efficient strategies to play the indistinguishability game for fuzzy sketches

One of the fundamental requirements for a fuzzy sketch algorithm is to offer indistinguishability, which ensures that an adversary cannot identify related sketches generated from the same biometric identity. Recently, it has been shown that the advantage of an adversary in distinguishing two related sketches generated using the code-offset construction is non-negligible. In this model, it is assumed that the adversary knows that a particular sketch (corresponding to a person´s biometric) is present in a database and the adversary is trying to find out what the best match in the database for his query is. The main contribution of this work is a new, efficient strategy for playing the indistinguishability game. We analyze the model known in the literature in a more realistic scenario in which classification is not perfect but it is subject to errors. In particular, we show that current results give an optimistic view on the capability of an adversary by assuming that she makes no false rejection mistake. In fact, our results indicate that the advantage of an adversary in the real world (where the false rejection rate is non-zero) depends on the threshold chosen by the distinguisher. Furthermore, we introduce a stronger model in which the adversary is assumed to have no a priory knowledge and we extend the existing framework by modeling the advantage of an adversary in the new model. It is also shown that in this stronger model the new strategy for playing the indistinguishability game is at least as strong as the known strategy.