密码学家就餐问题

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

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

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

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

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

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

但是,DC-Nets 存在如下的问题:

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

女巫攻击(Sybil Attack)

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

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

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

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

要解决该问题,主要有以下思路2 2

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

参考文章


  1. 简书 - 女巫攻击 ↩︎

  2. flydeam的博客 - 女巫攻击及其防范 ↩︎