Comment by alexey-salmin
2 years ago
> For example, it is not be possible to write an FHE program that uses fewer instructions than the program’s worst-case input. Doing so would reveal information that the input is not the worst-case, which contradicts the security of the cryptography. Instead, an FHE program must eagerly compute all branches of if-statements, and then use a select statement to decide which result should be used.
What exactly is "select statement"? Curious to know how to select a value without giving away what this value equals to (even in encrypting form). Otherwise I assume it would give away as much as seeing which branch was taken.
A select statement, in this case, looks like a ternary in C, "y = (x > 0) ? 1 : 0". In FHE with integers, it's evaluated by making a large polynomial all x <= 0 become 0 and all x>0 become 1. Once you have y, you evaluate both halves of the if-then but multiply one result by y and the other by (1-y). Then add them.
Cf. https://llvm.org/docs/LangRef.html#select-instruction
No branching, and the hard part in FHE is to evaluate this when the bit is encrypted. The results are the same type, so all you see after the op is that the result is a ciphertext.
Unrelated, but have you heard of Distributed Computing Through Combinatorial Topology? Seems up your alley.
Distributed Computing Through Combinatorial Topology: https://www.amazon.com/Distributed-Computing-Through-Combina...
This seems up my alley, but I suspect the techniques in that book aren't used, since I have spent a lot of time chasing down applications of computational topology only to find they weren't as useful as advertised.
Are you aware of anyone who uses these methods? Would be good for my book Practical Math
1 reply →