  Consider a set-associative cache with $p^n$ sets and $p^n$ ways where $p$ is
prime and $n>0$. Furthermore, assume that the cache may be shared among $p^n$
mutually distrusting principals that may use the Prime+Probe side-channel
attack against one another; architecturally, these principals occupy separate
security domains (for example, separate processes, virtual machines, sandboxes,
etc.). This paper shows that there exists a linear skewing of cache sets over
the Galois field $G_{p^n}$ that exhibits the following property: each cache set
of each security domain intersects every cache set of every other security
domain exactly once. Therefore, a random eviction from a single cache set in
security domain $A$ may be observed via Prime+Probe in any of security domain
$B$'s cache sets. This paper characterizes this linear skewing and describes
how it can be implemented efficiently in hardware.
