Thanks to @vbuterin for noticing that this protocol can be simplified: Every validator generates a random polynomial c(x)=\sum_{i=0}^{n-1} c_i x^i and commits to it via C = c(s) H. Every time a proof of custody needs to be computed, the data is encoded into a polynomial d(x) and a data commitment D = d(s) G is computed. To compute a proof of custody, a validator computes the polynomial product h(x) = c(x) d(x) (this can be done in n \log n field operations$ using FFTs) and publish \pi = h(s) G, which can be checked via the pairing equation
Naïvely, this can be outsourced by giving c_0 G, c_1 s G, c_2 s^2 G, etc. to the provider. They can then compute \pi in n EC and n^2 field multiplications using textbook multiplication or O(n \log n) using FFT algorithms on EC elements.
However, by changing the slashing condition, this can be stopped: We use a slashing condition where a whistleblower can get the validator slashed by being able to compute \pi for a data polynomial that is (a) not constant and (b) clearly not a block.