SPDZ-如何進行安全的小於比較

SPDZ 論文解釋瞭如何使用 SPDZ 協議來查找秘密值的和/積，以及如何找到秘密值和非秘密值的和/積（第 6 頁）。

該文件似乎說，您可以從中進行任何其他操作。您將如何使用它來進行安全的小於比較？

Bristol SPDZ 實施教程程序（第19 行）表明，他們的實施有一種安全地比較兩個秘密值以獲得秘密結果的方法。他們是如何實現的？報紙上好像沒有。

目前在 SPDZ 中執行此操作的方式是使用允許截斷秘密共享值的原語 $ [s] $ 通過一個眾所周知的權力 $ 2 $ .

您可以在此處查看程式碼。

在 SPDZ， $ k $ 位整數在範圍內 $ (-2^{k-1},2^{k-1}) $ . 它們表示為 $ x \mapsto x $ 反對 $ p $ . 所以每一個數字 $ x \in [2^{k-1},2^{k}) $ 被認為是負數。

如果我們有截斷，從高層次的概述，我們可以計算 $ [a] < [b] $ 作為秘密值：

1. 分配 $ s \leftarrow ([a - b]) $ 本地看 $ [s < 0] $ .
2. 表示 $ k $ 作為位長 $ s $ . 拿 $ r \leftarrow [s/2^{k-1}] $ 有輸出 $ [0] $ 或者 $ [1] $ 取決於符號 $ s $ . 由於符號保留的一些技術性，輸出在實踐中 $ [0] $ 或者 $ [-1] $ .
3. 為了標準化結果，輸出 $ 0 - [r] $ . 這再次在本地完成。

這里昂貴的部分是步驟 $ 2 $ 因為各方必須進行通信才能實現截斷。

如果您想查看詳細資訊，您可以找到具體的協議（ $ 3.2 $ , $ 3.3 $ ) 在頁面上 $ 7 $ 在這裡。

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