Two Standard Decks of Playing Cards Are Sufficient for a ZKP for Sudoku
| Autor: | Suthee Ruangwises |
|---|---|
| Rok vydání: | 2021 |
| Předmět: | |
| Zdroj: | Lecture Notes in Computer Science ISBN: 9783030895426 COCOON |
| DOI: | 10.1007/978-3-030-89543-3_52 |
| Popis: | Sudoku is a logic puzzle with an objective to fill a number between 1 and 9 into each empty cell of a \(9 \times 9\) grid such that every number appears exactly once in each row, each column, and each \(3 \times 3\) block. In 2020, Sasaki et al. proposed a physical zero-knowledge proof (ZKP) protocol for Sudoku using 90 cards, which allows a prover to physically show that he/she knows a solution without revealing it. However, their protocol requires nine identical copies of some cards, which cannot be found in a standard deck of playing cards (with 52 different cards and two jokers). Therefore, nine identical decks are actually required in order to perform that protocol. In this paper, we propose a new ZKP protocol for Sudoku that can be performed using only two standard decks of playing cards. In general, we develop the first ZKP protocol for an \(n \times n\) Sudoku that can be performed using a deck of all different cards. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|