AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Tsinghua Science and Technology Article
PDF (2.9 MB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

ZKP Protocols for Usowan, Herugolf, and Five Cells

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

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

Zero-Knowledge Proof (ZKP) protocolplaying cardscard-based cryptographyphysical assumptionsUsowanHerugolfFive Cells

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.
Crossref
[2]
Nikoli, Usowan, https://www.nikoli.co, 2023.
[3]

C. Iwamoto and M. Haruishi, Computational complexity of Usowan puzzles, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., vol. E101. A, no. 9, pp. 1537–1540, 2018.
Crossref Google Scholar
[4]
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.
Crossref Google Scholar
[6]
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.
Crossref
[7]
T. Mizuki and H. Shizuya, Practical card-based cryptography, in Proc. 7th Int. Conf. Fun with Algorithms, Lipari Island, Italy, 2014, pp. 313–324.
Crossref
[8]
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.
Crossref
[9]
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.
Crossref
[10]

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.
Crossref Google Scholar
[11]

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.
Crossref Google Scholar
[12]

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.
Crossref Google Scholar
[13]
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.
Crossref
[14]

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.
Crossref Google Scholar
[15]
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.
Crossref
[16]
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.
Crossref
[17]
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.
Crossref
[18]

T. Moran and M. Naor, Basing cryptographic protocols on tamper-evident seals, Theor. Comput. Sci., vol. 411, no. 10, pp. 1283–1310, 2010.
Crossref Google Scholar
[19]
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.
Crossref
[20]
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.
Crossref
[21]

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.
Crossref Google Scholar
[22]

S. Ruangwises, Two standard decks of playing cards are sufficient for a ZKP for Sudoku, New Gener. Comput., vol. 40, no. 1, pp. 49–65, 2022.
Crossref Google Scholar
[23]
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.
Crossref Google Scholar
[26]
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.
Crossref
[27]
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.
Crossref
[28]
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.
Crossref
[29]
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.
Crossref
[30]
S. Ruangwises, An improved physical ZKP for Nonogram, in Proc. 15th Int. Conf. Combinatorial Optimization and Applications, Tianjin, China, 2021, pp. 262–272.
Crossref
[31]
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.
Crossref
[32]
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.
Crossref
[33]

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.
Crossref Google Scholar
[34]

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.
Crossref Google Scholar
[35]

S. Ruangwises and T. Itoh, Physical zero-knowledge proof for Ripple Effect, Theor. Comput. Sci., vol. 895, pp. 115–123, 2021.
Crossref Google Scholar
[36]

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.
Crossref Google Scholar
[37]
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.
Crossref
[38]
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.
Crossref
[40]
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.
Crossref
[41]

S. Ruangwises and T. Itoh, Securely computing the n-variable equality function with 2 n cards, Theor. Comput. Sci., vol. 887, pp. 99–110, 2021.
Crossref Google Scholar
[42]

A. Nishimura, Y. I. Hayashi, T. Mizuki, and H. Sone, Pile-shifting scramble for card-based protocols, IEICE Trans. Fundam. Electron. Commun. Comput. Sci., vol. E101. A, no. 9, pp. 1494–1502, 2018.
Crossref Google Scholar
[43]
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.
Crossref
[44]
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.
Crossref Google Scholar
Tsinghua Science and Technology
Volume 29 Issue 6,
December 2024
Pages 1651-1666
DOI: 10.26599/TST.2023.9010153
Cite this article:
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

392

Views

48

Downloads

0

Crossref

0

Web of Science

1

Scopus

0

CSCD

Altmetrics
Received: 12 February 2023
Revised: 06 September 2023
Accepted: 04 December 2023
Published: 20 June 2024
© The Author(s) 2024.

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/).
Return