Pascal Lafourcade

Daiki -4459-511x]

Miyahara

Takaaki Mizuki

Sasaki

Hideaki Sone

A Physical ZKP for Slitherlink: How to Perform Physical Topology-Preserving Computation

Keywords: Physical Zero-Knowledge Proof, Slitherlink, Physical Topology Preserving Computation

We propose a new technique to construct physical Zero-Knowledge Proof (ZKP) protocols for games that require a single loop draw feature. This feature appears in Slitherlink, a puzzle by Nikoli. Our approach is based on the observation that a loop has only one hole and this property remains stable by some simple transformations. Using this trick, we can transform a simple big loop, visible to anyone, into the solution loop by using transformations that do not disclose any information about the solution. As a proof of concept, we apply this technique to construct the first physical ZKP protocol for Slitherlink.

Introduction

Zero-Knowledge Proof (ZKP) systems are powerful cryptographic tools that were introduced by Goldwasser, Micali, and Rackoff in [START_REF] Goldwasser | The knowledge complexity of interactive proof-systems[END_REF]. It was then shown that for any NP-complete problem, there exists an interactive ZKP protocol [START_REF] Goldreich | How to construct constant-round zero-knowledge proof systems for NP[END_REF]. Later, one of the first physical ZKP protocols was introduced by Naor et al. in [START_REF] Gradwohl | Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles[END_REF] for a popular puzzle, Sudoku. In the mentioned article, a prover wants to prove to a verifier that he/she knows the solution of a Sudoku puzzle instance using only physical objects; to this end, in that paper the authors used only cards. Recently in [START_REF] Sasaki | Card-based zero-knowledge proof for Sudoku[END_REF], better ZKP protocols have been proposed in terms of numbers of cards used and complexity. They used envelopes and physical tricks to improve the original protocol.

Nikoli 5 is a Japanese company famous for designing puzzles. The list of puzzles created by Nikoli contains more than 40 different kinds of puzzles including Sudoku. In this paper, we focus on Slitherlink that was introduced in 1989 in issue the 26th of Nikoli's Puzzle Times. It is also known as Loop-the-Loop. It is explained on Nikoli's web site as follows: "Getting the loop right is absorbing and addictive. Watch out not to get lost in Slitherlink. It's amazing to see how endless patterns can be made using only four numbers (0, 1, 2 and 3)". Slitherlink was proven to be NP-complete in [START_REF] Yato | Complexity and completeness of finding another solution and its application to puzzles[END_REF] and other variants in [START_REF] Kölker | Selected Slither Link variants are NP-complete[END_REF]. It means that applying the technique of [START_REF] Goldreich | How to construct constant-round zero-knowledge proof systems for NP[END_REF] to construct a ZKP is possible.

Our aim is to propose a physical ZKP protocol for this game. Slitherlink is not like other Nikoli's games since it requires to draw a single loop to solve the puzzle. This feature of the game is a challenge that was not present in the previous physical ZKPs for Nikoli's puzzles [4-6, 8, 11, 21].

Contributions:

We introduce a new technique to construct a ZKP protocol for a puzzle where constructing a single loop is one of the requirements of the solution. The difficulty is to avoid leaking any information regarding the solution to the verifier. For this, we use a topological point of view; more precisely, we use the notion of homology that defines and categorizes holes in a manifold. The main idea is that after any continuous transformations, the number of holes always remains the same. Using this simple idea, we construct transformations that preserve the number of loops in the solution. First, the verifier checks that the initial configuration has only a single big loop. Then, by transforming in several steps this trivial big loop into the solution, the prover convinces step after step that the solution has only one loop at the end by proving that the transformation does not break the loop or introduce an extra hole. This construction is applied to Slitherlink in this article but it can be used for any other puzzles that require such type of features in their rules.

Related works:

Since Naor et al. [START_REF] Gradwohl | Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles[END_REF] introduced the first physical ZKP protocol for the Sudoku, physical ZKPs for other puzzles (proven to be NP-complete) have been proposed, e.g., Nonogram [START_REF] Chien | Cryptographic and physical zero-knowledge proof: From sudoku to nonogram[END_REF], Akari, Takuzu, Kakuro, Kenken [START_REF] Bultel | Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen[END_REF], Makaro [START_REF] Bultel | Physical zero-knowledge proof for makaro[END_REF], and Norinori [START_REF] Dumas | Interactive physical zero-knowledge proof for Norinori[END_REF]. All these ZKPs deal with numbers. For example, in Sudoku, a prover has to show the verifier that each column, row, and subgrid contain all the numbers from one to nine.

Physical objects enable us to perform secure computation without relying on computers: such examples are a PEZ dispenser [START_REF] Balogh | Private computation using a PEZ dispenser[END_REF], tamper-evident seals [START_REF] Moran | Basing cryptographic protocols on tamper-evident seals[END_REF], and a deck of cards [START_REF] Den Boer | More efficient match-making and satisfiability: The Five Card Trick[END_REF]. Among them, secure computation with a deck of cards, called card-based cryptography, has been widely studied. Especially, for secure computation of logical AND function, the number of required cards have been reduced in [START_REF] Crépeau | Discreet solitary games[END_REF][START_REF] Koch | Card-based cryptographic protocols using a minimal number of cards[END_REF][START_REF] Mizuki | Six-card secure AND and four-card secure XOR[END_REF][START_REF] Niemi | Secure multiparty computations without computers[END_REF][START_REF] Stiglic | Computations with a deck of cards[END_REF], and necessary and sufficient numbers of cards have been provided in [START_REF] Kastner | The minimum number of cards in practical card-based protocols[END_REF][START_REF] Koch | Card-based cryptographic protocols using a minimal number of cards[END_REF].

However, these works do not deal with proving the topological feature of having a single loop in the solution.

Outline: In Section 2, we define the rules of Slitherlink, the formal definition of ZKP, and the notation used in this paper. In Section 3, we describe our ZKP protocol for Slitherlink. In Section 4, we show the security proofs of ZKP.

Preliminaries

Rules of Slitherlink

Slitherlink is one of the most famous pencil puzzles published in the puzzle magazine Nikoli. The puzzle instance consists of lattice-like dots where some squares contain numbers between 0 and 3. The goal of the puzzle is to draw lines that satisfy the following rules [1]:

