在 MPC 的布爾電路中計算 INV

生成一個有效的 MPC 函式來計算是否可行 $ a^{-1} $ 為了 $ a \in \mathbb{F_q} $ ，用布爾電路？

天真的方法似乎是不可能的，因為可能需要提前知道計算的深度。（例如在擴展 GCD 的計算中）。

編輯：我對這個問題的意圖是：有沒有更多的方法來計算逆而不是使用 EGCD（即一種類似的方法來計算更適合轉移到 MPC 的 INV）

謝謝。

布爾電路是圖靈完備的，因此任何計算的答案都是肯定的。具體來說，對於這種情況，電路將假設循環永遠不會提前退出（如果它提前結束，那麼電路將不會改變結果）。通常，如果您需要計算電路中的一個分支，則該電路將始終具有兩個分支。

如果您的問題是關於效率的，那麼可能有比電路更有效的方法來計算它。例如，使用 MPC 計算 $ r\cdot a $ 在哪裡 $ r $ 是一個未知的隨機值。然後，雙方計算 $ b=(r\cdot a)^{-1} \bmod q $ ，然後安全地計算 $ r \cdot b $ . 這個結果是 $ a^{-1} \bmod q $ . 有很多方法可以做到這一點，使用同態加密（例如，Paillier）、OT 等。但是，如果您想要惡意安全，主要的挑戰是防止作弊。這還取決於您是在查看誠實多數還是不誠實多數設置。對於誠實的大多數人，只需使用標準技術來生成秘密共享 $ r $ . 然後各方對共享值執行安全乘法以獲得 $ r\cdot a $ 並打開它，然後每個本地反轉結果。最後，每個都使用其份額的局部標量乘法 $ r $ 和 $ b $ 獲得股份 $ a^{-1} \bmod q $ .

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