3 ms·

> 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

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

j2kun 2y ago
Cf. https://llvm.org/docs/LangRef.html#select-instruction 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.
- sn9 2y ago
  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-Combinatorial-Topology/dp/0124045782 https://www.amazon.com/Distributed-Computing-Through-Combina...
  - j2kun 2y ago
    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
    - sn9 2y ago
      I've only skimmed my way through it, but it seems like the bulk of the research started in 2000 so it would be fairly new. It might still be just academic research at this point, but it at least seems to show some pretty interesting abstractions with which to analyze systems. It came out in 2013, so if it is used in industry after that point, the book wouldn't say and you'd have to go hunting for whitepapers that cite the research probably.
adolgert 2y ago
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.

j2kun 2y ago

Cf. https://llvm.org/docs/LangRef.html#select-instruction 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.

sn9 2y ago
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-Combinatorial-Topology/dp/0124045782 https://www.amazon.com/Distributed-Computing-Through-Combina...
- j2kun 2y ago
  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
  - sn9 2y ago
    I've only skimmed my way through it, but it seems like the bulk of the research started in 2000 so it would be fairly new. It might still be just academic research at this point, but it at least seems to show some pretty interesting abstractions with which to analyze systems. It came out in 2013, so if it is used in industry after that point, the book wouldn't say and you'd have to go hunting for whitepapers that cite the research probably.

adolgert 2y ago

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.