ZKP Protocols for Usowan, Herugolf, and Five Cells
- 1 December 2024
- journal article
- research article
- Published by Tsinghua University Press in Tsinghua Science and Technology
- Vol. 29 (6) , 1651-1666
Abstract
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.Keywords
Funding Information
- Kayamori Foundation of Informational Science Advancement
This publication has 39 references indexed in Scilit:
- Physical ZKP for Makaro Using a Standard Deck of Cards2022
- Hide a Liar: Card-Based ZKP Protocol for Usowan2022
- An Improved Physical ZKP for Nonogram2021
- Physical ZKP for Connected Spanning Subgraph: Applications to Bridges Puzzle and Other Problems2021
- Zero-Knowledge Proof Protocol for Cryptarithmetic Using Dihedral Cards2021
- Physical Zero-Knowledge Proof for Suguru Puzzle2020
- Efficient Private PEZ Protocols for Symmetric Functions2019
- Interactive Physical Zero-Knowledge Proof for Norinori2019
- Physical Zero-Knowledge Proof for Makaro2018
- Polling with Physical Envelopes: A Rigorous Analysis of a Human-Centric Protocol2006