Paper 2017/1188

Signature Schemes with a Fuzzy Private Key

Kenta Takahashi, Takahiro Matsuda, Takao Murakami, Goichiro Hanaoka, and Masakatsu Nishigaki

Abstract

In this paper, we introduce a new concept of digital signature that we call \emph{fuzzy signature}, which is a signature scheme that uses a noisy string such as biometric data as a private key, but \emph{does not require user-specific auxiliary data} (which is also called a helper string in the context of fuzzy extractors), for generating a signature. Our technical contributions are three-fold: (1) We first give the formal definition of fuzzy signature, together with a formal definition of a \lq\lq setting'' that specifies some necessary information for fuzzy data. (2) We give a generic construction of a fuzzy signature scheme based on a signature scheme that has certain homomorphic properties regarding keys and satisfies a kind of related key attack security with respect to addition, and a new tool that we call \emph{linear sketch}. (3) We specify two concrete settings for fuzzy data, and for each of the settings give a concrete instantiation of these building blocks for our generic construction, leading to two concrete fuzzy signature schemes. We also discuss how fuzzy signature schemes can be used to realize a biometric-based PKI that uses biometric data itself as a cryptographic key, which we call the \emph{public biometric infrastructure (PBI)}.

Note: This is the merged full version of the earlier papers that appear in the proceedings of ACNS 2015 and the proceedings of ACNS 2016. We added Section 1.5, where we explain the relations, correspondences, and differences between this paper and our ACNS 2015 and ACNS 2016 papers. We also updated some reference, and fixed typos.