1. Connect vertical/horizontal adjacent dots with lines to make a single loop. 2. Each number indicates the number of lines that should surround its square, while empty squares may be surrounded with any number of lines. 3. The loop never crosses itself and never branches off. Figure 1 shows an example of a Slitherlink puzzle and its solution; one can easily verify that all conditions are satisfied.

Zero-Knowledge Proof

A Zero-Knowledge Proof (ZKP) is a secure two-party protocol between a prover P and a verifier V . Formally, they both have an instance of I of a problem and only P knows the solution w. The prover P wants to convince V that he/she knows w without revealing any information about w. Such a proof is called a zero-knowledge proof, if it satisfies the following three properties. Completeness. If P knows w, then P can convince V . Extractability. If P does not know w, then P cannot convince V . Zero-Knowledge. V cannot obtain any information about w. Assuming a probabilistic polynomial time algorithm M (I) not containing w if outputs of the protocol and M (I) follow the same probability distribution, the zeroknowledge property is satisfied.

Notations

We use the following physical cards: ♣ ♣ • • • ♡ ♡ ; the black ♣ and red ♡ cards are called binary cards. The backs of all cards are identical and denoted by ? . In our construction, binary cards are used to encode the existence of a line while number cards are used for rearranging the positions of cards, as shown later.

Encoding: We encode Boolean values with two binary cards as follows: ♣ ♡ = 0 and ♡ ♣ = 1. Two face-down cards encoding 0 and 1 are called a 0-commitment and a 1-commitment, which are denoted by 0 and 1 , respectively.

In our protocol, a 0-commitment placed on a gap between two adjacent dots means that there is no line on the gap, and a 1-commitment means that there is a line on the gap. With this encoding, we can represent a loop that is made of several lines. Note that given an x-commitment for x ∈ {0, 1}, swapping the two cards consisting the commitment results in an x-commitment; thus, negation can be easily done.

Shuffle: Given a sequence of m face-down cards (c 1 , c 2 , . . . , c m ), a shuffle results in a sequence c r -1 (1) , c r -1 (2) , . . . , c r -1 (m) , where r ∈ S m is a uniformly distributed random permutation and S m denotes the symmetric group of degree m.

Pile-Shifting Shuffle: The goal of this operation, which is also called Pile-Shifting Scramble [START_REF] Nishimura | Pile-shifting scramble for cardbased protocols[END_REF], is to cyclically shuffle piles of cards. That is, given m piles, each of which consists of the same number of face-down cards, denoted by (pile 1 , pile 2 , . . . , pile m ), applying a Pile-Shifting Shuffle results in (pile s+1 , pile s+2 , . . . , pile s+m ):

? pile1 ? pile2 • • • ? pilem → ? piles+1 ? piles+2 • • • ? piles+m ,
where s is uniformly and randomly chosen from Z/mZ. To implement Pile-Shifting Shuffle, we use physical cases that can store a pile of cards, such as boxes and envelopes; a player (or players) cyclically shuffle them by hand until nobody traces the offset. It can be done by physical object as the one created for the physical ZKP for Sudoku in [START_REF] Sasaki | Card-based zero-knowledge proof for Sudoku[END_REF].

Pile-Scramble Shuffle: Pile-Scramble Shuffle is a well-known shuffle operation which was first used in [START_REF] Ishikawa | Efficient card-based protocols for generating a hidden random permutation without fixed points[END_REF]. As mentioned above, let us denote m piles by (pile 1 , pile 2 , . . . , pile m ). For such a sequence of piles, applying a Pile-Scramble Shuffle results in (pile r -1 (1) , pile r -1 (2) , . . . , pile r -1 (m) ), where r ∈ S m is a uniformly distributed random permutation. A Pile-Scramble Shuffle uses similar material as Pile-Shifting Shuffle but its operation is similar to Shuffle.

Chosen Pile Cut: It was proposed in [START_REF] Koch | Foundations for actively secure card-based cryptography[END_REF]. Chosen Pile Cut enables a prover to choose a pile pile i from m piles (pile 1 , pile 2 , . . . , pile m ) without revealing i to a verifier. The Chosen Pile Cut proceeds as follows, given m piles along with m additional cards:

1. The prover P holds m -1 ♣ s and one ♡ . Then, P places m cards with their faces down below the piles such that only the i-th card is ♡ : where s is generated uniformly at random from Z/mZ by this shuffle action. 3. Reveal all the cards in the second row. Then, one ♡ appears, and the pile above the revealed ♡ is pile i , and hence, we can obtain the desired pile i .

Owing to the Pile-Shifting Shuffle in Step 2, revealing cards leaks no information about i and thus, Chosen Pile Cut leaks no information about i, the index of the chosen pile.

Zero-Knowledge Proof for Slitherlink

In this section, we construct our physical zero-knowledge proof protocol for Slitherlink. The outline of our protocol is as follows.

Input Phase: The verifier V puts a 1-commitment (i.e., two face-down cards encoding 1) on every gap on the boundary of the puzzle board and 0commitments on all the remaining gaps. In other words, V creates a single big loop whose size is the same as the board. Topology-Preserving Computation Phase: The prover P transforms the shape of the loop according to the solution. After this phase, V is convinced that the placement of 1-commitments satisfies Rules 1 and 3 of Slitherlink without the disclosure of any information about the shape. Verification Phase: V verifies that the placement of 1-commitments satisfies Rule 2 of Slitherlink.

We introduce some subprotocols in Section 3.1 before presenting our protocol in Section 3.2.

Subprotocols

Chosen Pile Protocol: This is an extended version of the Chosen Pile Cut [START_REF] Koch | Foundations for actively secure card-based cryptography[END_REF] explained in Section 2. Given m piles with 2m additional cards, this protocol enables P to choose the i-th pile and regenerate the original sequence of m piles.

1. Using m -1 ♣ s and one ♡ , the prover P places m cards with their faces down below the given piles such that only the i-th card is ♡ : where s ′ is generated uniformly at random from Z/mZ. 5. Reveal all the cards in the second row. Then, one ♡ appears, and the pile above the revealed ♡ is pile 1 . Therefore, by shifting the sequence of piles, we can obtain a sequence of piles whose order is the same as the original one without revealing any information about the order of input sequence. Verifying-Degree Protocol: This protocol can verify that the "degree" of a target vertex (dot) is not four. Here, degree means the number of 1-commitments placed around a target vertex. Thus, the prover P wants to prove that there is at least one 0-commitment around the target vertex (when only P knows what the four commitments around the target are).

