Five Cells is a pencil puzzle consisting of a rectangular grid, with some cells containg a number. The player has to partition the grid into blocks, each consisting of five cells, such that the number in each cell must be equal to the number of edges of that cell that are borders of blocks. In this paper, we propose a physical zero-knowledge proof protocol for Shikaku using a deck of playing cards, which allows a prover to physically show that he/she knows a solution of the puzzle without revealing it. More importantly, in the optimization we develop a technique to verify a graph coloring that no two adjacent vertices have the same color without revealing any information about the coloring. This technique reduces the number of required cards in our protocol from quadratic to linear in the number of cells and can be used in other protocols related to graph coloring.
翻译:五个单元格是一个由矩形网格组成的铅笔拼图, 有些单元格包含数。 玩家必须将网格分割成块块, 每个由五个单元格组成, 这样每个单元格的数必须等于该单元格的边缘数, 也就是区块的边框数。 在本文中, 我们建议使用一张扑克牌为志家提出一个物理上的零知识证明协议, 使证明人能够实际显示他/ 她知道谜题的解答, 而不透露它。 更重要的是, 在优化过程中, 我们开发了一个技术, 来验证一个图形颜色, 显示两个相邻的顶部没有相同的颜色, 而没有透露任何关于颜色的信息。 这个技术可以减少我们协议中要求的卡片数, 从细胞数的二次角到直线, 并且可以用于与图形颜色有关的其他协议 。