[osaariki]

This is not how this works. Homomorphic encryption (HE) is best thought of as a software CPU that gives you ways to mutate data (but not read it without the secret key of course). Any computation you run has to be using the instruction set offered by HE: addition, multiplication or rotation. When you do an operation on two ciphertexts, you get a new ciphertext back, but no information on its contents.

Now the way you do machine learning here is by translating your model to use the instructions offered by HE. You've effectively recompiled the model to a new architecture.

If you'd like to read more about machine learning with homomorphic encryption, we published a paper on our CHET compiler [1]. I also talk about this space on a high level in this MSR podcast episode [2].

[1]: https://www.cs.utexas.edu/~roshan/CHET.pdf [2]: https://www.microsoft.com/en-us/research/blog/he-compilers-f...

[mcguire]

Quick question: If you have control of the computation instructions (the software for your HE CPU), can arrange for a leak of information from the encrypted data?

[KenoFischer]

In a properly functioning HE scheme, the party doing the evaluation cannot obtain information about the encrypted data, even if they do the operation incorrectly. Without further measures, they can of course compute an incorrect value, which depending on the larger protocol can sometimes be an issue (e.g. consider the scenario where after decryption the client shares the prediction with the server for some reason - in that case, if the server sends the original image ciphertexts, instead of predictions, they can trick the client into decrypting the original image). There is also always the risk that whoever is choosing the instantiation of the cryptoscheme knows something you don't and picks weak parameters, but that's just all the usual attack modes on cryptographic schemes.

[osaariki]

As other posters already mentioned, there's no control flow in the HE instruction set. This is actually one of the reasons neural networks are a great fit for HE, as they often have fixed data access patterns and no control flow.

[Dylan16807]

The software can only do arithmetic in a fixed pattern, no "if" statements or while loops or anything. Any conditionals have to be faked with arithmetic.

So, since the arithmetic is secure (otherwise it wouldn't be HE), and the entire runtime pattern is fixed up front and made of nothing but arithmetic, there's no way to leak anything.

[garganzol]

This gives a whole new look to lambda calculus and Lisp concepts that promote to represent everything as a (preferably pure) function.

If the whole logic can be expressed as a pure function without conditionals then it would fully fit into HE.

But what if we want conditionals?

Comparison operators like (a < b), (a > b), etc go out of the question immediately as they would allow to guess the values by a simple binary search.

Equality operation (a == b) seems plausible from the security standpoint as it would not reveal the encrypted value. But there is a challenge in performing that operation because both of its arguments may be encrypted with different randomization. To overcome this, probably some neat trick could be performed but... this is the question of the future.

EDIT: Here is an idea. Some FHE engines have pre-encoded values for some magic numbers like 0, 1 and -1.

What if the equality operation p(a, b) = (a == b) is performed like this:

p(a, b) = (a + (b * -1)) == 0

Does anyone have an intuition regarding the feasibility of the proposed trick in something like Microsoft SEAL? Do both left and right parts of the comparison would have the canonicalized randomness making the equality operation possible?

P.S. On a side note, the sheer existence of an equivalence operation in FHE scheme would decimate its security by allowing to plant bruteforce attacks with a lower guesswork. Not a catastrophe by any means, and some systems would prefer that as a small price to pay for having conditionals in a program.

[kortex]

Have you looked at reversible computing? The ideas are only vague in my mind at the moment, but the fragments are there. Disclaimer: out of my wheelhouse. Any conditional statement will throw some information away, "knowing" a==b means provably you have less complexity. Not a good look for encryption.

But instead let's say you have some register which gets rotated/xor'd in some way based on the relationship of a to b.

I don't think you can do branching logic though.

[garganzol]

Good suggestions, thank you.

> I don't think you can do branching logic though.

You can. If we would be able to introduce a special equality operator, let's call it SEQ that works like so:

SEQ(a, b) = 1 when a == b; SEQ(a, b) = 0 when a != b

Then we would be able to do conditionals by discarding the result of unmatched branch by multiplying it by 0.

Thanks to the fact that all HE calculations are pure, no observable side effects would be produced.

For example, here is a simple program with a conditional statement:

P(x) = x == 10 ? 42 : sin(x)

This is how it may look in HE domain:

P(x) = SEQ(x, 10) * 42 + (1 - SEQ(x, 10)) * sin(x)

No branching is involved here but the result is equivalent to a program with branching. Eureka!

Once again, thank you for the fruitful suggestions.

EDIT: by the way, it paves the way for implementing > and < operators as well due to the fact that operator result remains in encrypted domain. This is a serious wow moment.