Multiparty-Computation
MPC 中的 LSB 提取：對正確性的懷疑
我懷疑以下用於安全多方整數計算的改進基元論文中的 LSB 提取協議（表示為 Mod2）是否正確。澄清將不勝感激。
上面的協議在第 1 行呼叫**PRandM(k, 1)**來生成隨機共享值 $ r’’ $ 和 $ r’_0 $ （它忽略 $ r’ $ ) 然後在第 2 行中使用它們來致盲 $ a $ 然後揭示它以提取盲值的 LSB，然後計算隨機秘密共享值 $ a_0 $ .
協議 $ looks $ 正確，因為 LSB 的 $ c $ 本質上是 $ r_0\oplus a_0 $ 然後在第 3 行中，我們再次對它進行異或 $ r’_0 $ .
那就是……萬一 $ 2^{k-1}+[a]+2\cdot [r’’]+[r’_0] $ 不會溢出素數域 $ p $ . 當它溢出素數域時，LSB 翻轉，然後數學不再正確。
我們也不知道是否 $ c $ 是否溢出，因為 $ [a] $ 可 $ p-1 $ 在那種情況下 $ c $ 會大於 $ 2^{k-1} $ .
知道我在這裡缺少什麼嗎？
該協議僅設計為在以下情況下工作 $ a $ 在範圍內 $ {-2^{k-1},\dots,2^{k-1}-1} $ . 這確保了 $ c $ 不會溢出模組 $ p $ ， 只要 $ p $ 足夠大。
在論文中，他們通過選擇確保這一點 $ p > 2^{k+\kappa+\log n} $ ， 在哪裡 $ \kappa $ 是一個統計安全參數，並且 $ n $ 是當事人的數量。請參閱第 3-5 頁的討論。