[throwaway613834]

What are the time complexities like?

Do they actually do better than "factor the RSA key, then compute the output, then re-encrypt"?

[warkdarrior]

The paper at http://www.shoup.net/papers/helib.pdf should give you an idea of what goes in a HE scheme. They also report performance of multiplying two 1024x1024 matrices: 473 seconds.