選擇一個與一堆其他秘密數字不同的隨機數
我正在尋找一種算法，其中n 個參與者每個人都有不同的密碼 $ [0..x] $ （以及在哪裡 $ x $ 是已知的），然後參與者在其中隨機選擇另一個非秘密數字 $ [0..x] $ 不得與任何參與者的秘密發生衝突，不得洩露任何參與者使用的任何號碼。
每個參與者都有一個秘密號碼，並且沒有兩個參與者有相同的號碼是給定的。
不需要證明參與者誠實行事。您可以假設各方是半誠實的（即他們不會偏離協議）。
因此，例如（這部分我不感興趣）：
- 愛麗絲有號碼 $ 18 $
- 鮑勃有號碼 $ 52 $
- 夏娃有號碼 $ 193 $
此時每個參與者都知道：
- 自己的號碼
- 每個參與者都有不同的號碼
- 每個參與者只知道自己的號碼
考慮到作為我們的起點，現在 Alice、Bob 和 Eve 必須達成共識，允許在它們之間隨機選擇一個（並且只有一個）公眾號 $ [0..200] $ ，這不會與三個私人號碼中的任何一個發生衝突，也不會透露任何參與者的私人/秘密號碼的任何資訊。
有沒有一種實用的算法可以做到這一點？我所說的“實用”是指今天可以使用並且可以在非常合理的時間內執行的東西。
也許一些同態方案？
你可以假設 $ x $ 會很小而且 $ n<x $ ， 但不幸的是 $ n $ 將足夠大，以至於隨機數很可能與某些參與者的秘密號碼發生衝突。換句話說， $ n/x $ 是一個比較大的分數。
我認為這會起作用，儘管它是否實用是另一回事。對於大 $ x $ 不會的。它基本上是mental-poker的一個應用程序。
首先，選擇一種不易受到已知明文或選定密文攻擊的安全交換加密算法。
- 每個人都會生成一個隨機加密密鑰。
- 除了 Alice 之外，每個人都使用他們的密鑰來加密他們的唯一秘密號碼。
- Alice 使用她的密鑰加密列表中的每個項目 $ [0,…,x] $ ，除了她自己的號碼。然後她洗牌。
- 每個人都將他們加密的密碼/列表傳遞給下一個人（例如順時針方向），後者對其進行加密，當他們擁有列表時將其洗牌。重複直到所有的數字和列表都傳完。此時，Alice 的列表和其他所有人的號碼都已被所有人加密。
- 從列表中刪除所有加密號碼。由於加密是可交換的，每個加密後的數字都會在列表中匹配到自己，但是因為每個人都已經打亂了列表，所以他們不知道這些數字最初是什麼。
- 從列表中選擇第一個數字。讓每個人都用他們的密鑰解密它並傳遞結果，直到他們完成一整輪。現在每個人都應該有相同的隨機數，他們可以通過比較他們的結果來驗證。
（如果該號碼只被解密一次，最終的解密者可以作弊並選擇任何號碼，希望它與其他號碼不匹配。）
即與您的範例值：
- 愛麗絲：鑰匙 $ a $ ，鮑勃： $ b $ ，夏娃： $ e $
- 鮑勃： $ E_b(52) $ ，夏娃： $ E_e(193) $
- 愛麗絲： $ [E_a(0), … E_a(17), E_a(19), … E_a(200)] $ ，洗牌。
- 愛麗絲 $ \mapsto $ 鮑勃： $ [E_a(i), …] $ ，鮑勃： $ [E_b(E_a(i)), …] $ ，洗牌。
鮑勃 $ \mapsto $ 前夕： $ E_b(52) $ ，夏娃： $ E_e(E_b(52)) $ .
前夕 $ \mapsto $ 愛麗絲： $ E_e(193) $ ，愛麗絲： $ E_a(E_e(193)) $ .
愛麗絲 $ \mapsto $ 鮑勃： $ E_a(E_e(193)) $ ，鮑勃： $ E_b(E_a(E_e(193))) $ .
鮑勃 $ \mapsto $ 前夕： $ [E_b(E_a(j)), …] $ ，夏娃： $ [E_e(E_b(E_a(j))), …] $ ，洗牌。
前夕 $ \mapsto $ 愛麗絲： $ E_e(E_b(52)) $ ，愛麗絲： $ E_a(E_e(E_b(52))) $ . 5. 現在名單， $ E_a(E_e(E_b(52))) $ 和 $ E_b(E_a(E_e(193))) $ 可以顯露並且移除 Bob 和 Eve 的號碼。由於加密是可交換的， $ E_a(E_e(E_b(52))) $ 將匹配 $ E_e(E_b(E_a(52))) $ 列表中的某處，也會 $ E_b(E_a(E_e(193))) $ . 6. 每個人都取列表中的第一個數字，比如說 $ E_e(E_b(E_a(42))) $ . 他們每個人都解密它，例如 Bob： $ D_b(E_e(E_b(E_a(42)))) = E_e(E_a(42)) $ . 他們像在第 4 步中一樣傳遞它們，因此最終例如 Bob 得到 $ E_b(42) $ ，他可以解密並宣布，與 Alice 和 Eve 的結果相比。