The increasing concern for identity confidentiality in the Smart City scenario has fostered research on privacy-preserving authentication based on pseudonymization. Pseudonym systems enable citizens to generate pseudo-identities and establish unlinkable anonymous accounts in cloud service providers. The citizen's identity is concealed, and his/her different anonymous accounts cannot be linked to each other. Unfortunately, current pseudonym systems require a trusted certification authority (CA) to issue the cryptographic components (e.g., credentials, secret keys, or pseudonyms) to citizens. This CA, generally a Smart City governmental entity, has the capability to grant or revoke privacy rights at will, hence posing a serious threat in case of corruption. Additionally, if the pseudonym system enables de-anonymization of misusers, a corrupted CA can jeopardize the citizens’ privacy. This paper presents a novel approach to construct a pseudonym system without a trusted issuer. The CA is emulated by a set of Smart City service providers by means of secure multi-party computation (MPC), which circumvents the requirement of assuming an honest CA. The paper provides a full description of the system, which integrates an MPC protocol and a pseudonym-based signature scheme. The system has been implemented and tested.