Fuzzy Identity-Based Signature from Lattices for Identities in a Large Universe

摘要

A fuzzy identity-based signature (FIBS) is exactly like a traditional identity-based signature except that a signature issued under an identity id can be verified under any identity id' that is 'close enough' to id. This property allows FIBS having an efficient application in biometric authentication and three schemes over lattices exist, two constructions in the random oracle model and one in the standard model. However, the identities can only support binary vectors, i.e., {0, 1}~ℓ, which greatly limit the scope of its application. In this paper, a FIBS scheme from the hardness of lattice problems for identities living in a large universe, i.e., (Z_q~n)~ℓ, is proposed, so that they can capture more expressive attributes and the new construction is proved to be existentially unforgetable against adap-tively chosen identity and message attacks (EU-alD-CMA) in the random oracle model.