密码学家就餐问题

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

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

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

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

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

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

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

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

随机化回答

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

比如，使用下述代码，即可得到一个简单的结果。
如 55955595 条 “是”，44054405 条 “否” ，减去 40004000 条随机数据后，可以近似认为有 15951595 条 “是”，405405 条 “否”。
符合原本的数据比例 8:28: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)

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

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

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

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

要解决该问题，主要有以下思路^{2 2}：

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

参考文章