Recovering Attacks Against Linear Sketch in Fuzzy Signature Schemes of ACNS 2015 and 2016

In biometrics, template protection aims to protect the confidentiality of templates (i.e., enrolled biometric data) by certain conversion. At ACNS 2015, as a new approach of template protection, Takahashi et al. proposed a new concept of digital signature, called “fuzzy signature”, that uses biometric data as a private key for securely generating a signature. After that, at ACNS 2016, Matsuda et al. modified the original scheme with several relaxing requirements. A main ingredient of fuzzy signature is “linear sketch”, which incorporates a kind of linear encoding and error correction process to securely output only the difference of signing keys without revealing any biometric data. In this paper, we give recovering attacks against the linear sketch schemes proposed at ACNS 2015 and 2016. Specifically, given encoded data by linear sketch (called a “sketch”), our attacks can directly recover both the signing key and the biometric data embedded in the sketch. Our attacks make use of the special structure that a sketch has the form of a sum of an integral part and a decimal part, and biometric data is embedded in the decimal part. On the other hand, we give a simple countermeasure against our attacks and discuss the effect in both theory and practice.