Paper 2017/1188

Signature Schemes with a Fuzzy Private Key

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


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. Major revision. ACNS 2015 and ACNS 2016
Fuzzy SignaturePublic Biometric Infrastructure
Contact author(s)
t-matsuda @ aist go jp
2018-04-02: revised
2017-12-12: received
See all versions
Short URL
Creative Commons Attribution


      author = {Kenta Takahashi and Takahiro Matsuda and Takao Murakami and Goichiro Hanaoka and Masakatsu Nishigaki},
      title = {Signature Schemes with a Fuzzy Private Key},
      howpublished = {Cryptology ePrint Archive, Paper 2017/1188},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.