餐饮密码学家问题

跳到导航跳转在密码学中搜索，就餐密码学家问题研究如何执行布尔或函数的安全多方计算。David Chaum在20世纪80年代初首次提出了这个问题，并用它作为一个说明性的例子来说明发送匿名消息是可能的，而无条件的发送者和接收者是不可追踪的。基于这个问题的匿名通信网络通常被称为DC-net(其中DC代表餐饮.。

尽管有餐饮这个词，但就餐密码学家问题与就餐哲学家问题无关。

三位密码专家围坐在一张桌子旁共进晚餐。服务员告诉他们，这顿饭是由某个人支付的，这个人可能是密码学家之一，也可能是美国国家安全局(NSA)。密码学家们相互尊重对方匿名付款的权利，但希望查明美国国家安全局是否支付了这笔款项。因此，他们决定执行一个分两个阶段的协议。

在第一阶段，每两个密码学家建立一个共享的一位秘密，比方说，通过在菜单后面扔一枚硬币，这样每两个密码学家只有两个密码学家轮流看到结果。例如，假设在掷硬币之后，密码学家A和B共享秘密比特1{\displaystyle 1}，A和C共享0{\displaystyle 0}，并且B和C共享1{\displaystyle 1}。

如果他们没有支付餐费，他们与两个邻居分享的两个比特的异或(XOR)，

假设没有密码师付费，则A宣布1DisplayStyle 0=1{\⊕1\Oplus 0=1}，B宣布1DisplayStyle 1=0{\DisplayStyle 1\Oplus 1=0}，C宣布0⊕1=1{\DisplayStyle 0\Oplus 1=1}。另一方面，如果A已支付，则她宣布-(1⊕0)=0{\DisplayStyle\lnot(1\Oplus 0)=0}。

这三个公开声明加在一起揭示了他们问题的答案。简单地计算宣布的三个比特的异或(XOR)。如果结果为0，则意味着没有密码学家支付(因此NSA一定已经支付了账单)。否则，其中一个密码学家付钱，但其他密码学家仍然不知道他们的身份。

DC-NET协议简单美观。然而，它有几个限制，一些解决方案已经在后续研究中进行了探索(请参阅下面的参考资料部分)。

如果两个密码学家为晚餐买单，他们的消息将相互抵消，最终的XOR结果将是0{\displaystyle 0}。这称为冲突，并且使用此协议一次仅允许一个参与者进行传输。在更一般的情况下，只要有偶数个参与者发送消息，就会发生冲突。

任何不希望该组成功通信的恶意密码学家都可以通过简单地发送随机位而不是正确的XOR结果来阻塞协议，从而最终的XOR结果是无用的。出现这个问题的原因是，原始协议没有使用任何公钥技术，并且缺乏可靠的机制来检查参与者是否诚实地遵守协议。[1]。

该协议需要参与者之间的成对共享密钥，如果参与者很多，这可能会有问题。此外，虽然DC-NET协议是无条件安全的，但它实际上依赖于这样的假设，即在参与者对之间已经存在无条件安全的信道，这在实践中并不容易实现。

相关的匿名否决网络算法计算几个用户输入的逻辑OR，而不是像DC网络中那样的逻辑XOR，这在逻辑OR组合操作自然适合的应用中可能是有用的。

周大伟(David Chaum)在20世纪80年代初首次想到这个问题。第一本概述基本基本思想的出版物是他的。[2]期刊版出现在《密码学杂志》的第一期上。[3]。

DC网络容易被推广以允许每轮多于1比特的传输，对于大于三个参与者的组，以及对于除了二进制数0和1之外的任意字母，如下所述。

为了使匿名发送者能够在每一轮DC网络中传输多于一位的信息，密码学家组可以简单地重复该协议所需的次数，以创建所需位数的传输带宽。这些重复不需要连续执行。在实际的DC-Net系统中，典型的情况是成对的参与者使用Diffie-Hellman，预先商定一个共享的主秘密。

该协议可以推广到一组n{\displaystyle n}个参与者，每个参与者都具有与其他参与者共同的共享密钥。在每一轮协议中，如果一个标准杆