– 或者：如何在沒有莊家的情況下玩撲克

我知道這個問題很長，但這是一個關於共享秘密和多方計算的非常有趣的理論問題。

一般問題：“共享隨機生成”

考慮以下場景： $ N $ 當事人想玩一個簡單的遊戲。為此，需要產生一些隨機性（例如擲骰子、洗牌等；這兩種具體的秘密資訊將在本文的其餘部分中使用）。遊戲應該分散進行，即在某些中央伺服器上不需要“經銷商”；N 方中的任何一方都不應該是比其他方了解更多的“主人”（“秘密”）。

秘密需要在遊戲期間的某個時間點生成，然後進行修復，以使任何玩家都無法知道或仍然控制秘密（在生成之後）。應該有可能在遊戲過程中向單個玩家揭開秘密（想想從牌堆中抽出一張牌或在其他玩家隱藏的情況下查看骰子），當然也可以向所有玩家揭開。

假設有 $ N $ -到- $ N $ 給定的私人通信渠道（加密、驗證等），因此每個玩家都可以安全地與其他玩家通信。廣播機制可以單獨實現，也可以在對等通道之上實現。

擲骰子的解決方案

一個具體的場景可能是一個簡單的骰子遊戲，比如Mia（或 Liar’s Dice）。一名玩家在骰子盒中投擲兩個骰子。他可以在沒有其他玩家看到的情況下查看骰子。在某個時候，另一個玩家可以將骰子揭開到整張桌子上。實際的遊戲規則並不重要。重要的是，除了在骰子下面看的玩家之外，沒有人知道它們的價值。

解決方案可能如下所示：擲骰子（在現實世界中誰會擲骰子並不重要），每個玩家生成一個隨機整數，至少在範圍內 $ [0,6) $ . 骰子的值由這些整數的和模數隱式定義 $ 6 $ ，但沒有人知道這個結果。每個玩家現在生成一個隨機密鑰並使用像 AES 這樣的良好對稱加密來加密隨機整數。明文被附加或附加了一些足夠大的常數，因此不可能找到另一個將消息解密為稍後選擇的明文的密鑰（對於避免“後期操縱”很重要）。加密文本在所有玩家之間共享。只要是玩家 $ p $ 允許知道骰子的價值（當他被允許查看骰子盒時），所有其他玩家私下透露他們用來加密隨機數的密鑰。播放器 $ p $ 現在可以解密消息，驗證它們（通過查看前綴/附錄）並最終計算骰子的值。除了他，沒有人能做到這一點。為了向全桌揭開骰子，所有玩家都廣播了他們的密鑰。

要擲多個骰子，我們可以簡單地重複上述步驟（獨立地）讓所有骰子擲出。

洗牌

現在真正的問題是如何擴展這個想法來洗牌 $ M $ 卡片，例如 $ M = 32 $ 稅前。洗牌 $ M $ 卡正在尋找隨機 $ M $ -排列。一旦牌被洗牌，它們的順序就固定了。然後，每個玩家都可以從牌堆中抽牌；為簡單起見，想像一個遊戲，其中每個玩家按特定順序抽一張牌。當然，每個玩家都會向其他玩家隱藏自己的牌。

當第一個玩家抽一張牌時，這就像扔一個 $ M $ 雙面模具。然而，一旦第二個玩家抽一張牌，就只有 $ M-1 $ 剩下的牌，除了第一個玩家之外沒有人知道失去了哪張牌（所以這些牌有點依賴），所以即使扔一個 $ M-1 $ 雙面模具不能解決問題。這使得上面的方法在這裡不夠用（如果不是無用的話）。

