End-To-end security in the cloud has gained even more importance after the outbreak of data breaches and massive surveillance programs around the globe last year. While the community features a number of cloud-based security mechanisms, existing solutions either provide security at the expense of the economy of scale and cost effectiveness of the cloud (i.e., at the expense of resource sharing and deduplication techniques), or they meet the latter objectives at the expense of security (e.g., the customer is required to fully trust the provider). In this paper, we shed light on this problem, and we analyze the challenges in reconciling security and functional requirements in existing multi-Tenant clouds. We also explore the solution space to effectively enhance the current security offerings of existing cloud storage services. As far as we are aware, this is the first contribution which comprehensively explores possible avenues for reconciling the current cloud trends with end-To-end security requirements.