密码学家晚餐问题（n>2情况）

密码学家晚餐问题

场景描述

三位密码学家（Alice、Bob、Carol）正在享受晚餐，坐在他们钟爱的三星级餐馆。

业务逻辑

在准备支付账单时，侍者通知他们需要匿名支付，其中一个密码学家可能正在支付账单。账单可能已经由美国国家安全局（NSA）支付。他们互相尊重匿名支付的权利，但又需要确认是否是NSA在支付。

系统目标

确定是三者之一在支付账单，同时保护支付者的匿名性。

1. 每个密码学家将菜单放在左边，相互隔离。
2. 每人只能看到自己和右边密码学家的结果。
3. 每个密码学家在他和右边密码学家之间抛掷一枚硬币。
4. 每个密码学家广播她能看到的两枚硬币是同一面还是不同的一面。

判定结果:

• 如果桌上说“不同”的人数为奇数，则某个密码学家在支付账单。
• 如果桌上说“不同”的人数为偶数，则NSA在支付账单。

扩展1

当密码学家人数变为n，n＞2时，结果是否仍成立？

首先引入XOR观念便于理解和阐释：

• 硬币的结果只为0或1，密码学家给出的真结果：1⊕0=1，1⊕1=0，0⊕1=1与0⊕0=0
• 假结果：1⊕0=0，1⊕1=1，0⊕1=0与0⊕0=1

对于n枚硬币，设为1有p个，为0有q个，每个硬币的状态为ai（ai=0或1），每位学家给出的结果为xi。

若没有学家付款，则:

[x_1⊕x_2⊕……⊕x_i=(a_i⊕a_1)⊕(a_1⊕a_2)⊕(a_2⊕a_3)⊕……(a_{i-1}⊕a_i)=a_i⊕a_1⊕a_1⊕a_2⊕a_2⊕a_3⊕……a_{i-1}⊕a_i=(a_1⊕a_1)⊕(a_2⊕a_2)⊕(a_3⊕a_3)⊕……(a_i⊕a_i)=0]

若有一位学家付款，且不妨假设他是第一位学家，则:

[x_1⊕x_2⊕……⊕x_i=(a_i⊕a_1)’⊕(a_1⊕a_2)⊕(a_2⊕a_3)⊕……(a_{i-1}⊕a_i)=(a_2⊕a_2)⊕(a_3⊕a_3)⊕……(a_{i-1}⊕a_{i-1})⊕(a_i⊕a_1)’⊕(a_i⊕a_1)=0⊕1=1]

同时，易知对于一系列0、1逐位异或的结果为0，若1的个数为偶数，为1，若0的个数为奇数。

所以，对于n>2时结果仍然成立："桌上说“不同”的人数为奇数：某个密码学家在支付账单，"桌上说“不同”的人数为偶数：NSA在支付账单"的结论仍然成立。