The invention provides a method and apparatus for pseudonym generation and authentication. The method comprises the steps of: transmitting a user identity IDuser to a Personal Identity Manager (PIM); receiving a set of public parameters and a prime pseudonym Pprime corresponding to the ID user from the PIM; and selecting at least two random parameters, and generating a sub-pseudonym Ppseu with the at least two random numbers, the set of public parameters, and the prime pseudonym Pprime.