LIPIcs.FUN.2021.22.pdf
- Filesize: 394 kB
- 11 pages
Document
Physical Zero-Knowledge Proof for Numberlink
Authors
Suthee Ruangwises 
,
Toshiya Itoh
-
Part of:
Volume:
10th International Conference on Fun with Algorithms (FUN 2021)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-09-16
File
Document Identifiers
Author Details
- Department of Mathematical and Computing Science, Tokyo Institute of Technology, Japan
Cite As Get BibTex
Suthee Ruangwises and Toshiya Itoh. Physical Zero-Knowledge Proof for Numberlink. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 22:1-22:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FUN.2021.22
Abstract
Numberlink is a logic puzzle for which the player has to connect all pairs of cells with the same numbers by non-crossing paths in a rectangular grid. In this paper, we propose a physical protocol of zero-knowledge proof for Numberlink using a deck of cards, which allows a player to physically show that he/she knows a solution without revealing it. In particular, we develop a physical protocol to count the number of elements in a list that are equal to a given secret value without revealing that value, the positions of elements in the list that are equal to it, or the value of any other element in the list. Our protocol can also be applied to verify the existence of vertex-disjoint paths connecting all given pairs of endpoints in any undirected graph.
Subject Classification
ACM Subject Classification
- Security and privacy → Information-theoretic techniques
- Theory of computation → Cryptographic protocols
Keywords
- Zero-knowledge proof
- Card-based cryptography
- Numberlink
- Puzzles
- Games
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- A. Adcock, E.D. Demaine, M.L. Demaine, M.P. O'Brien, F. Reidl, F.S. Villaamil, and B.D. Sullivan. Zig-Zag Numberlink is NP-complete. Journal of Information Processing, 23(3):239-245, 2015. URL: https://doi.org/10.2197/ipsjjip.23.239.
- X. Bultel, J. Dreier, J.-G. Dumas, and P. Lafourcade. Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen. In Proceedings of the 8th International Conference on Fun with Algorithms (FUN), pages 8:1-8:20, 2016. URL: https://doi.org/10.4230/LIPIcs.FUN.2016.8.
- 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 Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pages 111-125, 2018. URL: https://doi.org/10.1007/978-3-030-03232-6_8.
- Y.-F. Chien and W.-K. Hon. Cryptographic and physical zero-knowledge proof: From Sudoku to Nonogram. In Proceedings of the 5th International Conference on Fun with Algorithms (FUN), pages 102-112, 2010. URL: https://doi.org/10.1007/978-3-642-13122-6_12.
- J.-G. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, T. Sasaki, and H. Sone. Interactive physical zero-knowledge proof for Norinori. In Proceedings of the 25th International Computing and Combinatorics Conference (COCOON), pages 166-177, 2019. URL: https://doi.org/10.1007/978-3-030-26176-4_14.
- O. Goldreich, S. Micali, and A. Wigderson. Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. Journal of the ACM, 38(3):691-729, 1991. URL: https://doi.org/10.1145/116825.116852.
- S. Goldwasser, S. Micali, and C. Rackoff. The knowledge complexity of interactive proof systems. SIAM Journal on Computing, 18(1):186-208, 1989. URL: https://doi.org/10.1137/0218012.
- Google Play: Numberlink. URL: https://play.google.com/store/search?q=Numberlink.
- R. Gradwohl, M. Naor, B. Pinkas, and G.N. Rothblum. Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles. In Proceedings of the 4th International Conference on Fun with Algorithms (FUN), pages 166-182, 2007. URL: https://doi.org/10.1007/978-3-540-72914-3_16.
- Y. Hashimoto, K. Shinagawa, K. Nuida, M. Inamura, and G. Hanaoka. Secure grouping protocol using a deck of cards. In Proceedings of the 10th International Conference on Information Theoretic Security (ICITS), pages 135-152, 2017. URL: https://doi.org/10.1007/978-3-319-72089-0_8.
- T. Ibaraki and Y. Manabe. A more efficient card-based protocol for generating a random permutation without fixed points. In Proceedings of the 3rd International Conference on Mathematics and Computers in Sciences and Industry (MCSI), pages 252-257, 2016. URL: https://doi.org/10.1109/MCSI.2016.054.
- R. Ishikawa, E. Chida, and T. Mizuki. Efficient card-based protocols for generating a hidden random permutation without fixed points. In Proceedings of the 14th International Conference on Unconventional Computation and Natural Computation (UCNC), pages 215-226, 2015. URL: https://doi.org/10.1007/978-3-319-21819-9_16.
-
K. Kotsuma and Y. Takenaga. NP-completeness and enumeration of Number Link puzzle. IEICE Technical Report, 109(465):1-7, 2010.
- J.F. Lynch. The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newsletter, 5(3):31-36, 1975. URL: https://doi.org/10.1145/1061425.1061430.
- D. Miyahara, T. Sasaki, T. Mizuki, and H. Sone. Card-based physical zero-knowledge proof for Kakuro. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E102.A(9):1072-1078, 2019. URL: https://doi.org/10.1587/transfun.E102.A.1072.
- Nikoli: Numberlink. URL: https://www.nikoli.co.jp/en/puzzles/numberlink.html.
- T. Sasaki, T. Mizuki, and H. Sone. Card-based zero-knowledge proof for Sudoku. In Proceedings of the 9th International Conference on Fun with Algorithms (FUN), pages 29:1-29:10, 2018. URL: https://doi.org/10.4230/LIPIcs.FUN.2018.29.