3 ms·
Sorting doesn't need any branches. For FHE you need to think like a circuit designer without indexing operations. In that situation your default sort is a sor
by Dylan16807 2mo ago
Sorting doesn't need any branches. For FHE you need to think like a circuit designer without indexing operations. In that situation your default sort is a sorting network, made out of nlogn conditional swaps.
- justincormack 2mo agocan you build a conditional swap in FHE in a small size though? FHE is always circuit like, ie no dynamic control flow anyway I think?
- Dylan16807 2mo agoOnce you calculate which value is smaller, the conditional swap itself is trivial. Let's say inputs A and B, comparison result is a boolean C. Outputs X and Y. Bitwise: X = A&C | B&¬C, Y = A&¬C | B&C Arithmetic: X = A*C + B*(1-C), Y = A*(1-C) + B*C Edit: Or to put it another way, one of the most basic things you can make in a circuit is a multiplexer, and a conditional swap is two minimum size multiplexers next to each other.