Shikaku is a pencil puzzle consisting of a rectangular grid, with some cells containing a number. The player has to partition the grid into rectangles such that each rectangle contains exactly one number equal to the area of that rectangle. In this paper, we propose two physical zero-knowledge proof protocols for Shikaku using a deck of playing cards, which allow a prover to physically show that he/she knows a solution of the puzzle without revealing it. Most importantly, in our second protocol we develop a general technique to physically verify a rectangle-shaped area with a certain size in a rectangular grid, which can be used to verify other problems with similar constraints.
翻译:Shikaku是一个笔谜, 由矩形格组成, 有些单元格含有数字 。 玩家必须将网格分割成矩形, 这样每个矩形都包含一个与矩形面积相等的精确数字 。 在本文中, 我们提议了两套实际的零知识验证程序, 用于 Shikaku 使用一张扑克牌牌, 使一个证明人能够实际显示他/ 她知道谜题的解答, 而不透露它 。 最重要的是, 在我们的第二个协议中, 我们开发了一种一般技术, 来实际验证矩形形形形形区域, 其大小与矩形格网的大小相当 。 这可以用来验证具有类似限制的其他问题 。