The increasing growth in the use of Hardware Security Modules (HSMs) towards identification and authentication of a security endpoint have raised numerous privacy and security concerns. HSMs have the ability to tie a system or an object, along with its users to the physical world. However, this enables tracking of the user and/or an object associated with the HSM. Current systems do not adequately address the privacy needs and as such are susceptible to various attacks. In this work, we analyse various security and privacy concerns that arise when deploying such hardware security modules and propose a system that allow users to create pseudonyms from a trusted master public-secret key pair. The proposed system is based on the intractability of factoring and finding square roots of a quadratic residue modulo a composite number, where the composite number is a product of two large primes. Along with the standard notion of protecting privacy of an user, the proposed system offers colligation between seemingly independent pseudonyms. This new property when combined with HSMs that store the master secret key is extremely beneficial to a user, as it offers a convenient way to generate a large number of pseudonyms using relatively small storage requirements.