? pile1 ? pile2 . . . ? pilei
The Verifying-Degree Protocol proceeds as follows.

1. Given four commitments that are placed around the target vertex, these can be regarded as a sequence of 4 commitments:

• ? ?

• ? ?

• ? ? • ? ?

• → ? ? ? ?

2. By using Chosen Pile Protocol, P chooses one of the 0-commitments. Open the chosen pile to show that it is 0. Now, V is convinced that the degree of the target vertex is not four. Then, V turns over all the opened cards.

Because only a 0-commitment is always opened, no information about the four commitments is disclosed. 3. V performs the remaining steps in the Chosen Pile Protocol. Then, all the cards are placed back to their original positions.

Topology-Preserving Computation:

This protocol changes a given loop into another loop by one of the three transformations given in Figure 2. Each transformation changes the lines surrounding a square, represented by dash line in Figure 2. Remember that a line is expressed by a commitment (i.e., two face-down binary cards) in our protocol. Therefore, for example, a (2,2)-transformation means

• 1 • 1 0 • 0 • → • 0 • 0 1 • 1 •
This can be implemented by swapping two cards of each commitment. (Remember that swapping the two cards performs negation of a commitment.) A (3,1)transformation and a (1,3)-transformation can also be implemented by swapping two cards of each commitment:

• 1 • 0 1 • 1 • → • 0 • 1 0 • 0 • • 0 • 0 0 • 1 • → • 1 • 1 1 • 0 •
Now, P wants to apply one of the three transformations while the applied transformation is hidden from V . Furthermore, P needs to show that the commitments around a target square are "transformable." Note that the three transformations are applicable to four commitments around a square if and only if there exists a 0-commitment facing a 1-commitment.

Topology-Preserving Computation proceeds as follows.

1. Pick four commitments around a target square:

? ? ? ?

2. P chooses a 0-commitment facing a 1-commitment using Chosen Pile Protocol. 3. V reveals the chosen commitment and the commitment that is two piles away from it: ↓ ↓ ? ? ? ?

♡ ♣ ♣ ♣ ? ? ? ?

Then, V checks that the two commitments are a 0-commitment and a 1commitment to be convinced that any transformation can be applied. 4. After turning over all the opened cards, V performs the remaining steps in the Chosen Pile Protocol to place all the cards back to their original positions. 5. Swap the two cards of each of the four commitments. (Remember that this results in negating all the four commitments, and hence, a transformation is applied.) 6. V applies a Verifying-Degree Protocol to each of the four dots of the target square. Then, V is convinced that no dots of degree four have been obtained as the result of transformation. This guarantees that the loop was not split and thus, it remains a single loop.

Our Construction

As mentioned at the beginning of this section, the main idea behind our protocol is that the verifier V first creates a big loop and then the prover P transforms the loop into the solution loop one by one. Let us consider a puzzle instance shown in Figure 3 as an example. Our protocol transforms the loop as illustrated in Figure 4.

We are now ready to present the full description of our zero-knowledge proof protocol for Slitherlink.

Input Phase:

The verifier V puts a 1-commitment on every gap on the boundary of the puzzle board and 0-commitments on all the other gaps. This placement corresponds to the single loop with the same size as the board. The following is an example of the placement of (2 × 2)-square puzzle board:

• 1 • 1 • 1 0 1 • 0 • 0 • 1 0 1 • 1 • 1 •
P will apply Topology-Preserving Computation to these commitments to transform the shape of the loop into the solution. Here, P needs to hide the target square. Therefore, we make a sequence of piles from the placed cards, pick the four target commitments using the Chosen Pile Protocol, and apply Topology-Preserving Computation. To properly pick the four commitments, a sequence of piles is formed, as follows.

We first expand the puzzle board by adding dots around the original board. (For explanation, the expanded dots are denoted by ⊙.)

⊙ ⊙ ⊙ ⊙ ⊙ ⊙ • 1 • 1 • ⊙ 1 0 1 ⊙ • 0 • 0 • ⊙ 1 0 1 ⊙ • 1 • 1 • ⊙ ⊙ ⊙ ⊙ ⊙ ⊙
Note that the expanded area is unrelated to the actual puzzle board. V puts dummy commitments on the gaps at the expanded area other than the right and the bottom ends. Each dummy commitment consists of two black cards ♣ ♣ to prevent the loop from spreading over the expanded area. We denote the dummy commitment by ♣ .

⊙ ♣ ⊙ ♣ ⊙ ♣ ⊙ ♣ ⊙ ♣ ♣ ♣ ♣ ⊙ ♣ • 1 • 1 • ♣ ⊙ ♣ 1 0 1 ⊙ ♣ • 0 • 0 • ♣ ⊙ ♣ 1 0 1 ⊙ ♣ • 1 • 1 • ♣ ⊙ ♣ ♣ ♣ ♣ ⊙ ⊙ ⊙ ⊙ ⊙
Next, V makes a sequence of 4-card piles as follows. For each square, V first makes a pile from the commitments placed on the left and the top (the commitment on the gap between each vertically consecutive dots is placed on the commitment on its upper right.)

⊙ ♣ ♣ ⊙ ♣ ♣ ⊙ ♣ ♣ ⊙ ♣ ♣ ⊙ ⊙ ♣ ♣ • 1 1 • 0 1 • 1 ♣ ⊙ ⊙ ♣ ♣ • 1 0 • 0 0 • 1 ♣ ⊙ ⊙ ♣ ♣ • ♣ 1 • ♣ 1 • ♣ ♣ ⊙ ⊙ ⊙ ⊙ ⊙ ⊙
Then, pick 4-card piles from top to bottom:

♣ ♣ ♣ ♣ ♣ ♣ . . . ♣ 1 ♣ 1 ♣ ♣
to make a sequence of piles:

? ? ? . . . ? ? ?

Topology-preserving computation phase: In this phase, P applies transformations (explained in Section 3.1) to stepwise change the big loop to the solution loop. Let n be the size of the puzzle instance, namely the number of squares on the puzzle board. Then, note that P can make the solution loop by at most n transformations.

1. P applies the following exactly n-1 times such that either the resulting loop is already the solution, or one more transformation will end up the solution.

