闲聊零知识证明：一个钢铁直男的证明

自上次发了《趣说安全多方计算 | 如何用密码学玩转暗军棋游戏？》的文章之后，不少小伙伴表示对安全多方计算很感兴趣，对李雷和韩梅梅孤男寡女共处一室更感兴趣。所以，今天我们的故事还是从李雷和韩梅梅开始。

这次，他们玩的是数独，相互出题给对方解答，一共玩三个回合，输的要请对方吃一个月饭。

Tips:数独是源自18世纪瑞士的一种数学游戏，是一种运用纸、笔进行演算的逻辑游戏。玩家需要根据9×9盘面上的已知数字，推理出所有剩余空格的数字，并满足每一行、每一列、每一个粗线宫（3*3）内的数字均含1-9，不重复。

两个回合过后，两人战成了平局。第三个回合，韩梅梅率先取得一分，然后对李雷说：

“时间不早了，估计你也赢不了，要不不玩了，你直接认输吧，咱们还可以干点别的事情。”

李雷这个直男一听就不乐意了，心想：你这不是耍赖吗，我这么学富五车、才高八斗、绝顶聪明的人怎么可能输给你呢？然后就绞尽脑汁给韩梅梅又出了一个数独题。

韩梅梅一脸嗔怒，但看着李雷坚定的表情，只好再次去解题。果然这道题难度极高，韩梅梅想了一个小时也没解出来。然后，开始则怪李雷：

“你是不是故意难为我，出了道根本没有答案的题？都这么晚了，你认个输就不行吗？”

李雷一听急了，说：“是你太笨了，花了一个小时都还没解出来。我可以在不告诉你答案的情况下，证明这道题是有解的！”说完便开始他“神奇”的证明过程。

李雷把答案填写到数独题上，并将纸背扣。然后在韩梅梅的监督下，到楼下复印店复印了3份。随后，又去找了27个小袋子和一把剪刀。

李雷将复制的第一张纸的每一行的数字挨个剪下来分别放入一个袋子中，9行数字共放入9个袋子；将复制的第二张纸的每一列的数字挨个剪下来分别放入一个袋子中，9列数字共放入9个袋子；将复制的第三张纸的每一个宫（粗线3*3正方形）的数字挨个剪下来分别放进一个袋子中，9个宫数字分别放入9个袋子。剪法大致如下图：

随后将27个袋子交给韩梅梅检查，如果每个袋子都有1到9的纸片各1张，则证明李雷出的题目是有解的。三张复印的纸分别校验了数独正确答案的3个条件，而且在这个过程中韩梅梅并不知道答案（数字的正确排列顺序）。

韩梅梅“绝望”地看了李雷一眼，依次打开了27个袋子，然后告诉李雷自己输了，客气地将李雷请了出去……

从此，李雷就再也联系不上韩梅梅了。

在故事里，我们把李雷的这个证明叫做“一个来自钢铁直男的证明”。

而现实中李雷证明数独有解的方法叫做零知识证明(Zero -Knowledge Proof)，它指的是证明者能够在不向验证者提供任何有用的信息的情况下，使验证者相信某个论断是正确的。

零知识证明是密码学中的另一项黑科技，可用于数字签名、密钥互换、交易验证等隐私保护等场景。