Homomorphically encrypted services don't need a priori knowledge of the encryption key. That's literally the whole point.

Consider the following (very weak) encryption scheme:

m, k ∈ Z[p], E(m) = m * k mod p, D(c) = c * k⁻¹ mod p

With this, I can implement a service that receives two cyphertexts and computes their encrypted sum, without knowledge of the key k:

E(x) + E(y) = x * k + y * k mod p = (x + y) * k mod p = E(x + y)

Of course, such a service is not too interesting, but if you could devise an algebraic structure that supported sufficiently complex operations on cyphertexts (and with a stronger encryption), then by composing these operations one could implement arbitrarily complex computations.