密码学家就餐问题

和计算机系统中讨论思索的哲学家就餐问题类似，也有一个密码学家聚餐问题(Dining Cryptographers' Problem, DC)

三个保密家到他们平时喜欢的三星级酒店的里吃饭，服务员告诉他们付款规则是采用匿名方式进行的。其中一个保密家可以为这顿饭付账或者由 NSA (美国国家安全局)替他们付账。三个保密家珍重每个人的匿名付账权力，但是他们疑惑是否由 NSA 来替他们付账。

如何既能让大家知道是否由 NSA 付账，又能保证大家的隐私，这个问题就是密码学家聚餐问题

该问题的解决方案 DC-Nets 由 David Chaum 在 1988 年提出，他也是 Mix 网络的提出者。

首先，每个密码学家随机出一个 $0$ 或 $1$ 的随机数，并把结果告诉与自己相邻的另外两个密码学家，作为共享的秘密，每个人将获得两个值 $L,R$
每个密码学家公布一个数值：
- 如果自己不是泄密者，公布相邻者数据的异或值: $L \oplus R$
- 如果自己是泄密者，公布相邻者异或值的非: $\neg (L \oplus R)$
将所有人公布的数值取异或
如果结果是 $1$ 说明泄密者是自己人

该思路基于异或运算 $a \oplus b \oplus a = b$ 的特点，如果不存在泄密者，所有的数据都会被异或两次，最终结果为 $0$

但是，DC-Nets 存在如下的问题：

无法实现信息学上匿名（除非存在真正的随机）
很难避免流量分析以及蜜罐节点（存在不遵守规则的节点）
没有问责机制（无法对不遵守规则的节点进行审查）
难以在大范围内使用
无法对节点进行验证（存在女巫攻击）

随机化回答

一种类似的概念是差分隐私中的随机化回答。如要统计学生是否挂过科，每个学生可以通过 $20\%$ 的概率说真话， $80\%$ 的概率随机说。这样就可以实现对于每一个说 “是” 和 “否” 的同学，都无法知道其是否真正挂过科。
假设有 $10000$ 条统计结果，那么可以预计有 $8000$ 条是随机的数据， $2000$ 是真实可靠的数据。那么对于随机数据中，可以视为有 $4000$ 条 “是”， $4000$ 条 “否”。将统计结果中减去这些结果，即可得到真实的比例。

比如，使用下述代码，即可得到一个简单的结果。
如 $5595$ 条 “是”， $4405$ 条 “否” ，减去 $4000$ 条随机数据后，可以近似认为有 $1595$ 条 “是”， $405$ 条 “否”。
符合原本的数据比例 $8:2$

import random

t = 8000
f = 10000-t
p = 80
d = {1: 0, 0: 0}

for i in range(t):
    if random.randint(0, 100) > p:
        d[1] += 1
    else:
        d[random.randint(0, 1)] += 1

for i in range(f):
    if random.randint(0, 100) > p:
        d[0] += 1
    else:
        d[random.randint(0, 1)] += 1

print(d)

女巫攻击(Sybil Attack)

在小说《女巫》中，女主被诊断分离性身份认同障碍，兼具 $16$ 种人格¹，女巫攻击就是对这种一个个体拥有多种身份的攻击

利用社交网络中的少数节点控制多个虚假身份，从而利用这些身份控制或影响网络的大量正常节点的攻击方式。Sybil 攻击最早出现于无线通信领域中。Douceur 第一次在点对点网络环境中提出，他指出这种攻击将破坏分布式存储系统中的冗余机制

在P2P网络中，由于节点可能会动态地加入、退出，因此数据可能会备份到多个节点上，如果一个节点将自己伪装成 $10$ 个节点，他将能获得 $10$ 个节点的权重，如果一个节点将自己伪装成 $1000000000$ 个节点（如果其存储和算力都足够），那么他可能比剩下所有的节点加起来权重还要高，也即控制了整个网路。

一个更直观但可能不太恰当的解释是水军：伪造身份刷赞、刷评论，营造出一种大家都觉得某个东西好（实则不一定）

要解决该问题，主要有以下思路² ²：

身份认证机制
- 统一的第三方认证机构（可能会损失匿名性）
- 初始化一些可信任节点，使用担保算法来确认其他节点
特征向量：按照数据分析算法，对每个结点的特征向量进行分析（不能完全避免）
加强伪造难度：区块链中常用的工作量证明(Proof of Work, PoW)（算力多的结点仍然会有更高的权重）