ZKP Protocols for Usowan,Herugolf,and Five Cells  

作　　者：Daiki Miyahara Léo Robert Pascal Lafourcade Takaaki Mizuki 

机构地区：[1]Graduate School of Informatics and Engineering,The University of Electro-Communications,Tokyo 1828585,Japan [2]MIS Lab,University of Picardy Jules Verne,Amiens 80000,France [3]Laboratory of Computer Science,Modelling and Systems Optimisation,University of Clermont Auvergne,Clermont-Ferrand 63178,France [4]Cyberscience Center,Tohoku University,Sendai 9808578,Japan

出　　处：《Tsinghua Science and Technology》2024年第6期1651-1666,共16页清华大学学报自然科学版（英文版）

基　　金：supported by the French ANR project ANR-18-CE39-0019(MobiS5);Other programs also fund to write this paper,namely the French government research program“Investissements d’Avenir”through the IDEX-ISITE initiative 16-IDEX-0001(CAP 20-25);the IMobS3 Laboratory of Excellence(No.ANR-10-LABX-16-01);Finally,the French ANR project DECRYPT(No.ANR-18-CE39-0007);SEVERITAS(No.ANR-20-CE39-0009)also subsidize this work;The first author was supported in part by Kayamori Foundation of Informational Science Advancement and JSPS KAKENHI(No.JP23H00479);The fourth author was supported in part by JSPS KAKENHI(Nos.JP21K11881 and JP23H00479).

摘　　要：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.

关 键 词：Zero-Knowledge Proof(ZKP)protocol playing cards card-based cryptography physical assumptions Usowan Herugolf FiveCells 

分 类 号：TP39[自动化与计算机技术—计算机应用技术]