(This is possible because successive two transformations (of the same) to the same square keep the loop unchanged.) (a) P applies the Chosen Pile Protocol to the sequence of 4-card piles: P picks a 4-card pile composed of left and top edges of the square that P wants to transform. The other edges can be picked by counting the distance from the chosen pile6 . (b) P applies the Topology-Preserving Computation to the four picked commitments. (c) V performs the remaining steps in the Chosen Pile Protocol to place the cards back to their original positions. 2. P applies one more transformation or does not change the solution loop so that V does not learn which action occurs, as follows.

(a) Similarly to Step 1 (a) above, P picks four commitments around the target square. (b) By using the method explained in Topology-Preserving Computation, V confirms that any transformation is applicable. (c) V arranges the four commitments vertically and makes a pile from each column: ? ? ? ? ? ? ? ?

→ ? ?

Note that swapping two piles results in inverted value of each commitment. Thus, it is equivalent to applying a transformation. (d) Using the Chosen Pile Cut, if P wants to transform the target square, then P chooses the right pile; otherwise, the left pile is chosen. (e) Rearrange the cards vertically such that the chosen pile is placed at left:

?

Chosen pile ? → ? ? ? ? ? ? ? ?

(f) V makes four commitments from each row, performs the remaining steps in the Chosen Pile Protocol, and places each commitment back to their original position. 3. Finally, all cards are placed on the puzzle board and the cards at the dummy area are removed.

Verification phase: V is now convinced that the placement of 1-commitments is a single loop (Rule 1) and it never branches off (Rule 3). Therefore, V only needs to verify that the placement satisfies Rule 2 of Slitherlink. Now, V verifies that the number on each square is equal to the number of lines surrounding it. The verification proceeds as follows, where we virtually assume that the board is colored like a checkered pattern so that all squares in the first row are alternation of blue and yellow, those in the second row are alternation of yellow and blue, and so on.

1. V picks all left cards (if the square is virtually blue) or all right cards (if the square is yellow) of four commitments around a square on which a number is written: ? ? ? ? .

2. P shuffles the four cards.

3. V reveals the four cards.

-If V picked all the left cards of four commitments in Step 1, V checks that the number of red cards ♡ is equal to the number on the square. -If V picked all the right cards of four commitments in Step 1, V checks that the number of black cards ♣ is equal to the number on the square. 4. Apply Steps 1 to 3 to all other numbered squares. (Note that a commitment is related to at most one blue numbered square and one yellow numbered square.)

Our protocol uses 6(p + 2)(q + 2) + 8 cards in total, where we have a p × q board.

Security Proofs for Our Construction

In this section, we show that our construction satisfies the completeness, extractability, and zero-knowledge properties.

Completeness:

In the input phase, V is convinced that 1-commitments are placed in a single loop because V does the operations by himself/herself, and hence, V is convinced that the placement satisfies Rules 1 and 3 of Slitherlink. As explained in Section 3.1, the transformations are applied to only applicable squares. Thus, every transformation is performed while preserving Rules 1 and 3. By verifying that the placement satisfies Rule 2 in verification phase, V is convinced that P knows the solution. Therefore, if P has a solution for the puzzle then P can always convince V .

Remember that P uses only (3,1), (1,3), and (2,2)-transformations in the Topology-Preserving Computation to transform a single loop into the shape of the solution. We now prove that this is possible in Theorem 1.

Theorem 1. Let n be the number of squares in the puzzle instance (namely, the big loop), and let k be the number of squares inside its solution loop. By applying a transformation to the loop exactly n -k times, the big loop can be transformed into the solution loop.

To prove Theorem 1, we first show Lemmas 1 and 2.

Lemma 1. The resulting placement of 1-commitments after the Topology-Preserving

Computation always represents a single loop.

Proof. Remember Steps 2 and 6 in the Topology-Preserving Computation: Due to Step 2, the target square is guaranteed to be none of the following two ones (up to rotations).

That is, one of (2,2), (3,1), and (1,3) transformations is always applied to the target square.

Due to the execution of the Verifying-Degree Protocol in Step 6, the following two transformations that make a loop split cannot occur.

Therefore, it remains a single loop.

⊓ ⊔ Lemma 2. For any single loop, there is always a (3,1), (1,3), or (2,2)-transformation that increases the number of squares inside the loop by exactly one.

Proof. Consider a single loop; let ℓ be the number of squares inside the loop. To prove this lemma, we show that there always exists a square on the board such that a (3,1), (1,3), or (2,2)-transformation can be applied to the square such that ℓ increases. Note that the loop remains single after the application of the transformation by Lemma 1. If ℓ ≤ 2, a (1,3) transformation increases the number of squares by one. Thus, one may assume that ℓ ≥ 3. Then, any square outside the loop can be classified in one of the following five types (up to rotations):

If none of (a), (b), and (c) exists, all squares outside the loop are either (d) or (e), and hence, it would not be a sigle loop. Therefore, at least one square of type (a), (b), or (c) must exist outside the loop.

Applying a (3,1), (1,3), or (2,2)-transformation to such an external square results in increasing ℓ by one.

⊓ ⊔ By these lemmas, Theorem 1 can be proved.

Proof of Theorem 1. By Lemmas 1 and 2, we can always increase the number of squares inside the solution loop by a transformation. Therefore, we can repeat the transformation so that the solution loop becomes the big loop. This means that, conversely, the big loop can be transformed into the solution loop by applying (3,1), (1,3), or (2,2)-transformation exactly n -k times.

⊓ ⊔

Extractability: Only the person who knows the solution can transform the loop so that the shape satisfies Rule 2. Therefore, V can detect any illegal prover in Verification Phase. Thus, if the prover does not know the solution for a puzzle, then V will be never convinced, irrespective of P 's behavior. More formally, to prove the extractability, we are required to show that any shape that does not satisfy Rule 1, 2, or 3 is always rejected during the protocol. Theorem 2. If the prover does not know the solution for the Slitherlink puzzle, then the verifier always rejects regardless of the prover's behavior.

To prove Theorem 2, we show that the resulting loop after the Topology-Preserving Computation always satisfies Rules 1 and 3 (as in Lemma 1) and any single loop that does not satisfy Rule 2 is always rejected in Verification Phase (as in Lemma 3). Therefore, any single loop except for the solution is always rejected. Lemma 3. Any (single) loop that does not satisfy Rule 2 is always rejected in Verification Phase.

