Algorithm-Design

是否有一種算法可以在各方之間安全地分配元素?

  • October 2, 2019

假設我們有一組數字 $ n = { 1, 2, 3, 4, 5, \ldots } $ 和 $ m $ 球員( $ m < \operatorname{sizeof}(n) $ , 當然)。

我想知道是否有適合所有人的方法 $ m $ ’s 從中選擇不同的數字 $ n $ 在某種程度上,它不會透露他們選擇了哪個或其他人選擇了哪些。

這是可行的。假設所有各方都是半誠實的,並且您有一個公鑰加密方案允許門檻值密鑰生成和門檻值解密以及重新加密,即:

  • $ keyGen(\lambda,m) $ :給定安全參數 $ \lambda $ 和一個整數 $ m $ , 輸出一個公鑰 $ pk $ 和 $ m $ 密鑰的份額,每個份額給一個玩家(每個玩家只知道自己的份額)。秘鑰是 $ sk $ 和 $ i $ -th 份額是 $ s_i $ .
  • $ Enc(pk;m,r) $ : 加密 $ m $ 隨機 $ r $ , 使用公鑰 $ pk $ .
  • $ Dec((s_1,\cdots, s_m);c,i) $ : $ m $ 玩家共同解密一個密文c,並將其輸出到 $ i $ - 方。
  • $ Reenc(pk;c,r) $ : 給定 $ c=Enc(pk;m,r’) $ , 用隨機數重新加密 $ r $ ,因此輸出是原始明文的有效密文(即 $ Enc(pk;m,r’’) $ ).

Elgamal 滿足上述要求。

然後玩家執行以下操作:

  1. 他們跑 $ keyGen $ 共同獲得公鑰和秘鑰份額。
  2. 第一位選手 $ P_1 $ 加密每個 $ n $ 數字,隨機排列密文列表,將排列後的列表傳遞給 $ P_2 $ .
  3. 然後 $ P_i $ 重新加密它收到的列表中的每個密文並隨機排列列表,並將排列後的列表傳遞給 $ P_{i+1} $ .
  4. $ P_m $ 重新加密它收到的列表中的每個密文並排列列表,並發布最終列表。
  5. 每一方在列表中選擇不同的密文。
  6. 從 $ i=1 $ 至 $ m $ ,玩家共同解密 $ P_i $ 的密文並將其透露給 $ P_i $ .

如果各方是惡意的,則需要有零知識證明以確保各方遵守協議。

引用自:https://crypto.stackexchange.com/questions/74763