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.
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.
In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and the prover knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have an extractability error with a non-zero probability, or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof of knowledge for Sudoku using a normal deck of playing cards with no extractability error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.
In 2009, Gradwohl, Naor, Pinkas, and Rothblum proposed physical zero-knowledge proof protocols for Sudoku. That is, for a puzzle instance of Sudoku, their excellent protocols allow a prover to convince a verifier that there is a solution to the Sudoku puzzle and that he/she knows it, without revealing any information about the solution. The possible drawback is that the existing protocols have a soundness error with a non-zero probability or need special cards (such as scratch-off cards). Thus, in this study, we propose new protocols to perform zero-knowledge proof for Sudoku that use a normal deck of playing cards and have no soundness error. Our protocols can be easily implemented by humans with a reasonable number of playing cards.
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.
Sudoku is a popular pencil puzzle where a player fills in the empty cells with numbers on an n × n board so that each row, column, and -block must contain all the numbers from 1 to n; a typical puzzle size is n = 9. In 2007, Gradwohl, Naor, Pinkas, and Rothblum proposed a physical zero-knowledge proof protocol for Sudoku using a physical deck of cards; their card-based protocol requires 3nℓ shuffles, where ℓ is a security parameter to eliminate the soundness error. Since the invention of this seminal protocol, several soundness-error-free protocols were constructed to reduce the number of required shuffles; the state-of-the-art one was designed in 2023, which uses shuffles. In this paper, we show that only three or two shuffles are sufficient to construct a zero-knowledge proof protocol for Sudoku, no matter how large n is, i.e., we propose two card-based protocols using constant numbers (namely, 3 and 2) of shuffles. Our proposed protocols are simple and efficient enough for people to execute for a 9 × 9 Sudoku puzzle in reality.
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.
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.