宿舍抽签工具及其可靠性证明

 提示：浏览本文时建议 关闭夜间模式

别的不说，先来这次推荐的歌曲～

超治愈超可爱！！

虽说我是因为 Spotify 的推荐算法找到的这首，不过考虑到国内打不开 Spotify 链接，还是用网易云的链接嵌入了。

Spotify：あたしが、先だった、先だったんだ！

写本文的原因

分享上面那首歌～

一切都从代班长 @Skyleaworlder 大佬忘记分宿舍的截止时间开始。依照大佬本来的计划，我们正式开学之后再抽签决定宿舍。不过我还是不希望等到那么晚，于是开始和 Skyleaworlder 讨论是否存在一个抽签协议，可以让大家在线上完成抽签的同时，还能保证结果的随机性和公平性。

想出这个协议后就决定写这篇文章，提供选宿舍的工具的同时证明一下这个过程的公平性。本来还计划征求所有参与抽签的同学的意见，得到同意之后再进行抽签协议。可惜预期剩余时间相当长的我们（尤其是我）一拖再拖，终于拖到了辅导员来催的那一天，带班长（？）才意识到截止时间已经过了…

所以，三个宿舍在完全没有得到提前通知的情况下，用我的半成品抽了签。没有挂在网上，也没有写完证明 _(´ཀ`」 ∠)_

当然，一些同学可能已经能理解这个方法的公平性了，但显然证明其公平的责任是在我这里。这样，这篇亡羊补牢式的证明就有必要写完，以打消大家的心中的一些疑虑。

问题背景

三组同学面临分寝室的问题。寝室有三个，分给三组人总共六种情况。现在需要一种可以通过网络进行，但又能保障结果的随机性和公平性的抽签协议，参与各方按照这一协议，通过明确、有限的步骤得到抽签结果，并且所有人都能验证结果的有有效性。

和 Skyleaworlder 讨论的过程中，商量了不少方案，不过都被认为有失公平性而舍弃了。比如

• 代班长或老师或其他第三方机构利用随机数给出随机结果的方案。

所有借助第三方 （好像这里是第四方了？） 的方案都会造成第三方的中立性问题。我俩也尝试想过解决这个问题，不过真的没想出除了“信任”之外的方案。在对“信任”不可靠这个观点达成共识后，我们放弃了所有完全由第三方决定的方案。

这里的第三方，还包括软件、服务和其他无人格的工具等。因此，我们想要的协议，参与者应该只包括与结果有直接利益的方面。

• 依赖随机过程来达到随机性的方案。

这里并不是在讨论“真随机”“伪随机”的问题。而是，产生随机数的工具总是要被人使用的，因此工具的操作者可以影响结果。

这个过程中，操作者和工具之间存在一个矛盾：如果工具不可重复，自然可以保证操作者无法影响数的随机性，但操作者却无法信任工具的随机性；如果工具可重复，那么操作者就可以通过重复实验验证工具的随机性，但操作者却可以通过这个重复的过程让结果对自己更有益。

一个典型的例子是，使用 QQ、微信等平台的骰子等工具是不可靠的。所有这些工具，若是前端生成，自然有手段进行更改（可自行搜索关键字“微信 骰子 修改器”）；如果随机数是后端生成，就又出现引入第三方的问题了。

（粗略的）解决思路

三组成员，每人先从 0～5 六个数中任选一个，并使用 AES 加密算法加密，得到密文，保存私钥。之后，各组公布密文。待密文全部公开后，各组再公布自己的密钥。

任何想知道结果或想验证结果的人，只需利用三组密钥和密文，解密出三个数，将其相加求和和再模 6 得到最终结果。比对 公示表 可知最终结果。

抽签工具

可靠性证明

前提/假设

1. 密钥全部公布前，任何参与者都对至少一个其他参与者所选的 n 一无所知。对一个参与者所选的 n 一无所知指的是，认为这个参与者所选数的概率分布为在集合 { 0, 1, 2, 3, 4, 5} 上的均匀分布，且认为这个参与者选的数与其他人的所选相互独立；
2. 参与者不会被错误信息误导。即，对参与者的决策有影响的信息一定是符合事实情况的信息。

这些假设是有意义的。抽签的过程中，参与者首先公开的是 AES 加密后的密文。AES 加密算法有公认的安全性，因此参与者无法通过密文获取到有效信息。不考虑被错误信息误导的情况。考虑进去就内么一点社工的味了（不是

而且很重要的一点，我和 Skyleaworlder 都参与了这个过程，而且都选择了随机生成，因此，根据下文分析可以了解，社会工程学的做法起码对这次分宿舍的过程已经失效了。

随机性

随机性指，在利用该协议进行一次抽签过程之前，最终结果属于 6 种情况中任意一种的概率对于任何参与者或旁观者而言都是相等的。

显然对于旁观者成立。对于参与者，记任何一位参与者 S 所选数为 n；剩余两位参与者 A、B 分别选数i_0, j_0 (i, j \in {0, 1, 2, 3, 4, 5})；S 视角下，A、B 两位参与者所选数为随机变量，分别记作 I、J；事件 I = i、J = j 分别为 A_i、B_j。在无有效信息的假设下，可知任意 A_i、B_j 发生的概率均为 \frac{1}{6}。在此情况下，显然 (i + j)\, mod\,6 依然是 {0, 1, 2, 3, 4, 5} 上的均匀分布。因此，参与者 S 无论选任何数 n，对于他而言最终结果都依然是一个均匀分布的随机变量。

公平性

公平性指的是，很难出现这样的情况：参与者不遵守或者破坏抽签程序，导致最终结果失去随机性，而向参与抽签的一方或多方倾斜。

• 部分作弊等价于无效

不妨假设参与者 S 利用某种手段掌握了另一位参与者 A 所选数的有效信息，这个信息让 S 的预测 I 的概率分布不再是均匀分布，甚至可以肯定 P(I = i_0) = 1。这时，根据假设 1，随机变量 J 仍服从随机分布。此时，对于任意的 k \in {0, 1, 2, 3, 4, 5}，有

\begin{aligned}
P\left((i + j)\;mod\;6 = k\right) 
&= \sum_{i=0}^5 P\left(A_iB_{\left(k-i\right)\;mod\;6}\right) \\
&= \sum_{i=0}^5 P\left(A_i\right) P\left(B_{\left(k-i\right)\;mod\;6}\right) \\
&= \frac{1}{6} \sum_{i=0}^5 P\left(A_i\right) \\
&= \frac{1}{6}
\end{aligned}

因此，对于“部分作弊”的参与者 S，最终的结果依然是随机的，与 n 的选取无关。

• 密文公示后无法更改

虽然 AES 尚未被破解，但 AES 也并不具有 One Time Pad 那样的 Perfect Security，因此密文也包含足够的信息，使得任何参与者都不可能根据一个密文，找出不同的密钥使明文为不同的值。

所以，一旦密文公布，能使结果有意义的密钥也无法造假了，进而之前选择的数已经不可更改。

一些小问题(*ﾉωﾉ)

由假设可知，以下情况并没有考虑在内：

• 形成了一个包含所有参与方面的联盟

嗯 emmmmmmmmm 怎么说呢，这种联盟都形成了还抽什么签啊（╯‵□′）╯︵┴─┴

• 通过社工行为影响或预测其他人的选项

其实就是假设 2 想避免讨论的问题。事实上这种可能是存在的。然而，这种行为可以近似为一个非合作博弈模型，并且存在纳什均衡——只要有一个人选择随机决定数 n，你社工白费力气，不如也随机决定一个，省时省力省脑细胞；如果别人选择社工你——当然是点击随机按钮让别人的社工无效化啊！别人都开始社工你了，这时候还相信大脑就中计了喂！

当然博弈论的结论从来没有 100% 有效过，更何况这里还只是个近似。所以，这里实在是说不清道不明。反正都是没有明确结论的，不如还是当作一个均匀分布来看？嗯嗯！这个方案还是没问题的啊嗯嗯！

更好的方案？

整个抽签方案还没考虑完全成熟就因为时间关系仓促执行了。实在是不幸，没过几天我就又想出了一个（可能）更好的方案，同样具有公平性和随机性，但将社工的难度提高了很多倍。还是考虑这次的问题，三组参与者和六种不同的结果。这个方案的步骤是：

1. 随便一个参与者（使用任意密钥）将这六种不同结果加密，并将密文以任意顺序交给随便另外一个参与者。密文称为第一级密文；
2. 第二个参与者再用他的密钥将六个一级密文加密到的六个二级密文，在以任意顺序给第三个人；
3. 第三个人任意选中一个二级密文，并公示选中的密文和其他的二级密文。
4. 第一、二个参与者将密钥公开。所有人都可以通过两次解密最终被选中的密文得到最终结果。解密剩余二级密文，以验证过程中未发生失误或抽签过程未被攻击。

因为并未采用这种方案，因此不再进一步证明。（不过其实也比较显然了

当然这种方案也有一些缺点，过程不可并行，因此若参与抽签的方面变多，抽签需要的时间将随之（至少）线性增长。此外，不如选数的操作更便捷等。但这种方案的确把社工等攻击手段的可能性降到很低了，因为每步交接都是“任意的顺序”交给下一个人，这种顺序有 720 种情况。任意一步没有成功攻破，误差就会一次一次地传递下去。

最后

虽说很希望能尽量严谨，可毕竟能力和知识都有限，如果发现错误可以在评论区指出，望多多原谅。此外，有其他问题也可在评论区留言一起探讨～