Modern systems make extensive use of resource virtualization to achieve high hardware utilization and minimize the total cost of ownership. However, sharing of physical resources invariably opens the door to side-channel exploitation where co-located attackers can covertly examine a victim's behavior and/or steal private information. Even though applications may not share data, they still compete for shared physical resources, notably for cache capacity. Since cache lookup is data/address-dependent, even the presence or absence of data in the cache can reveal sensitive information. This paper proposes Ceviche, a novel hardware virtualization strategy that allows for the secure allocation and use of physical cache resources among threads that belong to different trust domains. Ceviche enables a capability-based cache lookup by translating a given address-domain ID pair into a capability that encodes the access rights and the allowed set of operations on the physical cache line that it grants access to. By constraining cache lookup to occur based on a capability, Ceviche can achieve fine-grained partitioning of the cache at the granularity of a cache line, enforcing a wide set of confidentiality, availability, and fairness guarantees, while maximizing cache utilization. The paper presents detailed design mechanisms, policies, and optimizations along with extensive evaluation to demonstrate the feasibility of integrating the secure virtualization layer into modern multicore cache hierarchies. Ceviche caches offer protections at all levels of the cache hierarchy and incur an average performance degradation of 2.4% when compared to an insecure baseline, while only imposing 1.8% additional performance degradation over state-of-the-art secure caches Mirage and ScatterCache.