Der Artikel stellt ein einzigartiges kartenbasiertes Protokoll vor, das als "Druckprotokoll" bezeichnet wird und Lösungen für Zersetzungsrätsel wie Five Cells and Meadows verifizieren soll. Dieses Protokoll ermöglicht die Verifizierung von Rätsellösungen, ohne die tatsächliche Lösung preiszugeben, und nutzt das Konzept der Null-Wissen-Beweise. Die Autoren demonstrieren die praktische Anwendung dieses Protokolls, indem sie spezifische Null-Wissen-Nachweisprotokolle für die Fünf-Zellen-und-Wiesen-Rätsel entwickeln. Das Druckprotokoll ist vielseitig einsetzbar und kann an verschiedene Zersetzungsrätsel angepasst werden, wodurch eine greifbare und intuitive Methode zur Verifizierung komplexer Puzzellösungen zur Verfügung steht. Der Artikel beleuchtet auch die Beschränkungen des aktuellen Protokolls und schlägt zukünftige Forschungsrichtungen vor, um Rätsel mit einer größeren Anzahl regionaler Typen zu lösen.
KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
Abstract
Decomposition puzzles are pencil-and-paper logic puzzles that involve partitioning a rectangular grid into several regions to satisfy certain rules. In this paper, we construct a generic card-based protocol called printing protocol, which can be used to physically verify solutions of decompositon puzzles. We apply the printing protocol to develop card-based zero-knowledge proof protocols for two such puzzles: Five Cells and Meadows. These protocols allow a prover to physically show that he/she knows solutions of the puzzles without revealing them.
Hinweise
A preliminary version of this paper [25] has appeared at LATINCRYPT 2023.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
Pencil puzzles are puzzles that can be solved by writing down the solution on a paper. They must be solved using only logical reasoning and do not require additional knowledge. Examples of pencil puzzles include Sudoku, Nonogram, Kakuro, and Slitherlink.
Pencil puzzles can be categorized into several types based on their core theme. One of the common themes is to partition a rectangular grid into several regions to satisfy certain rules. We call these puzzles decomposition puzzles.
Anzeige
1.1 Five Cells
Five Cells is a decomposition puzzle created by Nikoli, a Japanese publisher famous for developing many popular pencil puzzles. The puzzle consists of an \(m \times n\) rectangular grid, with some cells containing a number. The player has to partition the grid into pentominoes. The number in each cell indicates the number of edges of that cell that are borders of pentominoes (including the outer boundary of the grid) [17]. See Fig. 1.
Fig. 1
An example of a \(5 \times 5\) Five Cells puzzle (left) and its solution (right)
×
Deciding solvability of a given Five Cells puzzle is NP-complete [11].
1.2 Meadows
Meadows is another decomposition puzzle consisting of an \(n \times n\) square grid, with some cells containing a dot. The player has to partition the grid into squares such that each square contains exactly one dotted cell. See Fig. 2.
The rules of Meadows are similar to those of Shikaku,1 a more well-known decomposition puzzle developed by Nikoli, so the puzzle may be considered a variant of Shikaku [12], which is also NP-complete [35].
Anzeige
1.3 Zero-Knowledge Proof
Suppose that Panthalassa, a puzzle expert, creates a pencil puzzle and challenges his friend Vodka to solve it. He wants to convince her that the puzzle indeed has a solution, but does not want to reveal the solution itself. A zero-knowledge proof (ZKP) makes this seemingly difficult task possible.
Formally, a ZKP is an interactive protocol between a prover P and a verifier V, where both are given a computational problem x, but only P knows its solution w. Also, the computational power of V is limited, so V cannot obtain w from x. A ZKP has to satisfy the following three properties.
1.
Completeness: If P knows w, then V accepts with high probability. (In this paper, we consider the perfect completeness property where V always accepts.)
2.
Soundness: If P does not know w, then V rejects with high probability. (In this paper, we consider the perfect soundness property where V always rejects.)
3.
Zero-knowledge:V learns nothing about w. Formally, there exists a probabilistic polynomial time algorithm S (called a simulator) that does not know w but has an access to V, and the outputs of S follow the same probability distribution as the ones of the real protocol.
The concept of a ZKP was first introduced in 1989 by Goldwasser et al. [7]. It has been proved that every NP problem has a ZKP [6], so a computational ZKP for any NP puzzle can be constructed via a reduction to another problem. Such construction, however, is unintuitive and looks unconvincing. Therefore, many researchers instead focused on constructing physical ZKPs using a deck of playing cards. These card-based protocols have benefits that they require only portable objects easily found in everyday life and do not require computers. They are also easy to understand and verify the correctness and security, even for non-experts, and thus can be used for didactic purpose.
Card-based ZKP protocols for many pencil puzzles have been developed,2 including Sudoku [8, 27, 33], Nonogram [3, 23], Akari [1], Takuzu [1, 15], Kakuro [1, 16], KenKen [1], Makaro [2, 32], Norinori [4], Slitherlink [14], Juosan [15], Numberlink [29], Suguru [19], Ripple Effect [30], Nurikabe [20], Hitori [20], Bridges [31], Masyu [14], Heyawake [20], Shikaku [28], Usowan [21], Nurimisaki [22], ABC End View [5, 26], Goishi Hiroi [26], Moon-or-Sun [9], and Kurodoko [22], as well as those for non-pencil logic puzzles such as Cryptarithmetic [10] and Ball sort puzzle [24].
Fig. 2
An example of a \(7 \times 7\) Meadows puzzle (left) and its solution (right)
×
1.4 Our Contribution
In this paper, we construct a generic card-based protocol called printing protocol. This protocol prints some numbers from the template onto a target area from the grid, and also verifies that the printed numbers do not overlap with the already existing numbers in that area. The printing protocol can be used to verify solutions of many decomposition puzzles. We show two applications of it by developing ZKP protocols for two such puzzles: Five Cells and Meadows.
2 Preliminaries
2.1 Cards
Each card used in our protocol either has an integer written on the front side (e.g.
) or is a blank card with nothing written on the front side (
). All cards have indistinguishable back sides denoted by
.
2.2 Pile-Shifting Shuffle
Given a matrix M of cards, a pile-shifting shuffle [34] shifts the columns of M by a uniformly random cyclic shift unknown to all parties (see Fig. 3). It can be implemented in real world by putting all cards in each column into an envelope, and letting all parties take turns to apply Hindu cuts (taking some envelopes from the bottom and putting them on the top) to the pile of envelopes.
Note that each card in M may be replaced by a stack of cards, and the protocol still works in the same way as long as every stack in the same row has the same number of cards.
Fig. 3
A pile-shifting shuffle on a \(5 \times 6\) matrix
×
2.3 Chosen Cut Protocol
Given a sequence \(C = (c_1,c_2,...,c_q)\) of q face-down cards, a chosen cut protocol [13] allows P to select a desired card \(c_i\) to use in other protocols without revealing i to V. Optionally, the protocol can also revert C back to its original state after P finishes using \(c_i\).
Fig. 4
A \(3 \times q\) matrix M constructed in Step 1 of the chosen cut protocol
×
P performs the following steps (called the first part).
1.
Construct the following \(3 \times q\) matrix M (see Fig. 4).
(a)
In Row 1, place the sequence C.
(b)
In Row 2, place a face-down
at Column i and a face-down
at each other column.
(c)
In Row 3, place a face-up
at Column 1 and a face-up
at each other column.
2.
Turn over all face-up cards. Apply the pile-shifting shuffle to M.
3.
Turn over all cards in Row 2 and locate the position of the only
. A card in Row 1 directly above this
will be the card \(c_i\) as desired.
Optionally, if P wants to revert C back to its original state, P continues the following steps (called the second part) after finishing using \(c_i\) in other protocols.
4.
Place \(c_i\) back into M at the same position.
5.
Turn over all face-up cards. Apply the pile-shifting shuffle to M.
6.
Turn over all cards in Row 3 and locate the position of the only
. Shift the columns of M cyclically such that this
moves to Column 1. M is now reverted back to its original state.
Note that each card in C may be replaced by a stack of cards, and the protocol still works in the same way as long as every stack has the same number of cards.
3 Printing Protocol
Given a \(p \times q\) matrix of cards called a template (which contains some non-blank cards, and possibly some blank cards) and another \(p \times q\) matrix of cards representing an area from the puzzle grid, all known to P but not to V. A printing protocol verifies that positions in the area corresponding to non-blank cards in the template are initially empty (consisting of all blank cards). The protocol then places all non-blank cards from the template at the corresponding positions in the area, replacing the original blank cards (see Fig. 5) without revealing any card to V.
Fig. 5
Examples of a succesful printing of numbers from a \(4 \times 5\) template onto a \(4 \times 5\) area (top) and an unsuccessful printing because of overlapping numbers (bottom)
×
P performs the following steps.
1.
Place each card from the template on top of each corresponding card from the area, creating pq stacks of two cards.
2.
For each of the pq stacks, perform the following steps.
(a)
Apply the first part of the chosen cut protocol to select a blank card. (If the preconditions are met, at least one card must be blank; if both cards are blank, P can select any of them.)
(b)
Reveal the selected card that it is a blank card (otherwise V rejects) and remove it from the stack.
After these steps, all non-blank cards from the template are placed at the corresponding positions in the area. V is also convinced that these positions in the area were initially empty (consisting of all blank cards) before the protocol.
Using the printing protocol, P can separately print each region in the partition onto the grid to construct P’s solution of a decomposition puzzle. V will be convinced that the regions do not overlap with one another.
4 ZKP Protocol for Five Cells
First, from the solution of Five Cells, one can fill a number on every cell according to the rule of the puzzle (the number in each cell being the number of edges of that cell that are borders of pentominoes). We call this instance an extended solution of the puzzle.
The key observation is that there are only \(\Theta (1)\) different types of pentomino. Namely, there are 63 of them [18].3 Furthermore, inside each type of pentomino in the extended solution, the number in each cell is fixed for that type. Therefore, we need to construct only 63 different templates.
In our protocol, P constructs 63 templates, one for each type of pentomino. Each template has size \(5 \times 5\) (as the height and length of a pentomino are at most five), and the pentomino is placed at the top-left corner of the template. A cell inside the pentomino is represented by a card with a number equal to the number of edges of that cell that are borders of the pentomino, while a cell outside the pentomino is represented by a blank card (see Fig. 6).
Fig. 6
Templates of the X-shaped pentomino and the P-shaped pentomino
×
4.1 Main Protocol
Initially, P publicly places a blank card on every cell in the grid. To handle edge cases, P publicly appends four rows and four columns of “dummy” blank cards to the bottom and to the right of the grid. Then, P turns all card face-down. We now have an \((m+4) \times (n+4)\) matrix of cards.
Observe that if we arrange all \((m+4)(n+4)\) cards in the matrix into a single sequence \(A=(a_1,a_2,...,a_{(m+4)(n+4)})\), starting at the top-left corner and going from left to right in Row 1, then from left to right in Row 2, and so on, we can locate exactly where the four neighbors of any given card are. Namely, the cards on the neighbor to the left, right, top, and bottom of a cell containing \(a_i\) are \(a_{i-1}\), \(a_{i+1}\), \(a_{i-n-4}\), and \(a_{i+n+4}\), respectively.
Also, P constructs 63 templates of all 63 types of pentomino and lets V verify that all templates are correct (otherwise V rejects).
Suppose that in P’s extended solution, the grid is partitioned into k pentominoes \(B_1,B_2,...,B_k\), where \(k=mn/5\). For each \(i=1,2,...,k\), P performs the following steps.
1.
Apply the first part of the chosen cut protocol to select a \(5 \times 5\) area containing pentomino \(B_i\) in the same position as in its corresponding template. (To be precise, P selects just the top-left corner cell of the area, and the rest will follow as the chosen cut protocol preserves the cyclic order).
2.
Apply the first part of the chosen cut protocol to select a template of a pentomino with the same type as \(B_i\).
3.
Apply the printing protocol on the selected template and the selected area. Continue the second part of the chosen cut protocol invoked in Step 1 to revert the grid into its original state.
4.
Reconstruct a template that has just been used and replenish the pile of templates with it. Let V verify again that all 63 templates are correct (otherwise V rejects). Note that V does not know which template has been used.
Finally, P reveals all cards on the cells that contain a number (in the original Five Cell puzzle). V verifies that the numbers on the cards match the numbers in the cells (otherwise V rejects). P also reveals all dummy cards that they are still blank. If all verification steps pass, then V accepts.
This protocol uses \(\Theta (mn)\) cards and \(\Theta (mn)\) shuffles.
4.2 Proof of Correctness and Security
We will prove the perfect completeness, perfect soundness, and zero-knowledge properties of this protocol.
Lemma 1
(Perfect Completeness) If P knows a solution of the Five Cells puzzle, then V always accepts.
Proof
Suppose P knows an extended solution of the puzzle. Consider each i-th iteration of the main protocol.
In Step 3, since \(B_1,B_2,...,B_k\) form a partition of the grid, \(B_i\) does not overlap with \(B_1,B_2,...,B_{i-1}\). Thus, the printing protocol will pass, and the numbers in \(B_i\) will be printed on the grid.
In Step 4, P reconstructs a template that has just been used, so this step will pass.
Therefore, every iteration will pass. After k iterations, all numbers in P’s extended solution will be printed on the grid, so all numbers in the original puzzle will match the numbers on the corresponding cards.
Hence, we can conclude that V always accept. \(\square \)
Lemma 2
(Perfect Soundness) If P does not know a solution of the Five Cells puzzle, then V always rejects.
Proof
We will prove the contrapositive of this statement. Suppose V accepts, which means the verification passes in all steps. Consider the main protocol.
Since Step 4 passes for every iteration, all 63 templates are correct after each iteration (and also at the beginning of the protocol), which implies the numbers printed in every iteration form a shape of a pentomino and follow the rule of the puzzle.
In Step 3, since the printing protocol passes for every iteration, \(B_i\) does not overlap with \(B_1,B_2,...,B_{i-1}\) for every i. Also, the combined area of \(B_1,B_2,...,B_k\) is \(5k=mn\), which implies \(B_1,B_2,...,B_k\) must form a partition of the grid.
Since the final verification passes, all numbers in the original puzzle match the numbers on the corresponding cards.
Hence, we can conclude that the original puzzle grid is partitioned into pentominoes according to the rule, which means P must know a valid solution of the puzzle. \(\square \)
Lemma 3
(Zero-Knowledge) During the verification, V obtains no information about P’s solution.
Proof
We will prove that the interaction between P and V can be simulated by a simulator S that does not know P’s solution. It is sufficient to show that all distributions of cards that are turned face-up can be simulated by S.
In Steps 3 and 6 of the chosen cut protocol in Sect. 2.3, the
has probability 1/q to be at each of the q columns (due to the pile-shifting shuffles), so these two steps can be simulated by S.
In Step 2(b) of the printing protocol in Sect. 3, there is only one deterministic pattern of the cards that are turned face-up (all blank cards), so this step can be simulated by S.
In Step 4 of the main protocol, there is only one deterministic pattern of the cards that are turned face-up (all correct templates), so this step can be simulated by S.
Hence, we can conclude that V obtains no information about P’s solution. \(\square \)
5 ZKP Protocol for Meadows
The key observation is that there are only n different sizes of square in the solution of Meadows. Therefore, we need to construct only n different templates.
In our protocol, P constructs n templates, one for each size of square. Each template has size \(n \times n\), and the square is placed at the top-left corner of the template. A cell inside the square is represented by a
, while a cell outside the square is represented by a blank card (see Fig. 7).
Fig. 7
\(5 \times 5\) templates of squares with side lengths 2 (left) and 4 (right)
×
5.1 Main Protocol
Initially, P publicly places a blank card on every cell in the grid. To handle edge cases, P publicly appends \(n-1\) rows and \(n-1\) columns of “dummy” blank cards to the bottom and to the right of the grid. Then, P turns all card face-down. We now have an \((2n-1) \times (2n-1)\) matrix of cards.
Also, P constructs n templates of all n sizes of square and lets V verify that all templates are correct (otherwise V rejects).
Let \(d_1,d_2,...,d_k\) be the dotted cells in the grid. Suppose that in P’s solution, the grid is partitioned into k squares \(B_1,B_2,...,B_k\), with each square \(B_i\) containing cell \(d_i\). For each \(i=1,2,...,k\), P performs the following steps.
1.
Apply the first part of the chosen cut protocol to select an \(n \times n\) area whose top-left corner is the top-left corner of square \(B_i\). (To be precise, P selects just the top-left corner cell of the area, and the rest will follow).
2.
Apply the first part of the chosen cut protocol to select a template of a square with the same size as \(B_i\).
3.
Apply the printing protocol on the selected template and the selected area. Continue the second part of the chosen cut protocol invoked in Step 1 to revert the grid into its original state.
4.
Turn over cards on cells \(d_i,d_{i+1},...,d_k\) to show that the card on \(d_i\) is a , and the cards on \(d_{i+1},d_{i+2},...,d_k\) are all blank cards (otherwise V rejects).
5.
Reconstruct a template that has just been used and replenish the pile of templates with it. Let V verify again that all n templates are correct (otherwise V rejects). Note that V does not know which template has been used.
Finally, P reveals all cards in the grid that they are all s (otherwise V rejects). P also reveals all dummy cards that they are still blank. If all verification steps pass, then V accepts.
This protocol uses \(\Theta (n^3)\) cards and \(\Theta (kn^2)\) shuffles.
5.2 Proof of Correctness and Security
We will prove the perfect completeness, perfect soundness, and zero-knowledge properties of this protocol.
Lemma 4
(Perfect Completeness) If P knows a solution of the Meadows puzzle, then V always accepts.
Proof
Suppose P knows a solution of the puzzle. Consider each i-th iteration of the main protocol.
In Step 3, since \(B_1,B_2,...,B_k\) form a partition of the grid, \(B_i\) does not overlap with \(B_1,B_2,...,B_{i-1}\). Thus, the printing protocol will pass, and all
s in \(B_i\) will be printed on the grid.
In Step 4, since all
s inside \(B_i\) have already been printed, and all
s inside \(B_{i+1},B_{i+2},...,B_k\) have not yet been printed, this step will pass.
In Step 5, P reconstructs a template that has just been used, so this step will pass.
Therefore, every iteration will pass. After k iterations, all cells in the grid will be printed with
s, so the final verification will also pass.
Hence, we can conclude that V always accept. \(\square \)
Lemma 5
(Perfect Soundness) If P does not know a solution of the Meadows puzzle, then V always rejects.
Proof
We will prove the contrapositive of this statement. Suppose V accepts, which means the verification passes in all steps. Consider the main protocol.
Since Step 5 passes for every iteration, all n templates are correct after each iteration (and also at the beginning of the protocol), which implies the
s printed in every iteration form a shape of a square.
Since Step 4 passes for every iteration, the square printed in each i-th iteration must contain exactly one dotted cell, which is \(d_i\).
In Step 3, since the printing protocol passes for every iteration, \(B_i\) does not overlap with \(B_1,B_2,...,B_{i-1}\) for every i. Also, since the final verification passes, the combined area of \(B_1,B_2,...,B_k\) must cover the whole grid, i.e. \(B_1,B_2,...,B_k\) form a partition of the grid.
Hence, we can conclude that the puzzle grid is partitioned into squares, with each one contaning exactly one dotted cell, which means P must know a valid solution of the puzzle. \(\square \)
Lemma 6
(Zero-Knowledge) During the verification, V obtains no information about P’s solution.
Proof
We will prove that the interaction between P and V can be simulated by a simulator S that does not know P’s solution. It is sufficient to show that all distributions of cards that are turned face-up can be simulated by S.
The zero-knowledge property of the chosen cut protocol and the printing protocol has been proved in the proof of Lemma 3, so it is sufficient to consider only the main protocol.
In Step 4, there is only one deterministic pattern of the cards that are turned face-up, so this step can be simulated by S.
In Step 5, there is only one deterministic pattern of the cards that are turned face-up (all correct templates), so this step can be simulated by S.
Hence, we can conclude that V obtains no information about P’s solution. \(\square \)
6 Future Work
We constructed the printing protocol, which can be used to develop ZKP protocols for decompositon puzzles.4 However, the limitation of this protocol is that the number of different possible types of region (which is equal to the number of templates we need to prepare) must be polynomially bounded. A possible future work is to find a technique to deal with decompositon puzzles which the number of different possible types of region are exponentially bounded, e.g. Fillomino.
Acknowledgements
The authors would like to thank the anonymous reviewers of LATINCRYPT 2023 who kindly suggested the main idea of the printing protocol. Without them, this paper would not have been possible. The authors would also like to thank Kyosuke Hatsugai, Yoshiki Abe, and Tomoki Ono for a valuable discussion on this research. This work was supported by JSPS KAKENHI Grant Numbers JP23H00468, JP23H00479, JP23K17455, JP22H03590, JP21H03395, and JST CREST JPMJCR23M2.
Declarations
Conflict of interest
The authors have no relevant financial or non-financial interests to disclose.
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Although there exists a card-based ZKP for Shikaku [28], the protocol uses a technique specifically designed for Shikaku, which cannot be applied to Meadows.
Among these puzzles, only Shikaku is a decomposition puzzle, and its ZKP protocol [28] uses a completely different approach from the one in this paper.
The printing protocol can also be used to construct a ZKP for Shikaku. However, for an \(m \times n\) Shikaku grid, we need to prepare mn templates, each having size \(m \times n\), resulting in the total of \(\Theta (m^2n^2)\) cards, while the existing ZKP protocol [28] uses only \(\Theta (mn)\) cards.
) or is a blank card with nothing written on the front side (
). All cards have indistinguishable back sides denoted by
.
at Column i and a face-down
at each other column.
at Column 1 and a face-up
at each other column.
. A card in Row 1 directly above this
will be the card \(c_i\) as desired.
. Shift the columns of M cyclically such that this
moves to Column 1. M is now reverted back to its original state.
has probability 1/q to be at each of the q columns (due to the pile-shifting shuffles), so these two steps can be simulated by S.
, while a cell outside the square is represented by a blank card (see Fig. 7).
s (otherwise V rejects). P also reveals all dummy cards that they are still blank. If all verification steps pass, then V accepts.
, and the cards on \(d_{i+1},d_{i+2},...,d_k\) are all blank cards (otherwise V rejects).
s, so the final verification will also pass.
s in \(B_i\) will be printed on the grid.
s inside \(B_i\) have already been printed, and all
s inside \(B_{i+1},B_{i+2},...,B_k\) have not yet been printed, this step will pass.
s printed in every iteration form a shape of a square.
