What is the flaw in this model for homomorphic encryption?

Question

Imagine a Field Isomorphism $g : \mathbb F1 \to \mathbb F2$ given by some $g(x)$

Assume a client is planning to outsource his computations to server, translates every possible $x$ as $g(x)$ and sends to server and once he gets the result he translates g inverse to get the answer.

I know the above is straw man solution for Homomorphic encryption, but am being naive to think of possible problems with such model. One problem I could think of is simple frequency analysis would break the system (but this can be mitigated by coming up padding schemes that retain the homomorphic nature), but what are others?

The catch here is , Most of the current homomorphic encryptions are trying to encrypt the data and perform operations on the encrypted data, but here instead of encrypting it , just the input set is transformed to a another field and such mapping $g(x)$ is kept secret.

Answer 1

The last paragraph of Section 2.3 of Gentry's "easy" intro to homomorphic encryption, I believe, contains an important result which applies to your model.

Researchers [1, 8] showed that if $\mathcal{E}$ is a deterministic fully homomorphic encryption scheme (or, more broadly, one for which it is easy to tell whether two ciphertexts encrypt the same thing), then $\mathcal{E}$ can be broken in sub-exponential time, and in only polynomial time (i.e., efficiently) on a quantum computer.

Where 1 is Algorithms for black-box fields and their application to cryptography and 8 is Quantum algorithms for some hidden shift problems.

Since your isomorphism is deterministic, this would most definitely apply. Granted, just because it can definitely be broken in sub-exponential time does not mean there is no hope (RSA can be broken in sub-exponential time), you are going to have to give a very good hardness proof to get anyone to use your system.

Answer 2

The first problem with your ring homomorphism is that it is not an isomorphism, as $g(0) = g(2) = g(4) = g(6) = g(8) = 0$ and $g(1) = g(3) = g(5) = g(7) = g(9) = 5$, and thus division by $5$ does not recover the original data.

The second problem, of course, is that the homomorphism is not secret - you need a huge selection of possible homomorphisms (actually isomorphisms, if you want to be able to decrypt again), from which one is selected as random.

In the example ring $\mathbb Z_{10}$, multiplication by $1$, $3$, $7$ or $9$ are additive isomorphisms, i.e. they allow $g(x+y) = g(x) + g(y)$. But these are (other than the trivial one) not multiplicative homomorphisms: $(3·x)·(3·y) = 9·(x·y) \neq 3·(x·y)$.

So, we need more complicated rings which allow a non-trivial amount of different isomorphisms, and useful encodings of the data into these rings, and encoding of the operations we actually want to do to into multiplications and additions.

Answer 3

Homomorphic encryption schemes are a subset of public key schemes. A public key cryptosystem is 3 algorithms: encryption, decryption and key generation with the property D is the inverse of E. The first and last must be computable quickly by anyone but decryption may only be computed quickly by those that know the key. In this case E and D are supposed to be the isomorphism and its inverse and the public key is F2. You want to keep E and D secret but that renders the scheme useless as a way of outsourcing computations since the receiver of the ciphertext can only do operations on the ciphertext. For example, if the receiver's job is take an encrypted message from the sender and modify it to the encryption of that message plus 1 there is no way for him to do that since he doesn't know what the encryption of 1 is, or any other message for that matter.

If E and D are not secret then it becomes an issue of finding the right fields to use and the right data to add to the public key. How the field is encoded is also important. For finite fields for example there are several ways to describe the fields. For all the typical encodings of finite fields, given an explicit isomorphism it is easy to find an inverse for it, so in this case there is no way that any modification of what you have proposed can work.

Answer 4

Considering your isomorphism $g:\mathbb F1\mapsto \mathbb F2$ there is the question of resources for computation. Most Fully Homomorphic systems are resource intensive, which affects their practicality.

In the case of $g:\mathbb F1\mapsto \mathbb F2$ I believe the complexity of the computational problem depends on the \$mathbb F1,\mathbb F2$ you choose.

For example, if you choose $\mathbb F1, \mathbb F2$ to contain $2^{64}$ numbers, they would be big enough to cover any number that can be stored as an integer in modern Linux or Windows systems. One could of course imagine a mapping $g:\mathbb F1\mapsto \mathbb F2$ such that each different number in $\mathbb F1$ was mapped to a different number in $\mathbb F2$.

Such an approach could be very strong but - we would need to prove that the mapping can support the homomorphic requirements - we would need to compute the mapping, which may require a huge table of size $C*2^{64}$ (C being some constant).

This is just an example, an illustation. What I am saying, more generally, you have a trade off between complexity and practicality. That is very typical of homomorphic encryption. It is the main difficulty (IMO) in bringing H.E. to the real world problems.

Answer 5

I don't understand. Are you trying to achieve homomorphic encryption scheme that is not public key encryption because definitely your scheme is not a public key encryption scheme. You are keeping your homomorphism "secret" which limits its applicability by large. The idea of public key encryption is to make the encryption key public.