Cryptanalysis and improvement of an ID-based ad-hoc anonymous identification scheme at CT-RSA 05

An ad-hoc anonymous identification scheme is a new multi-user cryptographic primitive that allows participants from a user population to form ad hoc groups, and then prove membership anonymously in such groups. Recently, Nguyen [L. Nguyen, Accumulators from bilinear pairings and applications, in: CT-RSA 2005, in: LNCS, vol. 3376, Springer-Verlag, 2005, pp. 275–292] proposed an ID-based ad-hoc anonymous identification scheme from bilinear pairings. However, in this paper, we propose an attack on Nguyen's ID-based ad-hoc anonymous identification scheme. We show that any one can impersonate a valid group member to perform the anonymous identification protocol successfully. Furthermore, we propose a solution to improve this scheme against our attack.