另一種方法是所有 $ N $ 玩家隨機生成 $ M $ -排列。然後，甲板上牌的順序由這些排列的組成來定義。（想像在現實世界中，第一個玩家洗牌，然後第二個玩家再次洗牌；每個玩家都知道自己的排列，但不知道組成。）然後協議可以這樣工作：抓牌的玩家看到甲板上的索引（要抽的第一張牌：1，第二張牌：2，等等）；他需要應用逆最終排列；這可以通過一個接一個地應用每個單獨排列的逆來完成。但是他需要在一個特定位置向玩家詢問他們的秘密棋子（注意他最終應該只能看到一個卡，即僅在一個索引處評估逆排列）。最後一個被問到的玩家（首先洗牌的那個）然後知道抽到了哪張牌，打破了一個要求。

這兩個問題的細微差別在於，在抽牌時，“隨機事件”的結果是相互依賴的。一旦確定了第一張牌，就只有 $ M-1 $ 剩下的牌；從其中隨機選擇一張需要這張卡的知識。為了規避這一事實，我們需要一次性生成適當的排列，這在滿足公平遊戲要求的情況下似乎是不可能的。

目前沒有導致任何可用的另一個想法可能是生成 $ M $ 範圍內的隨機數 $ [0,M) $ ， 使用 $ M $ 不同的 $ M $ 面骰子，然後檢測並解決相同值的多次出現（如果存在這種情況，類似“共享散列”算法可能會有所幫助，即計算總和的散列（模 $ M $ ）使用多方計算）。

有人有解決這個問題的想法嗎？任何提示指向我正確的方向？

你可以使用門檻值加密和混合網路嗎？它可能不是世界上最快的東西，但它使用了眾所周知的組件。

設置

1. 每個玩家都會生成一個 ElGamal 密鑰對並證明他們知道他們的密鑰。聯合公鑰是所有公鑰的乘積。（如果您擔心重置攻擊，請查看“Pedersen 門檻值密鑰生成”以獲得更多涉及的版本）。
2. 任何人在聯合公鑰下創建數字 0 到 31 的加密，以及非互動式知識證明，這些證明確實是 0 .. 31 的加密。其他人都驗證證明。
3. 玩家輪流通過將混合網路應用於加密列表來洗牌。（Wikstrom 的“Verificatum”是我所知道的最快的混合網路。）每個人都驗證其他人的混合網路證明。結果是一個列表 $ L $ 32 張洗牌、重新隨機、加密的卡片。

繪圖卡

1. 如您之前所述，第一個玩家擲出 32 面骰子。（而不是加密，我會使用同態承諾，但結果是一樣的。）這給出了一個隨機整數 $ i \in [0, 31] $ 所有玩家都看到了。第一個玩家拿牌 $ L[i] $ ，在列表中留下 31 張卡片。
2. 所有玩家對第一個玩家選擇的卡片進行門檻值解密。也就是說，他們為特定密文創建了一個門檻值-ElGamal 解密共享 $ L[i] $ 並將其發送給玩家 1。這些共享應附有 Chaum-Pedersen 證明（以個人公鑰），證明解密共享是正確的。
3. 下一位玩家擲出一個 31 面的骰子（再次在公共場合）並在正確的索引處“移除”卡片。所有玩家為相關卡生成一個解密份額，並將其發送給獲得卡的玩家。每當需要發新牌時重複此操作。

顯示卡

當玩家以這種方式“抽”一張牌時，他們可以解密它並了解它的價值（在 0-31 中）。為了向其他玩家展示卡片，卡片所有者只需發布這張卡片的所有解密共享，包括他們自己的。其他人可以檢查 NIZK 證明以說服自己該卡是正確的。

Cachin 描述的 Diffie-Hellman Coin-Tossing 協議似乎是您想要的：

https://cachin.com/cc/papers/abba.pdf

本質上，每個份額都是由參與者通過提高 Gi^SHARE 獨立修改的。合併的 Gsec^SHARE 是您的 PRF。

並且您可以驗證參與者是否誠實等。

您甚至可以通過使用多輪 DKG 步驟來消除受信任的經銷商步驟……因此，最終，任何一方都不知道秘密……並且各方都可以驗證隨機數是真實生成的.

https://eprint.iacr.org/2012/377.pdf

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