趣题：平面图三染色的零知识证明

    在各种介绍密码学与协议的教材里都有关于零知识证明的话题——如何让你相信我已经找到了一个解，但又不告诉你这个解是什么。最经典的例子便是关于Hamilton回路的问题——存在这样一种巧妙的协议，可以让你相信我已经找到了某个图的Hamilton回路，而你却完全得不到关于这个Hamilton回路本身的任何信息。今天我又看到了一个非常不错的零知识证明实例。给定一个平面图，你需要给每个区域染一种颜色，使得任两个相邻的区域颜色不同。如果你仅用三种颜色就能做到这一点，我们就说这个图是可以三染色的。目前我们还没有一个判断平面图可否三染色的好办法，寻找一个平面图的三染色方案并不是一件容易的事。现在，假如你已经找到了某个给定平面图的三染色方案，你想向别人炫耀自己的成果，但又不想透露关于你的染色方案的任何信息。你能否设计一种协议使得对方能够相信你确实找到了一种三染色方案而又不告诉他这种方案是什么呢？

    假设平面图一共有n个区域，从1到n分别编号。注意，如果你有了一种三染色方案，置换原方案中的颜色，你会立即得到另外五种染色方案。从六种（本质相同的）染色方案中随机选一种染色方案，用防欺骗的承诺协议对每个区域各自用的什么颜色进行加密（比如“区域编号+随机字符串+颜色代码”的md5值），然后把n份密文一同发给对方。对方选取原图中的相邻两块区域，要求查看它们的颜色。把他所选的两个区域编号所对应的原始信息告诉他，让他验证其颜色确实是合法的，并且这两个字符串的md5值正好与预先给他的相同。反复执行上述操作，直到对方确信你的确掌握有一种三染色的方案。

来源：http://math.ias.edu/~virgi/greatcs/Digitalenvelopecrypto.pdf

12 条评论

发表评论




Enter Captcha Here :