Proof. Consider any (single) loop that does not satisfy Rule 2, i.e., there are four commitments surrounding a numbered square such that the number of 1-commitments among them is not equal to the number. Due to Step 3 in Verification Phase, all the left (or right) cards of four commitments are turned over (after shuffling them), and hence, the number of 1-commitments is revealed. This means that the verifier can always reject any (single) loop that does not satisfy Rule 2.

⊓ ⊔ Proof of Theorem 2. By Lemma 1, the resulting loop after the Topology-Preserving Computation is always single, i.e., it satisfies Rules 1 and 3. By Lemma 3, if it does not satisfy Rule 2, the verifier always rejects it in Verification Phase. That is, any loop except for the solution cannot go through Verification Phase.

⊓ ⊔

Zero-Knowledge: In our construction, all the opened cards have been shuffled before being opened. Therefore, all distributions of opened cards can be simulated by a simulator M (I) who does not know the solution. For example, at Step 3 in Verification Phase, the Pile-Scramble Shuffle have been applied to opened commitments; thus, this is indistinguishable from a simulation putting randomly 1-commitments such that the number of them is equal to the number of the square.

Conclusion

In this study, we introduced a new technique that can transform a single loop encoded with physical objects into a new geometrical figure while preserving the single loop. Furthermore, by using this secure computation, we constructed the first physical zero-knowledge proof protocol for Slitherlink. As we mentioned in Section 1, our construction can be used for other puzzles that require a feature of drawing a single loop. For example, Masyu published by Nikoli has the same rule as Slitherlink, i.e., we should draw a single loop that never crosses itself and never branches off. Therefore, we can easily construct a physical ZKP protocol for Masyu by executing Topology-Preserving Computation (and then verifying the other rules).

Because physical ZKP protocols should be executed by humans' hands, we usually consider the size of puzzle instance to be bounded by a constant. This differs from conventional ZKP protocols (relying on computers). Note that people enjoying a pencil puzzle will not use a computer to solve it, and hence, physical ZKP protocols are useful and effective for ordinally people.

Fig. 1 .

 1 Fig. 1. Example of a standard Slitherlink challenge, and its solution.

♣ 2 .

 2 Regarding the cards in the same row as a pile, apply Pile-Shifting Shuffle to the piles (denoted by ⟨ • | . . . |• ⟩):

Fig. 2 .

 2 Fig. 2. Three transformations.

Fig. 3 .

 3 Fig. 3. Small example of Slitherlink challenge, and its solution.

Fig. 4 .

 4 Fig. 4. Transformation process.

  Remove the revealed cards, i.e., the cards in the second row. Then, apply a Pile-Shifting Shuffle:

					?	?	. . . ?
				-1	pilei	pilei+1
	?	?		?		?		?	. . .	?
	piles+1	piles+2	. . .	piles+m	→	pile s ′ +s+1	pile s ′ +s+2	pile s ′ +s+m
	?	?		?		?		?	. . .	?	,

pilem ? ♣ ? ♣ . . . ? ♣ ? ♡ ? ♣ . . . ? ♣ We further put m cards below the cards such that only the first card is ♡ : ? pile1 ? pile2 . . . ? pilei-1 ? pilei ? pilei+1 . . . ? pilem ? ♣ ? ♣ . . . ? ♣ ? ♡ ? ♣ . . . ? ♣ ? ♡ ? ♣ . . . ? ♣ ? ♣ ? ♣ . . . ? ♣ 2. Considering the cards in the same row as a pile, apply a Pile-Shifting Shuffle to the sequence of piles: ? pile1 ? ? ? pile2 ? ? . . . ? pilem ? ? → ? piles+1 ? piles+2 . . . ? piles+m ? ? . . . ? ? ? . . . ? ,

where s is generated uniformly at random from Z/mZ. 3. Reveal all the cards in the second row. Then, one ♡ appears, and the pile above the revealed ♡ is the i-th pile (and hence, P can obtain pile i ). When this protocol is invoked, certain operations are applied to the chosen pile. Then, the chosen pile is placed back to the i-th position in the sequence. 4.

http://www.nikoli.com/

In the above example, the bottom edge corresponds to the pile which is 4 piles away from the chosen pile. Note that the distance between any two piles never changes because only Pile-Shifting Shuffle is applied.

Acknowledgement

We thank the anonymous referees, whose comments have helped us to improve the presentation of the paper. This work was supported by JSPS KAKENHI Grant Number JP17K00001 and JP19J21153.


Ismail Mansour

Gérard Chalhoub

Pascal Lafourcade

Secure Multihop Key Establishment Protocols for Wireless Sensor Networks

Keywords: Authentication, key establishment, Wireless Sensor Network, Security, Multihop, Formal Verification

Designing secure communication protocols is not an easy task. Cryptography is often necessary but does not always guarantee the security of protocols as several famous examples attest in the literature. Moreover, in the context of Wireless Sensor Networks (WSNs) the design is even more difficult due to the limited resources of sensor nodes that add extra constraints to take into account. During the life time of a secure WSN, one of the first crucial steps is the key establishment between two nodes. In this paper we propose four secure multihop key establishment protocols based on elliptic curve cryptography (ECC). For each protocol, we make a formal security proof using the automatic tool Scyther. Then, in order to evaluate their performances, we implemented them on testbeds using TelosB motes and TinyOS. Results allow us to estimate the overhead of our key establishment methods.

Introduction

Due to the technological advances, Wireless Sensor Networks (WSNs) are more and more used in diverse applications. In the first age of WSNs, the main concern was to efficiently transmit the data to the destination using wireless communications. Only few applications, like military WSN examples, required a high level of security [START_REF] Hussain | Wsn research activities for military application[END_REF]. In this context, it is important to design secure efficient communication mechanisms between nodes of the network, using cryptography. Moreover, with the expansion of the Internet of Things (IoT) more and more devices will be interconnected and monitoring critical human activities. For instance nowadays most of the smart phones have a GPS, a camera, and several sensors. In a close future our environment will be equipped with several sensors in order to collect data to inform the user. In this context the knowledge of this data can leak private information, one solution to avoid this is to use cryptography in order to preserve privacy of the users. One of the first steps in this situation is to design secure multihop key establishment protocols. This is the main motivation of this paper.

Contributions:

