Multiparty-Computation
MPC中計算模逆的算法
是否有任何已知的計算算法 $ a^{-1} \pmod{q} $ ， 在哪裡 $ q < p $ 和 $ F_{p} $ 是 MPC 的素數域，線上性秘密共享方案中？
我嘗試使用標準算法，各方在其中生成 $ r $ ，然後對共享值執行安全乘法以獲得 $ r⋅a $ 並打開它，然後每個本地反轉結果。最後，每個都使用其份額的局部標量乘法 $ r $ 獲得股份 $ a^{-1} \pmod{q} $ . 但是，當逆域與 MPC 域不同時，這不起作用。
一般來說： $ a^{-1} \equiv a^{\phi (q)-1} \pmod q $ 在哪裡 $ \phi $ 是歐拉函式。如果 $ q $ 是素數，那麼 $ \phi (q)=q-1 $ 因此 $ a^{-1} \equiv a^{q-2} \pmod q $ .
最近，這裡已經完成了一種對通用欄位或環進行共享轉換的方法。基本上，本文提供了一種轉換共享的解決方案 $ a \in F_p $ IE $ [a]_p $ 分享 $ a \in F_q $ IE $ [a]_q $ .
如何？生成一些隨機位 $ [b]_p, [b]_q $ 這在兩個領域都是一樣的——使用剪切和選擇。從 $ [a]_p \rightarrow [a]_q $ 請執行下列操作：
- 屏蔽您的輸入 $ \log{p} $ 隨機位並設置 $ m \leftarrow \mathsf{Open}\big( [a]p - \sum{i=0}^{\log{p}}2^i[b_i]_p \big) $ .
- 拿 $ m $ 作為對您的公共輸入 $ F_q $ 共享算法並執行減法模 $ p $ 但這次在 $ F_q $ 使用雙共享隨機位。更正式地說，計算 $ [a]q \leftarrow \big( m + \sum{i=0}^{\log{p}}2^i[b_i]_q \big) \bmod p $ .
不過有一個警告。為了獲得適量的統計安全性並使打開的值看起來均勻隨機，您需要 $ p $ 和 $ q $ 接近於 $ 2 $ .
要回答您的問題，只需轉換 $ [a]_p \rightarrow [a]_q $ 然後做反轉 $ [a]_q \rightarrow [a^{-1}]_q $ 正如你所描述的。