Efficient Accuracy Evaluation Methods for Lattice-Based Fuzzy Extractors and Fuzzy Signatures

Fuzzy Extractors (FEs) and Fuzzy Signatures (FSs) are promising primitives for realizing online biometric authentication with Biometric Template Protection (BTP). To realize better authentication accuracy, lattice-based FEs and FSs have been studied. To apply them to biometric authentication, one has to determine the lattice scale to an appropriate value because it affects accuracy as well as the threshold in ordinary matching schemes. To find such an appropriate scale, one has to evaluate accuracy at various scales using a dataset. A simple method might be to change the scale to various values and repeat the matching for all pairs, but it is inefficient. The matching process includes solving the Closest Vector Problem (CVP), so when we evaluate accuracy for k scales using the dataset including P pairs, the simple method has to solve CVP kP times. In this paper, we propose a method to obtain accuracy for almost all scales without solving CVP. The proposed method computes the distance induced by the Minkowski functional of the Voronoi region, which we call the lattice distance, for each pair only once. Furthermore, in the case of a triangular lattice, we give a Θ (n) time algorithm for computing the lattice distance. Experimental analysis for the triangular lattice shows that accuracy for almost all scales can be obtained by the proposed method in a shorter time than the time required for obtaining accuracy for one scale by the simple method. We also show that accuracy at the remaining scales can be obtained by additionally solving CVP only once for each pair.