The point of introducing entropy was to give us a principled way to identify which systems intrinsically capture some process. This is to avoid pancomputationalism, the claim that every system computes and that we project particular meanings onto computational systems. If some operation is in a state space of 1x10^1000 bits and using some external system we can perform the operation in 100 steps (e.g. we did 100 guess-and-check steps), we know that system intrinsically captured approximately 1x10^1000 bits of the operation. If pancomputationalism were true, all systems are equally computational in nature and so no system would be better than any other at supporting the performance of any operation. But this obviously false.
But the entropy considerations are just a practical way for us to identify computational systems with certainty. It isn't an identity criteria. Consider your homomorphically encrypted program where the key is longer than the state space for that program. Presumably we cannot tell this encrypted program apart from some random set of operations that computes nothing (I doubt this is true in practice, but lets go with it). How can we say this program is in fact computing something? The assumption that the program is homomorphically encrypted also says there is a magic string of bits that unlocks its activity. Further, this magic string is independent (i.e. has zero mutual information) with the program in question. Essentially the key is random and so it cannot provide any information about the program itself. So when the key is combined with the encryption scheme to produce the decrypted program, we know that the program was embedded in the encrypted system the whole time, not added by the application of the key.
The key point is that information doesn't just pop into existence, information requires upfront payment in (computational) entropy, a computation-like process that does something like guess-and-check over the state space of the information. If ever you have a string of information, you either got it from somewhere else or you did guess-and-check over the state space. In the case of the homomorphic encryption, we know the key is independent of the program and so the key does not secretly contain the program. Thus the program must already exist in the behavior of the encrypted system.
We don't know the key but we know it exists by assumption. "Exists" here just means the upfront computational cost has already been paid for the relation between the hidden program, the encrypted system and the decryption key. Indeed, we can in theory recover the encrypted program with comparatively zero computational work by using the key. This is in contrast to recovering the mind program from, say, the dynamics of my wall. No upfront computational cost has been paid and so I have to search the entire state space to find a mapping between the wall and the mind program. Thus the wall provides no information about the mind program, i.e. it is not computing the mind program.
But the entropy considerations are just a practical way for us to identify computational systems with certainty. It isn't an identity criteria. Consider your homomorphically encrypted program where the key is longer than the state space for that program. Presumably we cannot tell this encrypted program apart from some random set of operations that computes nothing (I doubt this is true in practice, but lets go with it). How can we say this program is in fact computing something? The assumption that the program is homomorphically encrypted also says there is a magic string of bits that unlocks its activity. Further, this magic string is independent (i.e. has zero mutual information) with the program in question. Essentially the key is random and so it cannot provide any information about the program itself. So when the key is combined with the encryption scheme to produce the decrypted program, we know that the program was embedded in the encrypted system the whole time, not added by the application of the key.
The key point is that information doesn't just pop into existence, information requires upfront payment in (computational) entropy, a computation-like process that does something like guess-and-check over the state space of the information. If ever you have a string of information, you either got it from somewhere else or you did guess-and-check over the state space. In the case of the homomorphic encryption, we know the key is independent of the program and so the key does not secretly contain the program. Thus the program must already exist in the behavior of the encrypted system.
We don't know the key but we know it exists by assumption. "Exists" here just means the upfront computational cost has already been paid for the relation between the hidden program, the encrypted system and the decryption key. Indeed, we can in theory recover the encrypted program with comparatively zero computational work by using the key. This is in contrast to recovering the mind program from, say, the dynamics of my wall. No upfront computational cost has been paid and so I have to search the entire state space to find a mapping between the wall and the mind program. Thus the wall provides no information about the mind program, i.e. it is not computing the mind program.