Der Artikel führt ein physikalisches Null-Wissen-Proof-Protokoll für das Sukoro-Rätsel ein, ein logisches Rätsel, das von Nikoli eingeführt wurde. Das Protokoll verifiziert drei Bedingungen: Nachbarschaft, Nachbarschaft und Konnektivität. Die Konnektivitätsbedingung, die sicherstellt, dass alle gefüllten Zellen miteinander verbunden sind, ist besonders schwierig zu überprüfen, ohne die Lösung zu enthüllen. Die Autoren schlagen eine neue Methode mit dem Namen Vermehrungsverfahren vor, um diese Verifikation in einem nicht-interaktiven Umfeld zu erreichen, in dem der Prüfer nicht aktiv am Verifikationsprozess teilnehmen muss. Diese Methode propagiert Verpflichtungen auf dem gesamten Puzzlebrett und stellt sicher, dass alle gefüllten Zellen miteinander verbunden sind. Das Protokoll verwendet ein Kartenspiel mit binären Karten und verschiedene Mischtechniken, um die Sicherheits- und Null-Wissen-Eigenschaften des Beweises aufrechtzuerhalten. Der Artikel behandelt auch die Vollständigkeit, Solidität und Nullinformationseigenschaften des Protokolls sowie seine Effizienz hinsichtlich der Anzahl der benötigten Karten und Mischungen. Die Autoren lassen die Möglichkeit offen, die Konnektivitätsbedingung mit einer geringeren Anzahl von Shuffles bei gleichbleibender Sicherheit zu überprüfen.
KI-Generiert
Diese Zusammenfassung des Fachinhalts wurde mit Hilfe von KI generiert.
Abstract
A zero-knowledge proof protocol is a cryptographic protocol in which a prover, who knows the witness to a statement, can convince a verifier that the statement is true without revealing any information about the witness. Although zero-knowledge proof protocols are typically executed on electronic computers, there is a line of research to design zero-knowledge proof protocols based on physical objects (e.g., a deck of cards). This is called physical zero-knowledge proof. In this paper, we construct a physical zero-knowledge proof protocol for a logical puzzle called Sukoro. Sukoro has many cells on the puzzle board, like Sudoku, where each cell must be empty or filled with a number from one to four, and each number must match the number of adjacent filled cells, and the same numbers must not be adjacent to each other. In addition, it has a rule that all filled cells must be connected, which is called the connectivity condition. Although some existing protocols deal with the connectivity condition, all existing methods are interactive, which requires the prover’s knowledge to determine how the cards are manipulated during the execution of the protocols. In this paper, we give a new method for verifying the connectivity condition in the non-interactive setting, which means that the protocol can be executed without the prover’s knowledge, and construct a physical zero-knowledge proof protocol for Sukoro.
Hinweise
K. Shinagawa, who is the corresponding author of this paper, is supported by Japan Society for the Promotion of Science KAKENHI 21K17702 and 23H00479, and JST CREST Grant Number MJCR22M1.
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
1 Introduction
A zero-knowledge proof (ZKP) protocol, introduced by Goldwasser, Mikali, and Rackoff [6], is an interactive cryptographic protocol between a prover P and a verifier V in which P, who has the witness to a statement, can convince V that the statement is true without revealing any information about the witness. Although ZKP protocols are typically implemented on electronic computers, there is a line of research to design ZKP protocols based on physical objects such as cards and envelopes. This line of research is called physical zero-knowledge proof.
A ZKP protocol for a puzzle is a ZKP protocol for the statement that there exists an answer to the puzzle. In particular, the prover P who has a solution to the puzzle can convince the verifier V of the existence of a solution to the puzzle without revealing the solution itself. There is a line of research to design physical ZKP protocols for puzzles: Sudoku [7, 22, 31], Slitherlink [12], Cryptarithmetic [9], Kakuro [2, 15], Makaro [3, 30], Takuzu [2, 14], Juosan [14], KenKen [2], Akari [2], Norinori [4], Ripple Effect [26], Suguru [17, 21], Nurikabe [18], Hitori [18], Heyawake [18], Numberlink [25], Bridges [27], Nonogram [24], ABC End View [5], Shikaku [29], Nurimisaki [19], and Usowan [20]. Recently, physical ZKP protocols for non-puzzle problems are also proposed: Pancake Sorting [11], Topswops [10], and some graph problems [13, 27].
Anzeige
In this paper, we propose a zero-knowledge proof protocol for a new puzzle Sukoro. Sukoro is one of the logical puzzles introduce by Nikoli, which is the famous puzzle company for Sudoku. See Fig. 1 for an example of an instance and the solution of Sukoro. The rule of Sukoro is given as follows:
(1)
Place a number from 1 to 4 in some empty cells. Here, it is not necessary to fill all empty cells with numbers.
(2)
Adjacency condition: The same number cannot be adjacent vertically or horizontally.
(3)
Neighborhood condition: A number in a cell indicates the number of filled cells vertically or horizontally adjacent to the cell.
(4)
Connectivity condition: All filled cells are connected vertically or horizontally.
Of the three conditions, the connectivity condition is the most difficult to verify without revealing the solution. The connectivity condition for Nurikabe, Hitori, and Heyawake is solved by Robert, Miyahara, Lafourcade, and Mizuki [18]. However, their solution is interactive, which requires a prover P’s knowledge to determine how the cards are manipulated during executions of protocols. On the other hand, in the non-interactive setting, it is possible for the prover to just place cards and then let the verifier (or even a third party) operate the entire protocol, while the prover only observes to ensure that they operate the protocol correctly. To the best of our knowledge, verifying the connectivity condition in the non-interactive setting has not yet been addressed in the existing physical ZKP protocols. Note that it is nontrivial to verify the connectivity condition in the non-interactive setting, since the non-interactive setting is harder to achieve than the interactive setting due to the inability to use P’s knowledge. Our technical contribution is to design a protocol verifying the connectivity condition in the non-interactive setting. To achieve this, we use a new method which we name the propagation procedure, which “propagate” the commitment to 1 for all filled cells in the puzzle board (see Sect. 3.1.4).
Fig. 1
A puzzle instance (left) and its solution (right) of Sukoro
×
2 Preliminaries
In this section, we introduce basic definitions and notations.
2.1 Cards and Encodings
In this paper, we use a deck of binary cards where the front is either or and the back is the same pattern . A pair of two cards are used to encode one bit as follows:
A pair of two face-down cards following the above encoding is called a commitment.
An integer \(x \in \{0, 1, \ldots , k-1\}\) can be encoded by k cards consisting of one
and \(k-1\)s as follows:
A sequence of face-down cards following this encoding rule is called a \(\heartsuit \)-scheme of x, denoted by \(E^{\heartsuit }_{k}(x)\). For an integer \(x \not \in \{0, 1, \ldots , k-1\}\), the \(\heartsuit \)-scheme of x is defined by \(E^{\heartsuit }_{k}(x \bmod k)\). Similarly, a \(\clubsuit \)-scheme of x, denoted by \(E^{\clubsuit }_{k}(x)\), is defined by a sequence of face-down cards with the following encoding rule:
Note that \(E^{\clubsuit }_{2}(x)\) is exactly the same as a commitment to x. We also note that shifting \(E^{\heartsuit }_{k}(x)\) and \(E^{\clubsuit }_{k}(x)\) to the right by one card results in \(E^{\heartsuit }_{k}(x+1)\) and \(E^{\clubsuit }_{k}(x+1)\), respectively.
Anzeige
2.2 Pile-Scramble Shuffle
A pile-scramble shuffle is a shuffle proposed by Ishikawa, Chida, and Mizuki [8] in the literature to generate a uniformly random no-fixed-point permutation. This is a shuffle on a card sequence \((p_1, p_2, \ldots , p_m)\) of m piles of the same number of cards, and outputs a card sequence \((p_{\pi ^{-1}(1)}, p_{\pi ^{-1}(2)}, \ldots , p _{\pi ^{-1}(m)})\) for a permutation \(\pi \in S_m\) chosen uniformly at random. This operation can be easily implemented with m physical envelopes by putting each pile \(p_i\) of cards into the i-th envelope and scrambling these envelopes. In this paper, we use a matrix representation to denote a pile-scramble shuffle as follows:
where \(p'_i = p_{\pi ^{-1}(i)}\) for \(1 \le i \le m\).
For a special case, a pile-scramble shuffle when \(m = 2\) is usually called a random bisection cut, which was proposed by Mizuki and Sone [16] before the pile-scramble shuffles. In this paper, we denote a random bisection cut as follows:
2.3 Pile-Shifting Shuffle
A pile-shifting shuffle is a shuffle on a card sequence \((p_0, p_1, \ldots , p_{m-1})\) of m piles of the same number of cards, and outputs a card sequence \((p_{r}, p_{r+1}, \ldots , p _{r+m-1})\) for an integer \(0 \le r \le m-1\) chosen uniformly at random. Similar to the pile-scramble shuffle, a pile-shifting shuffle can be easily implemented with m physical envelopes and we use a matrix representation to denote a pile-shifting shuffle as follows:
where \(p'_i = p_{r+i}\) for \(0 \le i \le m-1\).
2.4 Existing Protocols for AND, XOR, and COPY
Mizuki and Sone [16] proposed a six-card AND protocol, a four-card XOR protocol, and a six-card COPY protocol.
The six-card AND protocol takes two commitments to \(x,y \in \{0,1\}\) and outputs a commitment to \(x\wedge y\) as follows:
The protocol proceeds as follows:
(1)
Place two commitments and two cards as follows:
(2)
Turn face-up cards and rearrange the card sequence as follows:
(3)
Apply a random bisection cut as follows:
(4)
Rearrange the card sequence as follows:
(5)
Open the first and second cards, then a commitment to \(x \wedge y\) is obtained as follows:
Note that the six-card OR protocol can be easily obtained from the above AND protocol using De Morgan’s law.
The four-card XOR protocol takes two commitments to \(x,y \in \{0,1\}\) and outputs a commitment to \(x\oplus y\) as follows:
The protocol proceeds as follows:
(1)
Place two commitments as follows:
item[(2)] Rearrange the card sequence as follows:
(3)
Apply a random bisection cut as follows:
(4)
Rearrange the card sequence as follows:
(5)
Open the first and second cards, then a commitment is obtained as follows:
The six-card COPY protocol takes a commitment to \(x \in \{0,1\}\) and outputs two copies of it as follows:
The protocol proceeds as follows:
(1)
Place a commitment and four cards as follows:
(2)
Turn face-up cards and rearrange the card sequence as follows:
(3)
Apply a random bisection cut as follows:
(4)
Rearrange the card sequence as follows:
(5)
Open the first and second cards, then a commitment is obtained as follows:
For any integer \(k \ge 2\), we can make k copies of the commitment using k pairs of as additional cards.
2.5 Existing Copy Protocol for Integer Encoding
Ruangwises [23] proposed a copy protocol for \(\heartsuit \)-scheme. The protocol requires one pile-shifting shuffles only. The protocol takes a \(\heartsuit \)-scheme of x and outputs two copies as follows:
(1)
Reverse the \(n-1\) rightmost cards of \(E^{\heartsuit }_{n}(x)\) as follows, resulting in \(E_n^\heartsuit (-x)\):
(2)
Place two copies of \(E^{\heartsuit }_{n}(0)\) under \(E^{\heartsuit }_{n}(-x)\) as follows:
(3)
Apply a pile-shifting as follows:
(4)
Open the top row of cards. Shift the matrix so that the column having will be the leftmost as follows:
Then the middle sequence and the bottom sequence are the copies of \(E^{\heartsuit }_{n}(x)\). (Note that, when it is used as a subprotocol of a zero-knowledge proof protocol, this step also verifies that the input sequence is in a correct format. In particular, if the number of is not one, or the number of s is not \(n-1\), then the verifier will reject the proof.)
2.6 Existing Addition Protocol
Ruangwises and Itoh [28] proposed an addition protocol that takes n commitments to \(x_1,x_2,\ldots ,x_n \in \{0,1\}\) and outputs a \(\heartsuit \)-scheme of \(s = x_1+x_2+\cdots +x_n\) as follows:
The protocol proceeds as follows:
(1)
Place n commitments and two cards as follows:
(2)
Take the commitments to \(x_1\) and \(x_2\). Place right next to the commitment to \(x_1\), and in the middle of the commitment to \(x_2\). By turning the face-up cards, we can observe that they are \(E^{\heartsuit }_{3}(x_1)\) and \(E^{\clubsuit }_{3}(-x_2)\) as follows:
(3)
Place \(E^{\clubsuit }_{3}(-x_2)\) to the bottom of \(E^{\heartsuit }_{3}(x_1)\) and apply a pile-shifting shuffle as follows:
Here, the top sequence will be \(E^{\heartsuit }_{3}(x_1 + r)\) and the bottom sequence will be \(E^{\clubsuit }_{3}(- x_2 + r)\), where r is the number of shifts in the pile-shifting shuffle.
(4)
Open the bottom sequence \(E^{\clubsuit }_{3}(- x_2 + r)\) and reveals \(x'_2:= - x_2 + r\). Shift the card sequence to the right by \(x'_2\) as follows:
Here, the top sequence is \(E^{\heartsuit }_{3}(x_1 + x_2)\) because \(x_1 + r + x'_2 = x_1 + r + (x_2 - r) = x_1 + x_2\).
(5)
Take the commitments to \(x_3\). Place right next to \(E^{\heartsuit }_{3}(x_1 + x_2)\), and in the middle of the commitment to \(x_3\). By turning the face-up cards, we can observe that they are \(E^{\heartsuit }_{4}(x_1 + x_2)\) and \(E^{\clubsuit }_{4}(-x_3)\) as follows:
Similar to Steps (3) and (4), make \(E^{\heartsuit }_{4}(x_1 + x_2 + x_3)\) and the free cards .
(6)
Repeat Step (5) from \(x_4\) to \(x_n\) and obtain \(E^{\heartsuit }_{n+1}(x_1 + \cdots + x_n)\).
The number of cards and shuffles of the protocol is \(2n+2\) and \(n-1\), respectively, and the type of shuffles is a pile-shifting shuffle, which is a random cyclic shift of a sequence of piles.
3 Zero-knowledge Proof Protocol for Sukoro
In this section, we propose a physical zero-knowledge proof protocol for Sukoro. Our protocol verifies the neighborhood, adjacency, and connectivity conditions, in this order.
3.1 Our Protocol
For simplicity, we assume that a puzzle board of Sukoro consists of \(k \times k\) cells. Each cell is represented by \((i,j) \in [k]\times [k]\). A hint cell is a cell filled with a number at the beginning. A filled cell is a cell filled with a number in the solution. (Note that a hint cell is a filled cell.) An empty cell is a cell other than filled cells.
For a cell \(\alpha \in [k]\times [k]\), we define an integer \(A_{\alpha } \in \{0, 1, 2, 3, 4, 5\}\) and a binary number \(B_{\alpha } \in \{0,1\}\) as follows. If \(\alpha \) is a filled cell, \(A_{\alpha }\) is set to be the number written on it, according to the prover’s solution. Note that, from the connectivity condition, it must hold \(1 \le A_{\alpha } \le 4\) in this case. If \(\alpha \) is an empty cell, the integer \(A_{\alpha }\) is set to 0 or 5 so that any adjacent empty cells vertically or horizontally do not have the same number. Specifically, the integer \(A_{(i,j)}\) is set to 0 when \(i+j\) is even and 5 when \(i+j\) is odd. The binary number \(B_{\alpha }\) is set to \(B_{\alpha } = 1\) if \(\alpha \) is a filled cell and \(B_{\alpha } = 0\) if \(\alpha \) is an empty cell.
Our protocol consists of four phases: (1) arrangement of cards (Sect. 3.1.1), (2) verification of the adjacency condition (Sect. 3.1.2), (3) verification of the neighborhood condition (Sect. 3.1.3), and (4) verification of the connectivity condition (Sect. 3.1.4).
3.1.1 Arrangement of Cards from the Solution
First, the prover and the verifier perform the following procedure for each cell \(\alpha \in [k]\times [k]\).
(1)
The prover makes a \(\heartsuit \)-scheme \(E^{\heartsuit }_{6}(A_{\alpha })\) and a commitment to \(B_{\alpha } \in \{0,1\}\), and places them on the cell \(\alpha \). Let \(S_{\alpha }\) be the (concatenated) card sequence on \(\alpha \) as follows:
Hereafter, the commitment to \(B_{\alpha }\) is called an filled-or-empty commitment since it is 1 if the cell is filled and 0 otherwise.
(2)
The verifier checks that there are 8 face-down cards on each cell \(\alpha \). If \(\alpha \) is a hint cell, the verifier also check that \(A_{\alpha }\) is a correct number and \(B_{\alpha } = 1\) by opening these cards. The verifier rejects if any of the above checks fail. If all the checks pass, all the face-up cards are closed.
Since each cell has 8 cards, the number of cards used in this phase is \(8k^2\).
3.1.2 Verification of Adjacency Condition
In this section, we verify that two adjacent cells do not encode the same integer. (Recall that adjacent empty cells also do not have same integer.) The prover and the verifier perform the following procedure for each adjacent cells \(\alpha , \beta \in [k]\times [k]\). It is based on the existing method [3], although our protocol does not use number cards unlike [3].
(1)
Copy \(E^{\heartsuit }_6(A_{\alpha })\) and \(E^{\heartsuit }_6(A_{\beta })\) using the copy protocol in Sect. 2.5. Make a \(2\times 6\) matrix from a copy of \(E^{\heartsuit }_6(A_{\alpha })\) and a copy of \(E^{\heartsuit }_6(A_{\beta })\) as follows:
(2)
Apply a pile-scramble shuffle to the matrix as follows:
(3)
Open all cards in the matrix. If two s do not appear in the same row, continue the protocol. Otherwise, the verifier rejects. The following is an example of the result.
The number of additional cards used in this phase is 18 binary cards because the copy protocols for \(E^{\heartsuit }_6(A_{\alpha })\) and \(E^{\heartsuit }_6(A_{\beta })\) require 12 additional cards, respectively, but among 24 cards, 6 cards can be reused. The number of shuffles used in the above procedure is only one; thus the total number of shuffles in this phase is \(2k(k-1)\) since the number of adjacent cells is \(2k(k-1)\).
3.1.3 Verification of Neighborhood Condition
In this section, for each cell \(\alpha \), we sum the number of filled cells around it, and check if the sum is equal to the integer of the cell. However, if that cell itself is empty cell, the sum does not have to be equal. Therefore, we make a dummy sequence that will always pass the verification. The commitment \(B_{\alpha }\) acts like a switch to select either the real sum or a dummy sequence. We also verify that the integer is neither 0 nor 5 when the real sum is chosen. This is why we remove the cards on \((p_0, p_5, q_0)\) after Step (3) in the protocol.
The prover and the verifier perform the following procedure for each cell \(\alpha \in [k]\times [k]\). For simplicity, we consider the case where \(\alpha \) has four neighborhood cells vertically or horizontally. (If \(\alpha \) is at the edge or the corner of the board, there may be only three or two cells vertically or horizontally but the verification of this case can be done in the same manner.) Let \(\beta ,\gamma ,\delta ,\epsilon \in [k]\times [k]\) be the four neighborhood cells.
(1)
Copy the commitments to \(B_{\alpha }, B_{\beta }, B_{\gamma }, B_{\delta }\), and \(B_{\epsilon }\) using the copy protocol in Sect. 2.4.
(2)
Apply the addition protocol in Sect. 2.6 to the four filled-or-empty commitments \(B_{\beta }, B_{\gamma }, B_{\delta }, B_{\epsilon }\) as follows:
Arrange \(E^{\heartsuit }_{6}(A_{\alpha })\) and \(E^{\heartsuit }_{5}(B)\) as follows:
Note that if \(A_{\alpha } \not \in \{0,5\}\) and \(B \ge 1\), the three cards on \((p_0, p_5, q_0)\) are .
(4)
Apply a pile-scramble shuffle to the rightmost four piles as follows:
We refer to the resultant sequence of 8 cards as S.
(5)
Arrange the free cards and turn them face-down as follows:
(6)
Apply a pile-scramble shuffle to the sequence as follows:
We refer to the resultant sequence of 8 cards as \(S_{\textsf{dummy}}\).
(7)
Rearrange \(B_{\alpha }\), S, and \(S_{\textsf{dummy}}\) as follows:
(8)
Apply a random bisection cut as follows:
(9)
Open the leftmost card in each pile as follows:
(10)
Open the 8 cards right next to . If there is a pair of , the protocol continues. Otherwise, the verifier rejects. The following is an example of the result.
The number of required free cards used in this phase is 16 cards: 6 pairs of and 4 s. Since we have 18 free cards (3 pairs of ) in the previous phase, we additionally need 3 s. Note that after executing this phase, we have \(6k^2 (+ \epsilon )\) additional free cards since all \(E^{\heartsuit }_{6}(A_{\alpha })\) are opened. The number of shuffles used in the above procedure is 11 if \(\alpha \) has four neighborhood cells, 9 if \(\alpha \) has three neighborhood cells, and 7 if \(\alpha \) has two neighborhood cells. Thus the total number of shuffles in this phase is \(11(k-2)^2 + 36(k-2) + 28 = 11k(k - 8)\) because the number of cells having four neighbors, three neighbors, and two neighbors is \((k-2)^2\), \(4(k-2)\), and 4, respectively.
3.1.4 Verification of Connectivity Condition
Let \(\alpha ^* \in [k]\times [k]\) be a hint cell. The prover and the verifier perform the following procedure:
(1)
Place a commitment to 1 on \(\alpha ^*\) and a commitment to 0 in the other cells. (These commitments are called propagation commitments.)
(2)
The following procedure, which we call the propagation protocol, is repeated \(\ell \) times, where \(\ell \) will be defined later.
Propagation protocol
For each cell, apply the single-step propagation protocol, which will be explained below. (Here, the order of cells to be applied is arbitrary.)
(3)
Open the propagation commitments on all hint cells. The verifier accepts if all of them are 1, and rejects if any of them are 0.
Now we describe the single-step propagation protocol for a cell \(\alpha \in [k]\times [k]\). For simplicity, we consider the case where \(\alpha \) has four neighborhood cells vertically or horizontally. (If \(\alpha \) is at the edge of the board, there may be only three or two cells vertically or horizontally, but the verification can be performed in the same way.) Let \(\beta ,\gamma ,\delta ,\epsilon \in [k]\times [k]\) be the four cells. Let \(I_{\alpha }, I_{\beta }, I_{\gamma }, I_{\delta }, I_{\epsilon } \in \{0,1\}\) be the current values of the propagation commitments placed on \(\alpha , \beta ,\gamma ,\delta \), and \(\epsilon \), respectively. (Note that they are initially 0 except one hint cell \(\alpha ^*\).) It proceeds as follows:
(1)
Copy the commitments to \(B_{\alpha }, I_{\alpha }, I_{\beta }, I_{\gamma }, I_{\delta }\), and \(I_{\epsilon }\) using the copy protocol in Sect. 2.4.
(2)
Using the OR protocol in Sect. 2.4, compute the commitment to \(I'_{\alpha }:= I_{\alpha } \vee I_{\beta } \vee I_{\gamma } \vee I_{\delta } \vee I_{\epsilon }\).
(3)
Using the AND protocol in Sect. 2.4, compute the commitment to \(I''_{\alpha }:= I'_{\alpha } \wedge B_{\alpha }\) as follows:
This is the new propagation commitment of \(\alpha \).
We do not need new additional cards in this phase since we have a sufficient number of free cards from the previous phases. The number of shuffles used in the single-step propagation protocol is 11 if \(\alpha \) has four neighborhood cells, 9 if \(\alpha \) has three neighborhood cells, and 7 if \(\alpha \) has two neighborhood cells. Thus the number of shuffles in the propagation protocol is \(11(k-2)^2 + 36(k-2) + 28 = 11k^2-8k\) because the number of cells having four neighbors, three neighbors, and two neighbors is \((k-2)^2\), \(4(k-2)\), and 4, respectively. Therefore, the total number of shuffles in this phase is \(\ell k(11k-8)\), where \(\ell \) is the number of repetition of the propagation protocol. Now we estimate the sufficient number \(\ell \) for the propagation. Since at least one propagation commitment is propagated in the propagation protocol if the propagation has not been finished, it is sufficient to set \(\ell \) as the longest length of the shortest path between two cells in a grid. An obvious upper bound is \(\ell \le k^2\) because \(k^2\) is the size of the board. With optimization, we can show that \(\ell \le \frac{2}{3}k^2 + O(k)\). From this bound, the number of shuffles in this phase is at most \(\frac{22}{3}k^4 + O(k^2)\), which is quadratic of the board size \(k^2\).
Finally, we show an upper bound \(\ell \le \frac{2}{3}k^2 + O(k)\) on the longest length of the shortest path between two cells in a grid. The proof is from the website [1]. Let \(\alpha _0 \rightarrow \alpha _1 \rightarrow \cdots \rightarrow \alpha _{\ell }\) be a path between \(\alpha _0\) and \(\alpha _{\ell }\) without shortcuts. We will refer to each cell on the path as a black cell, and to each cell off the path as a white cell. Draw an edge from each black cell to all of its adjacent white cells. Then we have at least \(2\ell -O(k)\) edges since every black cell except one on the border of the board has at least 2 edges. On the other hand, each white cell trivially has at most 4 edges, so the number of white cells is at least \(\frac{\ell }{2} - O(k)\). Since the sum of the number of black cells and white cells is \(k^2\), we have \(k^2 \ge \ell + \frac{\ell }{2} - O(k)\), so \(\ell \le \frac{2}{3}k^2 + O(k)\). We note that the website [1] also shows that this bound is tight by showing a lower bound \(\ell \ge \frac{2}{3}k^2 + O(k)\).
3.2 Completeness of Our Protocol
We show that the verifier always accepts if the prover behaves honestly, i.e. if the cards placed on the puzzle board correspond to a solution of the puzzle. Suppose that the cards placed in Sect. 3.1.1 are correctly arranged and correspond to a solution.
First, consider the verification of the adjacency condition. Let \(\alpha , \beta \) be any adjacent cells. If \(\alpha , \beta \) are both filled cells, two integers \(A_{\alpha }\) and \(A_{\beta }\) are different from the adjacency condition. If \(\alpha \) is a filled cell and \(\beta \) is an empty cell, two integers \(A_{\alpha }\) and \(A_{\beta }\) are different because \(A_{\alpha } \in \{1,2,3,4\}\) and \(A_{\beta } \in \{0,5\}\). If \(\alpha , \beta \) are both empty cells, two integers \(A_{\alpha }\) and \(A_{\beta }\) are different because we define any adjacent empty cells do not have the same number, Therefore, in Step (3), two s do not appear in the same row and the protocol continues to the next phase.
Next, consider the verification of the neighborhood condition. In Step (11), the sequence S is opened if \(\alpha \) is a filled cell and the dummy sequence \(S_{\textsf{dummy}}\) is opened if \(\alpha \) is an empty cell. Thus, if \(\alpha \) is an empty cell, from the arrangement of Step (6), the protocol always continues. If \(\alpha \) is a filled cell, the integer \(B \in \{0,1,2,3,4\}\) representing the sum of the filled-or-empty commitments must be equal to \(A_{\alpha }\) and thus the protocol continues to the next phase.
Finally, consider the verification of the connectivity condition. By the single-step propagation protocol for a filled cell \(\alpha \), the propagation commitment on \(\alpha \) will be 1 if one of the propagation commitments in the neighbor is 1. Since there will be at least one propagation from \(\alpha ^*\) each time, the propagation commitments on all filled cells will be 1 after repeating \(\ell \) times so the verifier accepts the proof.
3.3 Soundness of Our Protocol
We show that the verifier always rejects if there is no solution to the puzzle. We note that our protocol does not prove that the cards on the puzzle board correspond to a correct solution, but rather proves the existence of a solution.
If some integer encodings or commitments are invalid (e.g., some commitment is like or some integer encoding has two or more s), they will be detected in the copy protocol. So we can assume that all integer encodings and commitments are valid and they are \((A_{\alpha }, B_{\alpha })_{\alpha \in [k]\times [k]}\).
Define \(\overline{A}:= (\overline{A}_{\alpha })_{\alpha \in [k]\times [k]}\) by \(\overline{A}_{\alpha } = A_{\alpha }\) if \(B_{\alpha } = 1\) and \(\overline{A}_{\alpha } = \bot \) otherwise. (Note that the definition of \(\overline{A}\) does not care about the value \(A_{\alpha }\) if \(B_{\alpha } = 0\). This is why we do not need to check the consistency that \(B_{\alpha } = 0\) if and only if \(A_{\alpha } \in \{0,5\}\).) If \(\overline{A}\) is not a solution of the puzzle, we have either \(\overline{A}_{\alpha } \in \{0,5\}\) for some \(\alpha \) or \(\overline{A}\) does not satisfy one of the three conditions.
Suppose \(\overline{A}_{\alpha } \in \{0,5\}\) for some \(\alpha \). In Step (3) of the verification of neighborhood condition, the three cards on \((p_0,p_5,q_0)\) contains at least one . Since \(\overline{A}_{\alpha }\ne \bot \) implies \(B_{\alpha } = 1\), in Step (10), the real sequence S will be opened. Since S contains at most one , the verifier rejects the proof.
Suppose that \(\overline{A}\) does not satisfy the adjacency condition. Then there exists adjacent cells \(\alpha , \beta \) such that \(\overline{A}_{\alpha } = \overline{A}_{\beta }\), equivalently \(A_{\alpha } = A_{\beta }\). In this case, in Step (3), two s appear in the same column. Therefore the verifier rejects the proof.
Suppose that \(\overline{A}\) does not satisfy the neighborhood condition. Then there exists a filled cell \(\alpha \) such that the number of filled cells in the neighbor is not equal to \(\overline{A}_{\alpha }\). In this case, the opened cards in Step (10) will be the lower case. Therefore the verifier rejects the proof.
Fig. 2
A puzzle instance (left), an incorrect solution that does not satisfy the connectivity condition (center), and a correct solution (right)
×
Suppose that \(\overline{A}\) does not satisfy the connectivity condition. There are two cases: (1) there are two hint cells which are not connected and (2) all hint cells are connected but there are other filled cells which are not connected to the hint cells (see Fig. 2). In the case of (2), by removing the filled cells which are not connected to the hint cells (as in the right of Fig. 2), we can obtain a solution. Thus if the cards on the board satisfy all conditions except the connectivity condition in the case of (2), there exists a solution of the puzzle. Since we are assuming that there is no solution to the puzzle, we will focus on the case of (1). In the case of (1), since there are two hint cells which are not connected, at least one propagation commitment on a hint cell remains 0. Thus the verifier rejects the proof.
3.4 Zero-Knowledge Property of Our Protocol
We show that our protocol leaks no information on the solution of the puzzle. It follows from the observation that \(A_{\alpha }\) and \(B_{\alpha }\) for all cells \(\alpha \) are hidden from the verifier due to the security of all subprotocols and the effect of the pile-scramble shuffles. Thus our protocol is zero-knowledge.
3.5 Efficiency of Our Protocol
The number of cards required for our protocol is \(8k^2+21\) binary cards. The number of shuffles required for our protocol is \(\frac{22}{3}k^4 + O(k^2)\), which is quadratic in the number of cells \(k^2\) on the board.
4 Conclusion
In this paper, we proposed a physical zero-knowledge proof protocol for a pencil puzzle called Sukoro. Our protocol requires \(\frac{2}{3}n^2 + O(n)\) shuffles, where \(n = k^2\) is the number of cells in the puzzle board. The most dominant part with respect to the number of shuffles is the phase to verify the connectivity condition. We left as an open problem to verify the connectivity condition in the non-interactive setting with smaller number of shuffles while keeping the number of cards.
Acknowledgements
The authors would like to thank Prof. Koji Nuida for his valuable comments pointing out that an incorrect solution in Fig. 2 is accepted by our protocol. This work was supported by JSPS KAKENHI Grant Numbers JP21K17702 and JP23H00479, and JST CREST JPMJCR22M1.
Declarations
Conflict of interest
The authors declare no conflict of interest associated with this manuscript. This article does not contain any studies with human participants or animals performed by any of the authors.
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.
or
and the back is the same pattern
. A pair of two cards are used to encode one bit as follows:
A pair of two face-down cards following the above encoding is called a commitment.
and \(k-1\)
s as follows:
A sequence of face-down cards following this encoding rule is called a \(\heartsuit \)-scheme of x, denoted by \(E^{\heartsuit }_{k}(x)\). For an integer \(x \not \in \{0, 1, \ldots , k-1\}\), the \(\heartsuit \)-scheme of x is defined by \(E^{\heartsuit }_{k}(x \bmod k)\). Similarly, a \(\clubsuit \)-scheme of x, denoted by \(E^{\clubsuit }_{k}(x)\), is defined by a sequence of face-down cards with the following encoding rule:
Note that \(E^{\clubsuit }_{2}(x)\) is exactly the same as a commitment to x. We also note that shifting \(E^{\heartsuit }_{k}(x)\) and \(E^{\clubsuit }_{k}(x)\) to the right by one card results in \(E^{\heartsuit }_{k}(x+1)\) and \(E^{\clubsuit }_{k}(x+1)\), respectively.
where \(p'_i = p_{\pi ^{-1}(i)}\) for \(1 \le i \le m\).
where \(p'_i = p_{r+i}\) for \(0 \le i \le m-1\).
The protocol proceeds as follows: Note that the six-card OR protocol can be easily obtained from the above AND protocol using De Morgan’s law.
The protocol proceeds as follows: The six-card COPY protocol takes a commitment to \(x \in \{0,1\}\) and outputs two copies of it as follows:
The protocol proceeds as follows: For any integer \(k \ge 2\), we can make k copies of the commitment using k pairs of
as additional cards.
item[(2)] Rearrange the card sequence as follows:
will be the leftmost as follows:
Then the middle sequence and the bottom sequence are the copies of \(E^{\heartsuit }_{n}(x)\). (Note that, when it is used as a subprotocol of a zero-knowledge proof protocol, this step also verifies that the input sequence is in a correct format. In particular, if the number of
is not one, or the number of
s is not \(n-1\), then the verifier will reject the proof.)
The protocol proceeds as follows: The number of cards and shuffles of the protocol is \(2n+2\) and \(n-1\), respectively, and the type of shuffles is a pile-shifting shuffle, which is a random cyclic shift of a sequence of piles.
right next to the commitment to \(x_1\), and
in the middle of the commitment to \(x_2\). By turning the face-up cards, we can observe that they are \(E^{\heartsuit }_{3}(x_1)\) and \(E^{\clubsuit }_{3}(-x_2)\) as follows:
Here, the top sequence will be \(E^{\heartsuit }_{3}(x_1 + r)\) and the bottom sequence will be \(E^{\clubsuit }_{3}(- x_2 + r)\), where r is the number of shifts in the pile-shifting shuffle.
Here, the top sequence is \(E^{\heartsuit }_{3}(x_1 + x_2)\) because \(x_1 + r + x'_2 = x_1 + r + (x_2 - r) = x_1 + x_2\).
right next to \(E^{\heartsuit }_{3}(x_1 + x_2)\), and
in the middle of the commitment to \(x_3\). By turning the face-up cards, we can observe that they are \(E^{\heartsuit }_{4}(x_1 + x_2)\) and \(E^{\clubsuit }_{4}(-x_3)\) as follows:
Similar to Steps (3) and (4), make \(E^{\heartsuit }_{4}(x_1 + x_2 + x_3)\) and the free cards
.
Hereafter, the commitment to \(B_{\alpha }\) is called an filled-or-empty commitment since it is 1 if the cell is filled and 0 otherwise.
s do not appear in the same row, continue the protocol. Otherwise, the verifier rejects. The following is an example of the result.
and 4
s. Since we have 18 free cards (3 pairs of
) in the previous phase, we additionally need 3
s. Note that after executing this phase, we have \(6k^2 (+ \epsilon )\) additional free cards since all \(E^{\heartsuit }_{6}(A_{\alpha })\) are opened. The number of shuffles used in the above procedure is 11 if \(\alpha \) has four neighborhood cells, 9 if \(\alpha \) has three neighborhood cells, and 7 if \(\alpha \) has two neighborhood cells. Thus the total number of shuffles in this phase is \(11(k-2)^2 + 36(k-2) + 28 = 11k(k - 8)\) because the number of cells having four neighbors, three neighbors, and two neighbors is \((k-2)^2\), \(4(k-2)\), and 4, respectively.
where \(B:= B_{\beta } + B_{\gamma } + B_{\delta } + B_{\epsilon } \in \{0,1,2,3,4\}\).
Note that if \(A_{\alpha } \not \in \{0,5\}\) and \(B \ge 1\), the three cards on \((p_0, p_5, q_0)\) are
.
We refer to the resultant sequence of 8 cards as S.
We refer to the resultant sequence of 8 cards as \(S_{\textsf{dummy}}\).
. If there is a pair of
, the protocol continues. Otherwise, the verifier rejects. The following is an example of the result.
This is the new propagation commitment of \(\alpha \).
s do not appear in the same row and the protocol continues to the next phase.
or some integer encoding has two or more
s), they will be detected in the copy protocol. So we can assume that all integer encodings and commitments are valid and they are \((A_{\alpha }, B_{\alpha })_{\alpha \in [k]\times [k]}\).
. Since \(\overline{A}_{\alpha }\ne \bot \) implies \(B_{\alpha } = 1\), in Step (10), the real sequence S will be opened. Since S contains at most one
, the verifier rejects the proof.
s appear in the same column. Therefore the verifier rejects the proof.
