可驗證的分佈式秘密聖誕老人分配

我的家人正在計劃一個秘密的聖誕老人，我在想如何編寫一個小的網路應用程序來分發這些秘密任務。但是這種方法的缺點是顯而易見的：使用者無法知道我是 a) 隨機生成結果 b) 自己不窺探（秘密）分配。

在真正的秘密聖誕老人中，沒有中央機構分發任務。相反，有一個過程，每個使用者從帽子中抽出名字，如果他們拿起一個違反限制之一的名字（他們自己或有時是配偶），他們相信會重新繪製。在繪圖時，每個使用者都被信任/觀察到不會偷看帽子，只在無效條件下重繪。

所以我的問題是：在消息傳遞框架下，什麼方案需要最少的信任，但會產生一個沒有人知道其他任務的有效遊戲？

我能夠實現的最接近的是環系統，其中任意起始客戶端為自己繪製一個隨機的、有效的分配，然後將該分配發送給環中的下一個。然後這個使用者隨機抽取一個與之前的分配不衝突的有效分配，將這兩者組合在一起，然後將其發送給下一個客戶端。這可以重複，直到生成有效的總分配（一些分配在最後變得無效，例如：最後的使用者只收到一個名稱：他們自己的）。

這是相當次優的，因為第一個和最後一個分配可以分別由第二個和倒數第二個使用者計算。此外，必須信任每個使用者

1. 繪製隨機名稱
2. 保留第一個有效分配
3. 將他們的作業與之前的作業進行或運算並將其發送出去

我會說第 2 和第 3 是與物理遊戲共享的（相信您不會輸入多個名稱，取出多個名稱等……）但這是我似乎無法消除的第一個條件（或核實）。

如果這是一個愚蠢的問題，請原諒我，但我在床上躺了幾分鐘後很開心地思考這個問題，並想知道其他人是否有任何見解。

謝謝！

改革問題。與其讓每個參與者選擇他們的受贈人（他們給予的人），不如讓他們選擇一個贈予者（他們從中接受）。

1. 每個參與者隨機生成一個數字（適當大）並匿名送出（例如，通過 tor 網路）到站點。這個數字代表他們作為給予者。
2. 在所有參與者都進入後，網站會發布列表，參與者（一次 1 個，不按特定順序）從列表中選擇（並刪除）一個隨機數，將其與作為接收者的公共名稱連結到 giver-id .
3. 在所有參與者都為自己選擇了一個給予者 ID 後，評估有效性標準：每個參與者觀察與他們衝突的特定共同參與者（即直系親屬）。如果衝突的共同參與者擁有觀察者的給予者 ID，則該觀察者匿名（通過與步驟 1 中相同的渠道）註冊衝突。
4. 1. 如果沒有發生衝突，每個參與者現在都知道應該向誰贈送禮物：擁有其贈送者 ID 的共同參與者。
5. 如果發生一個或多個衝突，請從第 2 步重新開始，限制參與者不能選擇與以前相同的給予者 ID。
6. 如果所有組合都用盡，請通過重新選擇給予者 ID 從第 1 步重新開始。

成功的機率和/或預期的迭代次數留給讀者練習。

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