Our goal is to design several secure key establishment protocols for WSNs and to evaluate their performances on real nodes. Hence our contributions can be split in three points:

-Design of key establishment protocols based on ECC.

-Formal security analysis of the protocols.

-Evaluation on TelosB testbeds of the execution time of each solution. All our protocols are based on Elliptic Curve Cryptography (ECC) with a key of 160 bits. We propose a first protocol called M KES. It allows nodes that already share a key with the sink to establish a new secret key. The idea is to use the sink as a kind of third trusted party to establish a new key. In addition, we propose an improvement of this protocol called M KESlight. In this version, the sink performs costly computation instead of the nodes, since in many situations the sink has no limited battery and more computation power than nodes of the WSN. We also give two other protocols that establish a secret key between two nodes without passing by the sink. The first one is called M KENK , it uses only the network key shared between all the authenticated nodes in the network. This authentication phase can be done for instance using one of the protocols proposed in [START_REF] Mansour | Multihop node authentication mechanisms for wireless sensor networks[END_REF]. The second protocol is called M KEK, also it does not use the sink, but it uses the symmetric keys shared between neighbor nodes. In order to guarantee the authentication of nodes involved, this protocol only requires two flows of messages instead of three as it is the case for the protocol M KENK . In order to prove the security of all these protocols, we used Scyther an automatic cryptographic protocol verification tool developed by Cas Cremers. It is easy to propose a flawed protocol, this tool helps to verify the correctness of the security protocol and make sure that it resists against several kinds of attacks. Each of our solutions uses a different approach to securely establish a new secret key, they vary according to the number of cryptographic operations involved and the trust level that we need to have in the network nodes. Our last contribution is the implementation on real nodes of all our protocols. Our aim is to measure the execution time of each protocol, but also to compare them in order to be able to judge which one is the most suitable.

Related Work:

Many contributions have been made in the key establishment and symmetric key distribution in WSNs. Some of them are based on a probabilistic predistribution that guarantees that any two nodes in the network are able to share a key with a certain probability, and others are deterministic but cause more storage overhead [START_REF] Bala | Classification of symmetric key management schemes for wireless sensor networks[END_REF]. One of the most known symmetric key systems that were proposed for wireless sensor networks is SPINS (Security Protocols for Sensor Networks) [START_REF] Perrig | SPINS: Security protocols for sensor networks[END_REF] which uses a simplified version of TESLA (Timed, Efficient, Streaming, Loss-tolerant Authentication) protocol [START_REF] Perrig | Efficient authentication and signing of multicast streams over lossy channels[END_REF]. In SPINS, the base station plays an essential role in the key establishment process. It is a lightweight protocol but suffers from scalability and high dependency on the base station. Authors in [START_REF] Munivel | Efficient public key infrastructure implementation in wireless sensor networks[END_REF] proposed a multi-hop key establishment between nodes called Micro-PKI. Their method is based on the pre-distribution of the public key of the base station. Using this public key, every node is able to create a secret key with any other node of the network. The authentication process in this proposal is only dependent on the public key of the base station, if a node has this key, it is considered authenticated. This makes the procurement of this public key very critical on which depends the whole security architecture. In [START_REF] Chan | Pike: Peer intermediaries for key establishment in sensor networks[END_REF], authors proposed PIKE, peer intermediaries for key establishment, one of the most famous key establishment protocols that is not dependent on a central trusted node. According to PIKE, keys are pre-deployed in the nodes in such a way to guarantee that any two nodes in the network have at least one node in common with which each one of the two nodes has a secret key with it. Therefor, these two nodes are able to establish a secret key by using the trusted channel established with the common node. PIKE suffers from high memory storage to make sure that nodes are able to find at least one node in common to establish a new key. CARPY and CARPY+ were proposed in [START_REF] Yu | A simple non-interactive pairwise key establishment scheme in sensor networks[END_REF]. They are based on the symmetric keys of Blom [START_REF] Blom | An optimal class of symmetric key generation systems[END_REF] with a perturbation function that makes more difficult for an attacker to guess the pairwise keys. In their paper they discuss the five criteria that were proposed in [START_REF] Zhang | A random perturbationbased scheme for pairwise key establishment in sensor networks[END_REF] and claim that CARPY+ satisfies all of them. These criteria are: Resilience to the Adversary's Intervention during the key establishment phase, Directed and Guaranteed Key Establishment for any couple of nodes in the network, Resilience to Network Configurations nodes should be able to establish keys in any kind of network topology, Efficiency of the key establishment process in terms of memory storage, communication overhead and complexity, Resilience to Dynamic Node Deployment which allows nodes to be added at any time to the network and enabling them to establish keys. The main weakness of this scheme is the lack of a rekeying process. The preshared matrices will only help to create one pairwise key for every couple of nodes. Table 1 summarizes a comparison between the related work schemes and our proposition. The comparison is based on some repudiated criterias in WSN area. As the table shows, Yu et al. scheme [START_REF] Yu | A simple non-interactive pairwise key establishment scheme in sensor networks[END_REF] is the closest one to our schemes. Nevertheless, the authors use TelosB motes to evaluate energy consumption of basic operations used in their schemes and they provide a large scale simulation for thousands of nodes based on these measurements.

Proposed scheme

Predistribution Trusted Party

Cryptographic technique Simulation

Implementation Verification Perrig et al., 2000 [START_REF] Perrig | Efficient authentication and signing of multicast streams over lossy channels[END_REF], 2002 [START_REF] Perrig | SPINS: Security protocols for sensor networks[END_REF] yes In this paper, we did not compare our time execution results with other protocols from the state of the art because implementations are hardware and system dependent. In addition, they can be optimized for certain platforms which makes the comparison unfair using different platforms and cryptographic primitives. Finally the main difference with other works is that we formally prove the security of all our protocols using the automatic verification tool Scyther [START_REF] Cremers | The Scyther Tool: Verification, falsification, and analysis of security protocols[END_REF].

Outline:

In the next section, we introduce the notations used and present four key establishment protocols. Then, in Section 3, we give the results of our implementation on TelosB motes. Finally, we conclude in the last section.

Multi-hop Key Establishment Protocols

