Re: But is this not security through obscurity?
That's not how the paper suggests it works. Simplifying the example given:
SELECT COUNT(*) FROM items WHERE ItemId = ?
you devise a series of functions f1(x), f2(x), ... and ask each parition to calculate the sum of their own f(x) over all the rows in the table. You devise the functions in such a way, for example, that the sum of all the functions returns "1" for each x where ItemID has the requested value and "0" otherwise. You can then pass each partition a different function, but if you add the results together you get the query result you're looking for.
So although you execute multiple queries, only an aggregate result is returned from each partition.
Each f(x) is a point or interval function (i.e. it returns 1 if x is either a selected single value or within a range of selected values) and the claim is that although each parition of necessity knows f(x), it cannot determine the magic values that cause f(x) to return 1, thereby making the original query parameters undiscoverable. That's the point that maths turns into magic as far as I'm concerned...