Abstract Decomposition puzzles are pencil-and-paper logic puzzles that involve partitioning a rectangular grid into several regions to satisfy certain rules. In this paper, we construct a generic card-based protocol called printing protocol, which can be used to physically verify solutions of decompositon puzzles. We apply the printing protocol to develop card-based zero-knowledge proof protocols for two such puzzles: Five Cells and Meadows. These protocols allow a prover to physically show that he/she knows solutions of the puzzles without revealing them.
Abstract Decomposition puzzles are pencil-and-paper logic puzzles that involve partitioning a rectangular grid into several regions to satisfy certain rules. In this paper, we construct a generic card-based protocol called printing protocol, which can be used to physically verify solutions of decompositon puzzles. We apply the printing protocol to develop card-based zero-knowledge proof protocols for two such puzzles: Five Cells and Meadows. These protocols allow a prover to physically show that he/she knows solutions of the puzzles without revealing them.
A Zero-Knowledge Proof (ZKP) protocol allows a participant to prove the knowledge of some secret without revealing any information about it. While such protocols are typically executed by computers, there exists a line of research proposing physical instances of ZKP protocols. Up to now, many card-based ZKP protocols for pen-and-pencil puzzles, like Sudoku, have been designed. Those games, mostly edited by Nikoli, have simple rules, yet designing them in card-based ZKP protocols is non-trivial. In this work, we propose a card-based ZKP protocol for Usowan, a Nikoli game. In Usowan, for each room of a puzzle instance, there is exactly one piece of false information. The goal of the game is to detect this wrong data amongst the correct data and also to satisfy the other rules. Designing a card-based ZKP protocol to deal with the property of detecting a liar has never been done. In some sense, we propose a physical ZKP for hiding of a liar. This work extends a previous paper appearing in Ref. [1]. In this extension, we propose two other protocols, for Herugolf and Five Cells. The puzzles are specifically chosen because each of those three puzzles shares a common constraint, connectivity. However, showing the connected configuration cannot be done with generic approach and brings new construction to the existing connectivity ZKP protocol. Indeed, in Herugolf, the connectivity is handled with a given length of cell which is decremental (i.e., the length of each connected cell decreases by one at each step). For Five Cells, there is an additional step in the setup allowing to encode all the information needed to ensure a valid ZKP protocol.
Shikaku is a pencil puzzle consisting of a rectangular grid, with some cells containing a number. The player has to partition the grid into rectangles such that each rectangle contains exactly one number equal to the area of that rectangle. In this paper, we propose two physical zero-knowledge proof protocols for Shikaku using a deck of playing cards, which allow a prover to physically show that he/she knows a solution of the puzzle without revealing it. Most importantly, in our second protocol we develop a general technique to physically verify a rectangle-shaped area with a certain size in a rectangular grid, which can be used to verify other problems with similar constraints.
Card-based zero-knowledge proof (ZKP) protocols allow a prover to convince a verifier that it knows a witness of a given statement, without revealing any information, using a physical deck of playing cards. Previous studies have focused on puzzles with a specific connected component, such as a simple cycle and a polyomino. In this study, we propose a unified approach to handle a family of connected components, including a tree, path, cycle, and polyomino. This approach achieves this verification in O(mn) steps relative to a given grid size m × n. Using this approach, we construct a card-based ZKP protocol for Nurimeizu, where the goal is to find the shortest path on a given grid.
A zero-knowledge proof (ZKP) is an interactive proof between a prover and a verifier, with the prover's goal to convince the verifier that a solution of a computation problem exists without revealing any information about the solution itself. A card-based physical ZKP is an implementation of a ZKP using physical cards. Several metrics are used to measure the efficiency of card-based ZKPs, such as the numbers of required cards and shuffles. In this paper, we propose the first card-based ZKP for a puzzle Sudoku that uses only one shuffle. To achieve this, we use a technique of applying private operations interactively to prepare inputs for the protocol.
Abstract A zero-knowledge proof (ZKP) allows a prover to prove to a verifier that it knows some secret, such as a solution to a difficult puzzle, without revealing any information about it. In recent years, ZKP protocols using only a deck of playing cards for solutions to various pencil puzzles have been proposed. The previous work of Lafourcade et al. deals with a famous puzzle called Slitherlink. Their proposed protocol can verify that a solution forms a single loop without revealing anything about the solution, except this fact. Their protocol guarantees that the solution satisfies the single-loop condition, by interactively constructing a solution starting from a state that holds a simple single loop, and proceeding via steps that preserve the invariant of encoding a single loop, until the proper solution is reached. A drawback of their protocol is that it requires additional verifications to guarantee a single loop. In this study, we propose a more efficient ZKP protocol for such a puzzle with fewer additional verifications. For this, we employ the previous work of Robert et al., which addressed the connectivity property in a puzzle. That is, we verify that a solution is connected but not split, to be a single loop. Applying our proposal, we construct a card-based ZKP protocol for Moon-or-Sun, which has its specific rule of alternating pattern in addition to the single-loop condition.
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.