零知识/知识sudoku解的证明

Question

最近，我开始了斯坦福大学开设的“密码学1”课程。在解释零证明知识时，指导员提到以下几点：

几乎任何你想证明你有答案的谜题，你都可以证明它是你的知识。例如，假设你有一个sudoku谜题，你想要证明你知道解决方案，你可以向Bob证明它，就像Bob对这个解决方案一无所知，但是他仍然会被认为你知道它的解决方案。

我对此感到非常困惑。如何证明他可以解决sudoku难题，并证明给X(在这种情况下，Bob)，而不传递实际的解决方案？

Answer 1

假设Bob站在你旁边同一间屋子里：

• 准备印有正确数字的卡片
• 根据设置放下牌，面朝上。
• 用正确的解决方案把剩下的牌放下，朝下，这样鲍勃就看不到了。

现在让Bob选择一列、一行或扇区。

• 你拿起那一行，列或扇区中的卡片，仍然没有把它们展示给鲍勃(如果有的话，可以转过脸来)，然后开始洗牌。
• 把它们交给鲍勃，他可以看牌是否有正确的号码(在标准游戏中是1-9)。

经过洗牌后，鲍勃再也看不出哪一张牌在哪个位置，他只知道这一套牌是正确的。如果朝下的解决方案是正确的，这将永远正确的工作。如果你不知道实际的解决方案，就有一个不可忽视的概率被抓到作弊。捕捉作弊的机会是相当低的，所以你需要做很多重复，以获得一个总体上可接受的概率。

所有的过程都可以通过密码方式完成，例如，可以通过承诺实现面向下卡，从MPC、混合网等可以知道洗牌。

编辑:来自这个博客的替代解决方案:对数字应用一个置换，然后你就不需要洗牌了。然而，你需要证明这个解决方案实际上符合在这个排列下固定数字的设置。因此，维克多也可以选择看原版拼图。