How to Efficiently Determine the Lattice Scale for Fuzzy Extractors and Fuzzy Signatures

Fuzzy extractors (FEs) and fuzzy signatures (FSs) are promising primitives for online biometric authentication with biometric template protection. Some FE and FS schemes are constructed with a lattice, and an important problem for implementing them is to determine the lattice scale to an appropriate value. The scale affects False Matching Rate (FMR) and False Non-Matching Rate (FNMR), so it has to be chosen so that FMR and FNMR are suitable for system requirements. For a given dataset, FMR (resp. FNMR) at a certain scale can be calculated by the ratio of matching imposter pairs (resp. non-matching genuine pairs) to the number of all the impostor (resp. genuine) pairs. However, to find an appropriate scale, it is inefficient to change the scale to various values and repeat the matching for all pairs.Our goal in this paper is to calculate FMR and FNMR at various scales efficiently. For this goal, we utilize a metric introduced by Zhang et al. for lattice-based FEs, which we call the lattice distance. We show that we can obtain the exact value of FMR and FNMR at almost all scales by calculating the lattice distance for each pair of the dataset once. Furthermore, for a triangular lattice, used in Katsumata et al.’s FS, we give an algorithm for calculating the lattice distance in linear time in the dimension of the feature space.