4
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ What do you mean by output of a datapiece? How does the datapiece A (a bit string?) have an output X? Is A a function? Or are you fixing some function $f$ that is used in the whole scenario? $\endgroup$ – Hilder Vítor Lima Pereira Jul 18 '18 at 9:12
  • $\begingroup$ After datapiece A is put through an ML model (e.g. a neural network), it produces output X. Thanks for the question comrade $\endgroup$ – nick carraway Jul 18 '18 at 14:49
  • 1
    $\begingroup$ Okay. Now it is clear. You would like to have the following implication when using homomorphic encryption: $Eval(f, Enc(m_0)) = Eval(f, Enc(m_1)) \Rightarrow f(m_0) = f(m_1)$, where $Eval(f, c)$ stands to "apply $f$ homomorphically to the ciphertext $c$". $\endgroup$ – Hilder Vítor Lima Pereira Jul 18 '18 at 16:50
  • 1
    $\begingroup$ Yes! But, I am thinking that the model itself could also be encrypted at each bit. So, while your above equation would work, I think it is impossible. I think this is more realistic: Eval(Enc(f),Enc(m0))=Eval(Enc(f),Enc(m1))⇒f(m0)=f(m1).......... "f" is the model, "m0" is datapiece-A, "m1" is datapiece-unknown. $\endgroup$ – nick carraway Jul 18 '18 at 17:51
2
+50
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ May I add that if $Eval(f,\cdot)$ has non-negligible probability of collision for elements that have same image, this can be used to break the semantic security of the FHE scheme, unless $f$ is constant of course, or it is hard to sample two elements $x,y$ such that $f(x)\neq f(y)$. $\endgroup$ – Florian Bourse Jul 19 '18 at 9:05
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ I'm a bit confused about why you specify the structure of the ciphertext having 2 components? It seems it is not required to understand the following paragraph, which holds the answer to the question. $\endgroup$ – Florian Bourse Jul 19 '18 at 8:59
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.