I think the term information is misleading here. In any encrypted message there is the original information, it must be because we are able to decrypt it. So from an information theory point of view that the server can "distinguished my ciphertext enough to produce a coherent reply" is always possible. The whole point of encryption is that we have Math that allows the identification of that information only under presence of the (or at least some kind of) secret.

The price that HE is paying is essentially "have to run every possible contributing computation", which means it has to scale extremely badly for anything real world complex