On the Security of Two Fuzzy Identity-Based Signature Schemes

In BEI 2009, Wang and Kim proposed a new fuzzy identity-based signature (FIBS) scheme and proved that it is existentially unforgeable under chosen message attack and fuzzy identity attack in the random oracle model if the discrete logarithm problem is computationally hard. In NSS 2009, Chen et al. proposed a fuzzy identity-based signature with dynamic threshold which is proven secure against unforgeability in the standard model if the multi-sequence of Diffie-Hellman exponents problem is computationally hard. In this paper, we show that the former FIBS is vulnerable to key only attack and the latter FIBS is vulnerable to collusion attack. In the key only attack, by possessing only the information of public keys, an adversary can generate the user private key of every user in the system and thereby constitutes a breach of security. In the collusion attack, the misbehaved users can collude together in such a way that they can generate a signature that none of them alone could.