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