  Dodis et al. proposed an improved version of the fuzzy vault scheme, one of
the most popular primitives used in biometric cryptosystems, requiring less
storage and leaking less information. Recently, Blanton and Aliasgari have
shown that the relation of two improved fuzzy vault records of the same
individual may be determined by solving a system of non-linear equations.
However, they conjectured that this is feasible for small parameters only. In
this paper, we present a new attack against the improved fuzzy vault scheme
based on the extended Euclidean algorithm that determines if two records are
related and recovers the elements by which the protected features, e.g., the
biometric templates, differ. Our theoretical and empirical analysis
demonstrates that the attack is very effective and efficient for practical
parameters. Furthermore, we show how this attack can be extended to fully
recover both feature sets from related vault records much more efficiently than
possible by attacking each record individually. We complement this work by
deriving lower bounds for record multiplicity attacks and use these to show
that our attack is asymptotically optimal in an information theoretic sense.
Finally, we propose remedies to harden the scheme against record multiplicity
attacks.