In our evaluation testbed, we used public keys based on Elliptic Curve Cryptography (ECC), using parameters secp160r1 given by the Standards for Efficient Cryptography Group [START_REF] Research | Standards for efficient cryptography, sec 1: Elliptic curve cryptography[END_REF]. Our implementation of ECC on TelosB is based on TinyECC library [START_REF] Liu | Tinyecc: A configurable library for elliptic curve cryptography in wireless sensor networks[END_REF]. More precisely we used the Elliptic Curve Diffie-Hellman (ECDH) key agreement scheme [START_REF] Diffie | New directions in cryptography[END_REF]. For all symmetric encryption/decryption we use an optimized implementation of AES with a key of 128 bits proposed by [START_REF] Manica | WSN -secure comunications with AES algoritms[END_REF]. Note that we only use the public keys in order to establish symmetric keys without doing any asymmetric encryption or decryption operations. Indeed, it helps us establish a pairwise key without interaction between nodes thanks to the predistribution of public keys before the deployment. Before deployment, each node N knows the public key pk(S) of the sink S and also its own pair of private and public keys, denoted (pk(N ), sk(N )) respectively. Based on ECC, we have that pk(N ) = sk(N ) × G, where G is a generator point of the elliptic curve. Using this material, each node N can compute a shared key with the sink S using a variation of the Diffie-Hellman key exchange without interaction between the nodes, denoted KDH(N, S). These computations can be done by the sink and by all nodes before deployment in order to preserve their energy.

-The sink knows its own secret key sk(S) and the public key pk(N ) of a node N . The sink computes KDH(N, S) = sk(S) × pk(N ). -Node N multiplies his secret key sk(N ) by the public key of the sink pk(S) to get KDH (N, S). Both computations give the same shared key since:

KDH(N, S) = sk(N ) × pk(S) = sk(N ) × (sk(S) × G) = (sk(N ) × G) × sk(S) = pk(N ) × sk(S)

Notations

In what follows, we use the following notations to describe exchanged messages in our protocols:

-I: a new node that initiates the protocol, -R: a neighbour of node I, -S: the sink of the network (also called base station), -Ji: the i-th intermediate node between R and S, -nA: a nonce generated by node A, -pk(A): the public key of node A, -sk(A): the secret (private) key of node A, -K(I, S): the session key between I and S, -N K: the symmetric network key between all nodes of the network, -KDH(N, S): the shared symmetric key between N and S using the Diffie-Hellman key exchange without interaction described above, -{x} k : the encryption of message x with the symmetric or asymmetric key k. In all the figures that describe our protocol, we denote a direct communication by an arrow between two nodes, and a communication passing by several possible intermediate nodes by a dotted arrow. We also explicit above each exchanged message the size in Bytes.

Protocols with Intervention of the Sink

Our aim is to establish a shared key between any two authenticated nodes I and R of the network (not necessary in range). We propose two protocols, called M KES and M KESlight. Protocol M KES, depicted in Figure 1, uses the secure channels created between the sink and each node to communicate the public keys of I and R. Notice that in our context the sink knows all the public keys of all nodes and a node only knows its public key and the public of the sink. The initiator node I builds a request containing the identity of node R and a nonce nI . This request is encrypted with KDH(I, S) and sent to S. The sink S sends:

to I, the identity of R, a nonce nS, the public key of R encrypted with the shared symmetric key KDH(I, S), -to R, the identity of I, the same nonce nS, the nonce nI received from I and the public key of I encrypted with the shared symmetric key KDH(S, R).

Once these two messages received by I and R, the two nodes are able to compute KDH(I, R) as follows:

-Node I computes sk(I) × pk(R) = sk(I) × sk(R) × G = KDH(I, R). -Node R computes sk(R) × pk(I) = sk(R) × sk(I) × G = KDH(I, R).
To ensure mutual authentication of R and I, node R generates a nonce nR, then uses KDH(I, R) to encrypt its own identity, the two received nonces from S plus its nonce nR. This cipher is sent to I, without necessary passing by S. Finally, node I verifies that the received nonce from R is the same as the one sent by the sink. Then it confirms that it correctly received the message by sending to R its own identity and the two nonces nS and nR, encrypted with KDH(I, R). Notice that the computation of the new key KDH(I, R) can be done by the sink in order to save some computations on nodes R and I. This version called M KESlight is depicted in Figure 2.

Protocols without intervention of the Sink

In order to avoid exhausting nodes situated near the sink, we propose two protocols, called M KENK and M KEK , that do not need the intervention of the sink in the key establishment process. The protocol M KENK , depicted in Figure 3, uses the network key N K allowing the initiator node I and the responder R to exchange their public key. The initiator node I builds a request containing his own identity and a nonce nI . This request is encrypted with N K and sent to R. After decrypting this request, the responder R is able to extract pk(I) and compute KDH(I, R). In order to ensure mutual authentication of R and I, node R generates a nonce nR, then uses KDH(I, R) to encrypt the received nonce from I and its nonce nR. Then, node R builds the response message including this cipher and his own public key pk(R). The response message is encrypted using N K and sent to the initiator I. After decrypting the response message, node I extracts pk(R) and computes KDH(I, R). Using this key, I decrypts the two nonces nI and nR. After verifying the nonce nI , node I builds a reply message containing nR, encrypted with KDH(I, R). Finally, node R verifies that the received nonce nR from I is the same as the one it originally sent. No encryption/decryption operations on intermediate nodes.

We note that the use of N K to exchange public keys between nodes I and R can be useful when the initiator I is in the neighborhood of R. Indeed, node I sends directly its request to node R without the need of intermediate nodes to forward its request. Since the network key N K is known by all nodes before deployment, the protocol M KENK may suffer from man-in-the-middle attack when an intruder is able to recover N K by capturing any node in the network for example. In what follows, we describe the scenario of such attack. An intruder, denoted E, captures a previously authenticated node N in the network and compromises the network key. Node E intercepts the request sent from I to R, decrypts the request and builds an intruder request instead by replacing the nonce nI by its own nonce nE and pk(I) by pk(E). Node E encrypts this new request using N K and sends it to R. Node R decrypts the request, extracts pk(E) and computes KDH(R, E).

The response message to E becomes {pk(R), {nE, nR} K DH (E,R) }NK . Upon reception, node E decrypts the response message with N K, extract pk(R) and computes KDH(R, E). Node E uses the key computed to decrypt the nonce nR and sends it back to R encrypted with KDH(R, E).

