Homomorphic & Functional encryption: Mapping unencrypted outputs to encrypted outputs using existing data

Question

Let's assume I have datapiece A which, after being put through a model or neural network, has a known output X in the unencrypted space. When I move datapiece A into an encrypted space, and put it through an encrypted model, it becomes datapiece e-A. Now, it has output e-X. In this way, I am using a known (unencrypted) data to map X into the encrypted space (e-X).

The model in the unencrypted space has only two possible outputs: X and Y. When I encrypt this model, I'd like there to still be only two possible outputs: e-X and e-Y.

When someone else sends me an encrypted input data, datapiece e-Unknown, I plug it into the function, and I also get output e-X. Since datapiece e-unknown produces e-X in the encrypted space, can it be assumed that datapiece-Unknown also produces output X in the unencrypted space? In other words, does the map from the first paragraph enable deciphering outputs for the anonymized input datapiece-Unknown? Assume datapiece unknown and datapiece A are different (i.e. not exactly the same).

Eval(Enc(f),Enc(dA))=Eval(Enc(f),Enc(dU))⇒f(dA)=f(dU)

where Eval(f,c) stands to "apply f homomorphically to the ciphertext c" .... "f" is the model, "dA" is datapiece-A, "dU" is datapiece-unknown.

If this can be done without encrypting the model, that would also work.

Eval(f,Enc(dA))=Eval(f,Enc(dU))⇒f(dA)=f(dU)

---

For an unusual use case, I want this to be true. How can I make it work?

Does this hold true for homomorphic encryption? Since h.e. is probabilistic, are there any tricks to make it hold true for homomorphic encryption (e.g. re-seeding with each new input)? If not, why? I am asking specifically about H.E. because a number of libraries already exist that make it easy to use.

Does this hold true for functional encryption? I have heard it does, but there are not many libraries available for functional encryption.

Answer 1

Actually, what you asked is not unusual, even more, it is always true.

Since $Eval(f, Enc(dA)) = Enc(f(dA))$ and $Eval(f, Enc(dU)) = Enc(f(dU))$, if $Eval(f, Enc(dA)) = Eval(f, Enc(dU))$, then $ Enc(f(dA)) = Enc(f(dU))$.

Now, if you use the decryption algorithm in both sides, you get $f(dA) = f(dU)$.

The same argument applies if we use $Enc(f)$ instead of $f$.

The point now is whether this information is useful or not, because the probability that $Eval(f, Enc(dA)) = Eval(f, Enc(dU))$ is very small: even if $dA = dU$, you are supposed to have $Enc(dA) \not = Enc(dU)$, therefore, the evaluation algorithm is likely to give you different outputs.

So, you would probably never see this event and, consequently, you would not be able to use the conclusion (the right side of the implication).

Answer 2

I will talk about HE here, since I am not much aware of FE.
If you look at Somewhat Homomorphic Encryption schemes, say Lauter et al's scheme in "Can Homomorphic Encryption be Practical", you will find that the cipertext, e-X in you case, has 2 components, one of which depends on the message and the second does not depend on the message (A here).
Now, let us see if it is possible for a B (not equal to A) to encrypt to the same cipertext. If you look at the above mentioned SwHE algorithm, you will realize that it is simply not possible to get A and B encrypt to same cipertext, e-X, after applying the function (* Given that the function in bijective *).
So, if the function is bijective, then A = B. And definitely e-X will always decrypt to X.

Answer 3

Functional encryption and homomorphic encryption are best pals. An MIT paper, "On the Relationship between Functional Encryption, Obfuscation, and Fully Homomorphic Encryption" provides an excellent background.

In Randomized Functional Encryption, an encryptor is able to hide an input within a ciphertext in such a way that authorized decryptors can only recover the result of applying a randomized function to it.

This is almost word-for-word what you are asking about: Creating environments where outputs from functions can be decrypted, without decrypting the inputs.

However, your bounty states:

I would like the bounty winner to provide a reason why existing homomorphic encryption libraries couldn't be used in this manner by removing the probabilistic nature of their functions.

The easiest way to map outputs like you described may be to turn existing homomorphic encryption algorithms into probabilistic ones. Instead of using a time-dependent value for the leading string, just a hash of the data that you're encrypting. See the answer in Partially Homomorphic Cryptographic Schemes - Deterministic vs Probabilistic.

In your random oracle model, you describe the following:

When someone else sends me an encrypted input data, datapiece e-Unknown, I plug it into the function, and I also get output e-X. Since datapiece e-unknown produces e-X in the encrypted space, can it be assumed that datapiece-Unknown also produces output X in the unencrypted space?

It is possible that if every encrypted part of your algorithm uses the same random salt (or hash), shared between the model-runner and the data-donator, then you could create a data obfuscation system that somewhat works. But, it is pretty insecure, as the model-runner would only need to conduct a bunch of hashes on your data to figure out its true input. At that point, it is really a lot of computational power for almost no improvement.