You are assuming that encrypting is a bijection, i.e. that for every plaintext, there is only one possible ciphertext. One of the first things you learn in a pu

You are assuming that encrypting is a bijection, i.e. that for every plaintext, there is only one possible ciphertext. One of the first things you learn in a public key cryptography is that you have to add random bits in the computation of the ciphertext, either via simple random padding (in the case of RSA) or via some more involved steps (in the case of cyclic group-based cryptography). I don't know much about homomorphic encryption (the concept has always seemed contrived to me - if you don't trust your cloud provider, hosting your own servers will always be much more efficient), but I assume they use similar tricks. As for the thing about polynomials: it should be obvious that any polynomial-time computation on an input of a fixed size can be expressed by a DAG of logic gates. Logic gates can in turn be represented by simple polynomials over the field F_2 = { 0, 1 }, and the composition of gates is then simply the composition of polynomials. Since we're talking about fixed-size inputs, this does not really capture the full Turing machine model. However, since all practical encryption schemes can be broken via brute force in exponential time anyway, it only really makes sense to worry about implementing polynomial-time computations in the context of homomorphic encryption.