In order to finish his attack, node E builds a response message {pk(E),-{nI , nE} K DH (E,I) }NK and sends it to node I. Using pk(I), which was extracted from the request originally sent by I, node E is able to compute KDH(E, I). Upon reception, the initiator I decrypts the received response using N K, computes KDH(E, I) and replies with nE encrypted with KDH(E, I).

In order to make the key establishment more resilient to node capture, we propose another protocol, called M KEK that uses sessions keys previously established with common neighbors in order to establish new keys. The protocol M KEK , depicted in Figure 4, uses the session keys established with common neighbors, denoted intermediate nodes J1 : k, in order to share a new key between an initiator I and a responder R.

We assume that the trusted path from I to R is determined by a routing mechanism. Unlike the protocol M KENK , nodes J1 : k are involved in the key establishment, they decrypt, modify and encrypt the exchanged messages between nodes I and R instead of just forwarding. Indeed, each intermediate node Jj, (j = 1, ..., k), extracts only the nonce from the request of the initiator I and replaces it by its own nonce nj . Upon the reception of a response message sent by the responder R, node Jj recovers and verifies its nonce nj and replies with the nonce extracted previously from the request. The adding of nonces nj at each hop helps to authenticate intermediate nodes. Note that KDH(I, R) is used as a common nonce between nodes I and R to ensure the mutual authentication between of I and R. Also, it should be noted that the protocol M KEK can only be used if nodes I and R have at least one common neighbor.

Results

We prove the correctness of all our protocols automatically using Scyther a tool for the automatic verification of security protocols. Cas Cremers has developed an automatic tool called Scyther [START_REF] Cremers | The Scyther Tool: Verification, falsification, and analysis of security protocols[END_REF]. It is a free tool available on all operating systems (Linux, Mac and Windows). This tool can automatically find attacks on cryptographic protocols and prove their security for bounded and unbounded numbers of sessions. One main advantage of Scyther is that it provides an easy way to model security properties like secrecy and authentication. This tool abstract the cost of the communications and the execution times of each cryptographic operation. Scyther uses the Dolev-Yao intruder model [START_REF] Dolev | On the security of public key protocols[END_REF]. In this model, the intruder controls the network and all communications pass through it. Which means that all packets can be captured by the intruder. Moreover the intruder has its own public and private pair of keys. Thus, it is able to play the role of any participant in the protocol. It can also encrypt messages with all public or symmetric keys that it knows and decrypts cipher-texts only if it knows the decryption key. In Table 2, we present the execution time for our protocols using TelosB which are very limited in calculation resources and are used as a base for comparison between the different protocols and not for obtaining the best results in terms of performance. Notice that these results are done with the minimum required cryptographic operations necessary to realize each protocol. For example, the evaluation of M KES, M KESlight, and M KENK is done without intermediate nodes between node I and R. Indeed, the intermediate nodes are just forwarding the messages between I and R. In contrast, we evaluated M KEK with one intermediate node between nodes I and R due to the necessity of one common neighbor node to use the session keys established with this neighbor. Note that M KESlight is the most efficient of all protocols. Indeed, the computation of new shared keys are done by nodes I and R in all protocols except M KESlight where only the sink S is doing this computation. So M KESlight is very suitable for protocols where the sink has more capacities than the sensor nodes. We note that the computation of new keys according to ECDH without interaction is about 3.2 seconds. This time consumption has a clear effect on the execution time of protocols. While the number of computation of new keys are equal in the M KES, M KENK and M KEK , M KEK differs from M KES and M KENK by the decryption/encryption operations done by intermediate nodes. Indeed, the difference is more than 400ms per each intermediate node. In addition, M KES and M KENK have almost the same cryptographic operations which is why their execution times are very close. We can expect that the protocol M KES is more suitable when nodes I and R are next to the sink while the protocol M KENK is more suitable when these nodes are too far from the sink. So in a given topology, nodes should be able to execute the protocol that is less consuming according to their positions relative to the sink.

Protocol name

Conclusion

In this paper, we proposed different methods for establishing a secret key between two authenticated nodes in a WSN. We presented and validated two protocols that enables authenticated nodes to establish a common key in a multihop manner with the intervention of the sink or the base station of the WSN.

In order to avoid exhausting nodes that are located near the sink with the key establishment requests, we proposed two protocols that allow nodes to establish secret keys without the intervention of the sink M KENK and M KEK . These latter protocols are based on the fact that nodes can use the network key to exchange key establishment messages or use previously established session keys on each hop. Depending on the type of keys that are used and the intervention of the sink, the resiliency of the protocol against intruder attacks is different. The most vulnerable protocol is the one that uses the network key without the intervention of the sink M KENK , but it is the fastest one. The most secure protocols are M KES and M KESlight, but they exhaust nodes that are near the sink and might take longer routes to reach the sink compared to M KENK and M KEK .

In our future work, we plan on evaluating the performance of each of these protocols with the presence of intermediate nodes between nodes that are establishing a new key, and between these nodes and the sink as well. Depending on the network topology, a trade-off might arise and we might need to make these protocols available at the same time and to be used according the relative positions of the involved nodes.

Fig. 1 :9BFig. 2 :

 12 Fig. 1: M KES: Multihop Key Establishment using the sink S to deliver public keys. KDH(I, R) is computed by the initiator I and the responder R.

4BFig. 3 :

 3 Fig. 3: M KENK : Multihop Key Establishment using the network key N K. No encryption/decryption operations on intermediate nodes.

Fig. 4 :

 4 Fig. 4: M KEK : Multihop Key Establishment using session keys. Encryption/decryption on every intermediate node.

Table 1 :

 1 Comparison of related work schemes.

			Base station symmetric	JAVA	none	manual
	Chan et al., 2005[3]	yes	Base station symmetric	yes	none	manual
	Yu et al., 2009[15]	yes	none	symmetric	none	TelosB	manual
	Munivel et al.,			symmetric/
	2010[11]	yes	Base station	asymmetric	manual	none	none
				symmetric/
	Our schemes	yes	Base station	asymmetric	none	TelosB automatic

Table 2 :

 2 Execution times of all protocols.

		Time	Time		Standard
		with S (ms)	without S (ms) Gain	deviation (ms)
	M KE S	6888.15	6625.94	4%	5.81
	M KE S -light 3679.30	365.85	90%	5.02
	M KE N K	6853.26	6853.26	0%	5.01
	M KE K	7434.95	7434.95	0%	3.44