I'm looking for a Key Derivation Function, kind of like PBKDF2 or Scrypt, but which can be computed by a machine you don't trust. Some way to give it a derivative of the source password, such that the key can be computed from the derivative but the derivative is opaque and otherwise useless to the untrusted machine. Also, I should be able to verify that machine actually performed the KDF and didn't just throw back a random key.
For the first part, protecting the password, I imagined the system would have to be something like:
s = random() P = F(s,password) I = KDF(P) K = G(s,I)
Where s is some random number, and F and G are some kind of functions such that K is always the same given the same password, regardless of s.
Basically, some way to "encrypt" the password into an opaque value that the KDF can generate an incomplete key from, and then we can use the secret from that encryption to get the real key. We then throw away s. Later, to regenerate K from just the password, we can just pick another random s.
I don't know if any such combination of F, KDF, and G exist. I also don't know how to approach the proof requirement; that we can prove the KDF was executed correctly.
And of course this needs to be practical. I'm sure you could accomplish all of this using general homomorphic encryption to implement scrypt, but that would be intolerably slow.