I haven't had time to delve into the details of this attack, but I do want to note that adding randomization usually doesn't do much for security in these situations. Essentially, randomization usually just increases the number of samples needed for the attack, so it just ups the computational cost a bit. The same is true in timing attacks, for example, and I very strongly suspect that's the case here too.
The authors give some ideas for mitigation, however, in section 11 of their paper [1] (appropriately titled "Mitigation").
The authors give some ideas for mitigation, however, in section 11 of their paper [1] (appropriately titled "Mitigation").
[1] http://www.tau.ac.il/~tromer/papers/acoustic-20131218.pdf