Really not that complicated
You'll need your scientific calculator and rather advanced mathematical knowledge to make sense of the next few of the paper's pages.
Really, Simon? Pages 2-3 have nothing more complicated than some very straightforward big-O complexity formulas and a couple of simple probabilities - the sort of stuff they teach in undergrad CS. Things get a bit more complicated after that, but anyone with the basic mathematical literacy you'd expect from a technical baccalaureate should be able to follow it.
The problem they're addressing is this: You don't want an adversary to be able to discern information about your data by watching your access pattern (traffic analysis). The defense against this is to rearrange the data so your access pattern is indistinguishable from random. This is like shuffling a deck of cards, except that you don't want the shuffling process to be reversible, from the cloud server's point of view, so straightforward swapping-based shuffles won't do. (The server could keep a record of the swaps.)
The conventional way to approach this is to assign a random key to all the records, then sort the data using that random key. That's expensive, because sorting is expensive.
What this team have done is devised a relatively cheap shuffle that doesn't involve sorting and isn't reversible by the server. From the paper: "Our Melbourne shuffle algorithm is instead the first data-oblivious shuffle method that is not based on a data-oblivious sorting algorithm." They also show related results, such as using the Melbourne shuffle with various oblivious access algorithms.
The algorithm itself involves taking N input records and distributing them among N buckets along with a number of dummy records, according to a pseudorandom permutation. That's followed by a "clean-up" phase that removes the dummy records and rearranges items in each bucket into the correct order. The paper has the complete algorithm (along with variants with different performance characteristics), diagrams, etc. Actually understanding it to the point of implementing it would probably require some head-scratching from most folks, but it's hardly the most obscure thing to come down the pike.