I came up with a rather simple FHE scheme that shouldn't work, but I can't figure out how it breaks. Any help with this is appreciated!

Part one

First, note that if we had an abelian field where computing the multiplicative inverse was difficult, then we could construct a homomorphic scheme for addition and multiplication trivially. Let’s say the message we want to encrypt is $m$. Then we sample some random element, $e$ (such that we know $e^{-1}$), and our cipher text simply becomes $c=m\cdot e$. We give the server $m \cdot e$ and $e$. Note that because it is difficult to find the multiplicative inverse, the server cannot simply compute $e^{-1}$ and then multiply that by $m\cdot e$. Anyways, let’s say the server wanted to perform an addition with the cipher text and some constant $a$. They would simply compute $a \cdot e$, and then add this to $m\cdot e$ to get $(a+m)\cdot e$. If this wasn’t a constant (some other encrypted message), we could simply add the messages together. Multiplication is a bit more tricky. Now, we’re gonna need to keep track of how many “e”s are in our cipher text. When the client first gives the server $c$, the exponent of $e$ is simply $1$, so we can store that data point as $(c,1)$. If we have another cipher text $c’ = m’ e$, and we want to multiply these together, we can find that $(c,1) \cdot (c’,1) = (c\cdot c’,2)$. Note that what the server really has is $(m \cdot m’)e^2$. When the server gives this value back to the client, it will give back $(c\cdot c’,2)$, which is telling the client that there are two $e$s in the product. Therefore, it can simply multiply $c\cdot c’$ by $e^{-2}$ to get $m \cdot m’$. Now what if the computation didn’t end there? What if the server had three ciphertexts, $c_1,c_2,c_3$, and it wanted to compute $c_1\cdot c_2+c_3$. First it would compute $c_1 \cdot c_2 = (c_1c_2,2)$. Now it wants to compute $(c_1c_2,2) + (c_3,1)$. In order to do this, it has to compute $c_3\cdot e$ to get $(c_3,2)$, and then it can just do $(c_1c_2,2) + (c_3,2)=(c_1c_2+c_3,2)$. When the server gives this value back, the client can simply multiply by $e^{-2}$ and have $m_1m_2+m_3$.

Part Two

To actually find a field where we can’t compute the inverse is difficult. The solution I came up with (which I’m not so confident of), is to leverage the fact that you can only compute inverses in $\mathbb{F}_p$ if you know the order of the field. Otherwise it’s impossible. Therefore, the client could be working with the integers $\mod p$, but it would never tell this to the server. Then, it would pick some random $e$, compute $m\cdot e \mod p$, give it to the server, and the server could do all of its computations with the number. If the result of the computation is $R$, the server can simply give back $(R,n)$ to the client (where $n$ is the amount of $e$s), and then the client could simply compute $R e^{-n} \mod p$ to get the answer. The reason why this works is because modulo-ing is fully homomorphic; you can do it in the middle of the computation, at each step of the computation, or simply just do it at the end. In essence, the client does the modulo in the beginning, masking $m$, and it then lets its servers do computations on it. When it gets back the result, it just computes the modulo. This would be equivalent to the server doing all the computations in modular arithmetic the entire time, but we accomplish this without telling the server what $p$ is. Unfortunately, this is inefficient because these numbers could grow to have arbitrarily long lengths. In order to fix this problem, the client could compute some other prime, $q$, during the initialization phase, and then compute $N=pq$. The client gives $N$ to the server (note that by the RSA assumption this reveals nothing about $p$). Then, the server could do all of it’s computations modulo $N$, and thus it wouldn’t have integers that grow up to an arbitrarily long size. The reason this works is that since $N$ is a multiple of $p$, if $x \equiv a \mod N$, then $x \equiv a \mod p$ (check out the comment on this post, which is what gave me the inspiration for this idea).

Computing the inverse of something $\bmod N$ is not particularly hard unfortunately. In particular, $x^{-1}\bmod N$ is the value in $\mathbb{Z}_N$ such that $xx^{-1}\equiv 1\bmod N$. Note that if we knew integer $a, b$ such that

$$aN + bx = 1$$

then $x^{-1}\equiv b\bmod N$. This is because the above equation $\bmod N$ is $ bx\equiv 1\bmod N$, so $b$ is "the thing that multiplies with $x$ to get 1 $\bmod N$", i.e. its inverse.

How might we get $a, b$ such that $aN + bx = 1$? The extended euclidean algorithm will give us $a, b$ such that $aN+bx= \mathsf{gcd}(x, N)$. Unfortunately, $x$ being invertible $\bmod N$ is equivalent to $\mathsf{gcd}(x, N) = 1$, so the extended euclidean algorithm computes inverses $\bmod N$, and breaks your cryptosystem quite efficiently (it is something like $O((\log N)^3)$ iirc).

If the message $m$ is unknown and the value of $e$ is also unknown, then if $c=me \mod n$, then without knowing the value of $e$ (and by definition we don't know the value of $m$ otherwise no need to decrypt), the message can't be easily retrieved, since c can be factored phi(n) ways.

One problem with this type of scheme is a chosen plain text attack.

If you encrypt a message k (known to you) this way, then $c=ke$, thus $ck^{-1}=e$ and hence $e$ can be discovered since you know $k$ and $c$. You would need to use a randomly chosen e for each encryption to prevent this easy attack.