8.4　零知识数独

鲍勃在午餐时间尝试解开一道当天报纸上的数独谜题。

图8-6　零知识数独

鲍勃痛苦地喊道：“报纸一定弄错了，这个数独不可能有解！”他的同事艾莉丝听到了，过来看了一眼。她在早班车上解出了同一道题，所以她知道鲍勃是错的。艾莉丝的解如下。

图8-7　 零知识数独的解

鲍勃正打算放弃这个谜题，于是艾莉丝说她能解出这道题，但鲍勃不相信。艾莉丝知道鲍勃看到明天公布在报纸上的答案时将会很沮丧，所以她想让鲍勃继续尝试下去。她可以向鲍勃展示自己的答案，但这将毁掉鲍勃破解谜题的乐趣。艾莉丝想在不透露任何答案信息的前提下，让鲍勃相信这个数独谜题是有解的。

幸运的是艾莉丝在大学里主修计算机科学，她知道零知识证明。她设计了如下这个方案。

首先，艾莉丝回到自己的办公隔间，不让鲍勃看见她。艾莉丝随机重新排列了1～9的数字。

图8-8　数字

然后她把自己的解按上表进行数字替换（用2代替1，3代替9，等等），然后把结果写到一大张纸上。

图8-9　经过重新排列的零知识数独

然后艾莉丝仔细地把纸剪成81片，每片上有一个数字。她把每片纸放到一个小袋子里，并把袋子按数字原来的顺序放在一个空白的网格上。

图8-10　被遮盖的零知识数独

最左上角的袋子里装着数字2，它右边的袋子装着数字3，等等。

艾莉丝小心地把网格和袋子带到鲍勃那里，解释了刚才她做的事情（没有透露数字重排前后的对应关系），并让鲍勃从28个检验方法中选择一种。

• 从9行中选择一行，打开那行的所有袋子。
• 从9列中选择一列，打开那列的所有袋子。
• 从9个3x3的方格中选择一个，打开里面的所有袋子。
• 选择那些位于原来谜题中已知数字位置上的袋子，并打开它们。

假如鲍勃选择了打开第3行的所有袋子。他看到的如下图所示。

图8-11　打开一行的零知识数独

如果艾莉丝有一个解，并且做了她说的那些操作，那么鲍勃看到的应该是1～9这几个数字不重复的随机排列。如果鲍勃看到两个相同的数字，那他就知道艾莉丝作弊了，但是这里艾莉丝通过了测试。

鲍勃若选择列或方格也有同样的检验策略。

如果鲍勃选择最后一种检验方法，即“选择那些处在原来谜题中已知数字位置上的袋子，并打开它们”。他看到的如下图所示。

图8-12　打开已知数字对应位置的零知识数独

当且仅当鲍勃选择做这项测试时，艾莉丝会把数字重排前后的对应关系表展示给鲍勃看。

图8-13　数字

然后鲍勃就可以检查打开位置的数字与谜题中原来已知数字的对应关系是否如表中所示。根据此表，原题中的数字9应该对应袋中的数字3，果然如此。

如果艾莉丝真的有一个解并且做了她说的那些操作，她就会通过所有的测试。鲍勃从中得知了什么？如果鲍勃选择查看某一行、列或方块，他只能够看到随机排列的1～9，没有任何对解题有用的信息。

如果鲍勃选择了最后一个测试，他会看到原来谜题的一个随机重排，也没有任何对解题有用的信息。

要是艾莉丝没有一个真正的解会怎样呢？那无论艾莉丝怎么做，都不可能通过鲍勃可能选择的所有测试。如果鲍勃随机选择的话，艾莉丝有至少1/28（即3.57%）的概率被抓到作弊。听起来这个概率挺低的，但如果艾莉丝和鲍勃重复83次测试（每次都选择一个新的数字对应关系），艾莉丝至少有1次不能通过测试的概率将超过95%。

鲍勃终于相信艾莉丝解出了这道数独谜题，但是他得到的是关于解的“零知识”，即除了知道存在一个解之外一无所知。鲍勃可以继续求解这道谜题，并相信它是有解的，但这对于找到答案没有任何帮助。

在这个例子里，鲍勃不愿意了解艾莉丝的解的任何细节。但在理论上，鲍勃可以通过抓起所有袋子并打开它们来作弊。为了避免这种情况，艾莉丝可以用上锁的箱子来代替袋子，并且只给鲍勃他选择的那些箱子的钥匙。

要是鲍勃和艾莉丝不在同一个办公室，而是位于不同的城市呢？他们仍可以轻松地通过电话或电子邮件交流，但是怎么来表示袋子呢？他们可以使用简单的加密技术。艾莉丝为每一个袋子选一个不同的随机大数字，其最后一位和袋子里的数字相同，比如为装有数字2的袋子选择3 682 502。然后艾莉丝用她的公钥为这些数字加密，把它们发送给鲍勃。鲍勃选好做哪项测试后，艾莉丝给出鲍勃选择的袋子对应的解密后的值。鲍勃可以用艾莉丝的公钥重新加密这些数字，然后检查是否与之前发送的加密值相符。

正如我们在第4章看到的，数独是NP完全问题，即每一个NP问题都能归约到数独问题。所以我们就自动有了每一个NP问题的零知识系统。艾莉丝可以说服鲍勃在敌友国存在一个很大的团，可以用三种颜色填充某张地图，或存在一条很短的旅行商路线，同时只透露团、填色方法或路线的零知识，即它们是存在的这个事实。

密码学攻击中常用的方法是通过冒充别人来蒙混过关。零知识证明则提供了一种防卫这种身份欺骗的方法。艾莉丝使用自己的公钥加密一些随机选择的个人机密信息。艾莉丝想向鲍勃证明她的身份。如果她直接把这些秘密告诉鲍勃，那么理论上鲍勃就有了冒充艾莉丝的机会。而如果艾莉丝提供的是一些零知识证明，那么她不仅能让鲍勃相信她知道这些秘密，更重要的是没有透露自己的任何秘密。这样鲍勃就能在不知道艾莉丝个人机密信息的前提下确认对方的身份。