Current Cloud services raise serious security and privacy concerns due to the potential misuse of user data by the omniscient Cloud service provider. Solutions proposing the “cloud-of-clouds” paradigm just mitigate service availability threats, and additional encryption operations do not prevent users from being identified and traced. Moreover, these solutions still fail to address a main orthogonal problem, i.e. the intrinsic contrast between the provider’s business model and the user’s privacy. In this paper, we propose a new architecture for Cloud computing which addresses the protection of the user’s privacy from the outset. Cloud services are provided by a number of cooperating independent parties consisting in the user nodes themselves. Unlike current Cloud services, the proposed solution provides user anonymity and untraceability. Such architecture can still take part in the “cloud-of-clouds”, allowing users to select service providers on the basis of the expected privacy protection.