MPC中二進制小於的算法

給定二元股份 $ [a_{l-1}]_p,…,[a_0]p, [b{l-1}]p,…,[b_0]p $ 這樣 $ a = \sum{i=0}^{l-1} a_i2^i,b = \sum{i=0}^{l-1} b_i2^i $ 為了 $ a,b \in Z_p $ , 如何計算 $ a \overset{?}{\lt} b $ 在 MPC 中（結果未關閉）？

找到位置 $ a $ 和 $ b $ 的位不同： $ c_i=a_i\oplus b_i=a_i+b_i-2a_ib_i $

計算部分或和： $ d_{l-1}=c_{l-1},\quad d_i=d_{i+1}\vee c_i=a_i+b_i-a_i b_i $

隔離第一個不同的位： $ e_{l-1}=d_{l-1},\quad e_i=d_i-d_{i+1} $

結果是相應的位 $ b $ : $ \sum e_i b_i $

這是關於如何實現這一目標的一個很好的參考。等式、比較、位和求冪的無條件安全常數輪多方計算 $$ pdf is here $$. 這與@ngn的答案基本相同

引用自：https://crypto.stackexchange.com/questions/64408