An adversary can always determine the virtual address. How will a new cache design help?
Of course, the virtual address is translated into a physical address via the MMU tables - this does not attempt to disguise that.
Instead, what this idea attempts to do is disguise the mapping between physical address and location within the cache.
The idea behind cache attacks is that memory references that the program under attack makes affects the cache (for example, if the program makes a reference to an sbox entry, that sbox entry will be pulled into the cache if it wasn't already there). Hence, if the attacker monitors the cache (which is shared between different programs running on the same CPU), they can deduce what memory references the program makes (and if the program makes secret dependent references, then the attacker gets some information about those secrets).
The idea in the paper is to randomize the mapping between physical addresses and cache entries; that is, if the program loads in an sbox entry, the attacker could potentially deduce that something was loaded into the cache, but wouldn't be able to determine which entry was loaded (and so he couldn't deduce the sbox entry).
That said, there are several obvious issues with the cited paper:
The attacker couldn't necessarily deduce where things got loaded, but they could determine that something was, and that gives them some information. For example, the attacker would be able to distinguish between 'two different sbox entries in two different cache lines were referenced' and 'only the sbox entries in one cache line were referenced', and that obviously is some information.
Modern CPUs have multiple levels of cache; this proposal does not address the L1 cache (which is internal to the CPU), and the attacker can obviously exploit that.
The "two cycle" cipher they propose is, to put it kindly, dreadful. It is entirely linear (see figure 6 of the paper); that is, $\text{Encrypt}_K(M)$ is equivalent to $\text{Encrypt}_0(M) \oplus \text{F}(K)$ (for some function $F$, which is easy to compute, but which we can ignore) - the attack cares only about collisions, and the value of the secret key $K$ does not affect what collides with what. Hence, the attacker can just proceed with his normal attack, just taking into account how $\text{Encrypt}_0$ works, and he proceeds as efficiently as before.
