论文标题
如何在网格中物理验证矩形：Shikaku的物理ZKP
How to Physically Verify a Rectangle in a Grid: A Physical ZKP for Shikaku
论文作者
论文摘要
Shikaku是一个由矩形网格组成的铅笔拼图，其中一些包含数量。播放器必须将网格划分为矩形，以使每个矩形完全包含一个等于该矩形区域的数字。在本文中，我们使用一张扑克牌提出了两个实体零知识证明协议，以实现shikaku，这使摊子可以物理地表明他/她知道难题的解决方案而不会透露拼图。最重要的是，在我们的第二个协议中，我们开发了一种通用技术，可以物理验证矩形网格中具有一定大小的矩形形状区域，该区域可用于验证具有相似约束的其他问题。
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.
