Graduate School of Informatics and Engineering, The University of Electro-Communications, Tokyo 1828585, Japan
MIS Lab, University of Picardy Jules Verne, Amiens 80000, France
Laboratory of Computer Science, Modelling and Systems Optimisation, University of Clermont Auvergne, Clermont-Ferrand 63178, France
Cyberscience Center, Tohoku University, Sendai 9808578, Japan
Show Author Information
Hide Author Information
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.
No abstract is available for this article. Click the button above to view the PDF directly.
References
[1]
L. Robert, D. Miyahara, P. Lafourcade, and T. Mizuki, Hide a liar: Card-based ZKP protocol for usowan, in Proc. 17th Int. Conf. Theory and Applications of Models of Computation, Tianjin, China, 2022, pp. 201–217.
C. Iwamoto, M. Haruishi, and T. Ibusuki, Herugolf and Makaro are NP-complete, in Proc. 9th Int. Conf. Fun with Algorithms, La Maddalena, Italy, 2018, pp. 24: 1–24: 11.
[5]
C. Iwamoto and T. Ide, Five cells and tilepaint are NP-complete, IEICE Trans. Inf. Syst., vol. 105-D, no. 3, pp. 508–516, 2022.
S. Goldwasser, S. Micali, and C. Rackoff, The knowledge complexity of interactive proof-systems, in Proc. Seventeenth Annu. ACM Symp. Theory of Computing, Providence, RI, USA, 1985, pp. 291–304.
J. Dreier, H. Jonker, and P. Lafourcade, Secure auctions without cryptography, in Proc. 7th Int. Conf. Fun with Algorithms, Lipari Island, Italy, 2014, pp. 158–170.
B. D. Boer, More efficient match-making and satisfiability the five card trick, in Proc. Workshop on the Theory and Application of of Cryptographic Techniques, Houthalen, Belgium, 1989, pp. 208–217.
P. Lafourcade, D. Miyahara, T. Mizuki, L. Robert, T. Sasaki, and H. Sone, How to construct physical zero-knowledge proofs for puzzles with a “single loop” condition, Theor. Comput. Sci., vol. 888, pp. 41–55, 2021.
K. Shinagawa, T. Mizuki, J. C. N. Schuldt, K. Nuida, N. Kanayama, T. Nishide, G. Hanaoka, and E. Okamoto, Secure computation protocols using polarizing cards, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., vol. E99. A, no. 6, pp. 1122–1131, 2016.
K. Shinagawa, T. Mizuki, J. C. N. Schuldt, K. Nuida, N. Kanayama, T. Nishide, G. Hanaoka, and E. Okamoto, Cardbased protocols using regular polygon cards, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., vol. E100. A, no. 9, pp. 1900–1909, 2017.
T. Mizuki, Efficient and secure multiparty computations using a standard deck of playing cards, in Proc. 15th Int. Conf. Cryptology and Network Security, Milan, Italy, 2016, pp. 484–499.
J. Balogh, J. A. Csirik, Y. Ishai, and E. Kushilevitz, Private computation using a PEZ dispenser, Theor. Comput. Sci., vol. 306, nos. 1–3, pp. 69–84, 2003.
Y. Abe, M. Iwamoto, and K. Ohta, Efficient private PEZ protocols for symmetric functions, in Proc. 17th Theory of Cryptography Conf., Nuremberg, Germany, 2019, pp. 372–392.
T. Mizuki, Y. Kugimoto, and H. Sone, Secure multiparty computations using a dial lock, in Proc. 4th Int. Conf. Theory and Applications of Models of Computation, Shanghai, China, 2007, pp. 499–510.
T. Mizuki, Y. Kugimoto, and H. Sone, Secure multiparty computations using the 15 puzzle, in Proc. First Int. Conf. Combinatorial Optimization and Applications, Xi’an, China, 2007, pp. 255–266.
T. Moran and M. Naor, Polling with physical envelopes: A rigorous analysis of a human-centric protocol, in Proc. 25th Annu. Int. Conf. the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, 2006, pp. 88–108.
T. Moran and M. Naor, Split-ballot voting: Everlasting privacy with distributed trust, in Proc. 14th ACM Conf. Computer and Communications Security, Alexandria, VA, USA, 2007, pp. 246–255.
T. Sasaki, D. Miyahara, T. Mizuki, and H. Sone, Efficient card-based zero-knowledge proof for Sudoku, Theor. Comput. Sci., vol. 839, pp. 135–142, 2020.
X. Bultel, J. Dreier, J. G. Dumas, and P. Lafourcade, Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen, in Proc. 8th Int. Conf. Fun with Algorithms, La Maddalena, Italy, 2016, pp. 8: 1–8: 20.
[24]
D. Miyahara, L. Robert, P. Lafourcade, S. Takeshige, T. Mizuki, K. Shinagawa, A. Nagao, and H. Sone, Card-based ZKP protocols for Takuzu and Juosan, in Proc. 10th Int. Conf. Fun with Algorithms, Favignana Island, Italy, 2021, pp. 20: 1–20: 21.
[25]
D. Miyahara, T. Sasaki, T. Mizuki, and H. Sone, Card-based physical zero-knowledge proof for Kakuro, Fundam. Electron. Commun. Comput. Sci., vol. E102. A, no. 9, pp. 1072–1078, 2019.
X. Bultel, J. Dreier, J. G. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, A. Nagao, T. Sasaki, K. Shinagawa, and H. Sone, Physical zero-knowledge proof for Makaro, in Proc. 20th Int. Symp. on Stabilizing, Safety, and Security of Distributed Systems, Tokyo, Japan, 2018, pp. 111–125.
S. Ruangwises and T. Itoh, Physical ZKP for Makaro using a standard deck of cards, in Proc. 17th Int. Conf. Theory and Applications of Models of Computation, Tianjin, China, 2022, pp. 43–54.
J. G. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, T. Sasaki, and H. Sone, Interactive physical zero-knowledge proof for Norinori, in Proc. 25th Int. Computing and Combinatorics Conf., Xi’an, China, 2019, pp. 166–177.
Y. F. Chien and W. K. Hon, Cryptographic and physical zero-knowledge proof: From Sudoku to Nonogram, in Proc. 5th Int. Conf. Fun with Algorithms, Ischia, Italy, 2010, pp. 102–112.
S. Ruangwises, An improved physical ZKP for Nonogram, in Proc. 15th Int. Conf. Combinatorial Optimization and Applications, Tianjin, China, 2021, pp. 262–272.
L. Robert, D. Miyahara, P. Lafourcade, and T. Mizuki, Card-based ZKP protocol for Nurimisaki, in Proc. 24th Int. Symp. on Stabilizing, Safety, and Security of Distributed Systems, Clermont-Ferrand, France, 2022, pp. 285–298.
L. Robert, D. Miyahara, P. Lafourcade, and T. Mizuki, Physical zero-knowledge proof for suguru puzzle, in Proc. 22nd Int. Symp. on Stabilizing, Safety, and Security of Distributed Systems, Austin, TX, USA, 2020, pp. 235–247.
L. Robert, D. Miyahara, P. Lafourcade, L. Libralesso, and T. Mizuki, Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle, Inf. Comput., vol. 285, p. 104858, 2022.
L. Robert, D. Miyahara, P. Lafourcade, and T. Mizuki, Card-based ZKP for connectivity: Applications to Nurikabe, Hitori, and Heyawake, New Gener. Comput., vol. 40, no. 1, pp. 149–171, 2022.
S. Ruangwises and T. Itoh, Physical zero-knowledge proof for Numberlink puzzle and k vertex-disjoint paths problem, New Gener. Comput., vol. 39, no. 1, pp. 3–17, 2021.
S. Ruangwises and T. Itoh, Physical ZKP for connected spanning subgraph: Applications to bridges puzzle and other problems, in Proc. 19th Int. Conf. Unconventional Computation and Natural Computation, Espoo, Finland, 2021, pp. 149–163.
S. Ruangwises and T. Itoh, How to physically verify a rectangle in a grid: A physical ZKP for shikaku, in Proc. 11th Int. Conf. Fun with Algorithms, Favignana Island, Italy, 2022, pp. 24: 1–24: 12.
[39]
R. Isuzugawa, D. Miyahara, and T. Mizuki, Zero-knowledge proof protocol for Cryptarithmetic using dihedral cards, in Proc. 19th Int. Conf. Unconventional Computation and Natural Computation, Espoo, Finland, 2021, pp. 51–67.
S. Ruangwises, Physical zero-knowledge proofs for five cells, in Proc. 8th Int. Conf. Cryptology and Information Security in Latin America, Quito, Ecuador, 2023, pp. 315–330.
T. Mizuki and H. Sone, Six-card secure AND and four-card secure XOR, in Proc. Third Int. Workshop on Frontiers in Algorithmics, Hefei, China, 2009, pp. 358–369.
A. Koch and S. Walzer, Foundations for actively secure card-based cryptography, in Proc. 10th Int. Conf. Fun with Algorithms, Favignana Island, Italy, 2021, pp. 17: 1–17: 23.
[45]
R. Gradwohl, M. Naor, B. Pinkas, and G. N. Rothblum, Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles, Theory Comput. Syst., vol. 44, no. 2, pp. 245–268, 2009.
Miyahara D, Robert L, Lafourcade P, et al. ZKP Protocols for Usowan, Herugolf, and Five Cells. Tsinghua Science and Technology, 2024, 29(6): 1651-1666. https://doi.org/10.26599/TST.2023.9010153
The articles published in this open access journal are distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/).
