3 ms·
Yes, but you can't branch on the result, because you don't know if the result is zero or not. So your program needs to have fixed control flow, i.e., you cannot
by giomasce 6y ago
Yes, but you can't branch on the result, because you don't know if the result is zero or not. So your program needs to have fixed control flow, i.e., you cannot implement arbitrary programs.
- dlubarov 6y agoThere isn't branching in the traditional sense, but we can work around it. Instead of doing result = if condition { a } else { b } in circuit programming, we normally do result = condition * a + (1 - condition) * b
- giomasce 6y agoSure, that was already mentioned on another comment, but that's not enough for proper branching. You also need while loops. See also comment https://news.ycombinator.com/item?id=24018284 https://news.ycombinator.com/item?id=24018284.
- heavenlyblue 6y agoIf you constrain your computer to always take the same amount of time to execute any while loop (which a homomorphic computer needs to do not to leak any data), your computer would also have unbounded circuitry complexity and thus it’s not any better. Also unbounded loops can’t practically finish even on a Turing machine :)
- giomasce 6y agoThat's my point: not any Turing machine can be implemented with FHE, because FHE must have bounded execution time.
- heavenlyblue 6y agoYou can either say “a Turing machine can not be implemented” or “it can” but never “not any Turing machine” because there isn’t any types of a Turing machine - just a single one.
- heavenlyblue 6y agoYou don’t need to branch, you execute both branches at the same time.