Two Constructions of Fuzzy Identity Based Signature

Sahai and Waters first introduced the notion of fuzzy identity based encryption (Fuzzy IBE) in 2005, which can be applied to enable encryption using biometric inputs as identities. Later, Yang et al. introduced the concept of fuzzy identity based signature (Fuzzy IBS) in 2008, and constructed a Fuzzy IBS scheme based on Sahai and Waters's Fuzzy IBE scheme. In this paper, we further formalize the notion and security model of Fuzzy IBS scheme and present two new constructions of Fuzzy IBS scheme. The first Fuzzy IBS scheme follows a certification approach based on standard signatures and its security is the same as that of underlying standard signature scheme. The second Fuzzy IBS scheme is a transformation from convertible identification schemes in the random oracle model and it is proved to be existentially unforgeable under a chosen message attack and Fuzzy identity attack in the random oracle model assuming the Discrete Logarithm problem is computationally hard.