Interesting problem, right? Not an expert in the area, but blockchain implementers say they solve this issue. Afaik then there isn't one trusted party, but anyone can compile and run the code and be a provider (and be paid), and a single untrustworthy party won't bother because his chances of compromising the user's data is small.
Lately I've spent some time contemplating how to establish trust in cloud services, this particular nut I haven't been able to crack yet.