Eol
Thanks for reading :)
Eol's Blog

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

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

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

其实是因为懒得做两套样式 _(:з」∠)_

别的不说,先来这次推荐的歌曲~

超治愈超可爱!!

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

Spotify:あたしが、先だった、先だったんだ!

写本文的原因

分享上面那首歌~

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

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

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

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

问题背景

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

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

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

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

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

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

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

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

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

(粗略的)解决思路

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

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

抽签工具

一、选数并加密

加密部分的内容请注意保存。该部分每个宿舍只需完成一次,请各宿舍内部自行协商。

1. 首先,请从 {0, 1, 2, 3, 4, 5} 六个自然数中任选一个填入下方输入框中(为方便后续叙述,这个数记为 n)。你也可以点击点击右侧按钮产生随机数。

Random

2. 之后请在下方输入 32 个(大写)十六进制字符作为密钥(即 128 位)。你可以使用任选的 32 个数字,也可以点击右侧按钮产生随机的密钥。

Random

注意:请保存好您所选的数字和密钥,一旦遗忘将无法产生抽签结果。离开或刷新界面后,由于本页面并未储存您的信息,数字和密钥均会清空。

3. 点击加密后,将密文复制到班群即可。注意密钥的保密。

加密

二、密钥公开

待达到公开时间且三个宿舍的密文均公开后,各个宿舍再将密钥公开到班群中。

三、结果查询

将三组密文和密钥分别填入下方对应位置后即可得到最终结果。任何人可检验。若与最终公示结果不符,请及时指正。

({{ results[0] }} + {{ results[1] }} + {{ results[2] }}) mod 6 = {{ sum }}

当三组密文和密钥均填写完毕后,公示表(下表)的最终结果所在行将会高亮显示

可靠性证明

前提/假设

  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 两位参与者所选数为随机变量,分别记作 IJ;事件 I = iJ = 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 种情况。任意一步没有成功攻破,误差就会一次一次地传递下去。

最后

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

Eol

Author

Leave a Reply

textsms
account_circle
email

Eol's Blog

宿舍抽签工具及其可靠性证明
真实问题:三组同学面临分寝室的问题。寝室有三个,分给三组人总共六种情况。现在需要一种可以通过网络进行,但又能保障结果的随机性和公平性的抽签协议……
Scan QR code to continue reading
2020-02-27