Physical Zero-Knowledge Proofs for Cell-Coloring Nikoli Puzzles with Set Membership Verification

Iwamoto, Chuzo

doi:10.51094/jxiv.6584

##article.authors##

Iwamoto, Chuzo Hiroshima University https://researchmap.jp/read0184822

DOI:

https://doi.org/10.51094/jxiv.6584

キーワード:

Zero-knowledge proof、 Card-based cryptography、 Set membership、 Nikoli puzzle

抄録

Shimashimaropu and Kuralin are cell-coloring pencil puzzles
published by Nikoli, both of whose generalized versions are known to
be NP-complete. Since these puzzles are computationally hard,
solvers struggling with a difficult instance may suspect that it has
no solution. To address this, we propose physical zero-knowledge
proof (ZKP) protocols that verify the existence of a solution
without revealing it, thereby preserving the fun of solving the
puzzle. Our protocols utilize the Secret Swap Protocol---a
technique for the set membership problem---as a key building block.
This paper demonstrates the versatility of the Secret Swap Protocol
in handling various puzzle mechanics, including cell-coloring and
loop-forming rules.

利益相反に関する開示

There are no conflicts of interest to disclose.

ダウンロード *前日までの集計結果を表示します

ダウンロード実績データは、公開の翌日以降に作成されます。

引用文献

Nikoli: Puzzle Communication Nikoli. NIKOLI Co., Ltd., Tokyo (2026). (in Japanese), ISBN: 978-4890726844

Janko, O.: Shimashimaropu - Nikoli 188/#7. https://www.janko.at/Raetsel/Nikoli/188.htm#7. Accessed: 2026-09-22

Nikoli: Kuralin — Nikoli Official Website. https://www.nikoli.co.jp/en/puzzles/kuralin/. Accessed: 2026-09-22

Nikoli: Japanese Number Puzzles. NIKOLI Co., Ltd., Tokyo (2019). ISBN: 978-4890728503

Ruangwises, S.: Verifying the first nonzero term: physical zkps for ABC End View, Goishi Hiroi, and Toichika. J. Comb. Optim. 47(4), 69 (2024) https://doi.org/10.1007/S10878-024-01170-6

Iwamoto, C., Ohara, K.: Card-based zero-knowledge proof for Dosun-Fuwari. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 108(9), 1206–1210 (2025) https://doi.org/10.1587/TRANSFUN.2024DML0001

Otsuji, T., Fulla, P., Fukunaga, T.: Np-completeness and physical zero-knowledge proof of hotaru beam. In: Chen, Y., Gao, X., Sun, X., Zhang, A. (eds.) Computing and Combinatorics, pp. 239–251. Springer, Singapore (2024)

Hand, S.D., Koch, A., Lafourcade, P., Miyahara, D., Robert, L.: Efficient card-based ZKP for single loop condition and its application to Moon-or-Sun. New Gener. Comput. 42(3), 449–477 (2024) https://doi.org/10.1007/S00354-024-00274-1

Iwamoto, C., Ohara, K.: Card-based zero-knowledge proof for Nuritwin. In: Winter LA Symposium, Kyoto, Japan, January 26–28, 2026, vol. 21S, pp. 1–9 (2026)

Miyahara, D., Robert, L., Lafourcade, P., Kaneko, S.: When Locality Implies Globality: Card-Based ZKP Protocol for Shakashaka Puzzle. In: Iacono, J. (ed.) 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), vol. 366, pp. 33–13316. Schloss Dagstuhl – Leibniz-Zentrum f¨ur Informatik, Dagstuhl, Germany (2026). https://doi.org/10.4230/LIPIcs.FUN.2026.33 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.33

Lafourcade, P., Miyahara, D., Mizuki, T., Robert, L., Sasaki, T., Sone, H.: How to construct physical zero-knowledge proofs for puzzles with a “single loop” condition. Theoretical Computer Science 888, 41–55 (2021) https://doi.org/10.1016/j.tcs.2021.07.019

Sasaki, S., Shinagawa, K.: Physical zero-knowledge proof for Sukoro. New Gen. Comput. 42(3), 381–398 (2024) https://doi.org/10.1007/s00354-024-00271-4

Ruangwises, S.: Tatami printer: Physical zkps for Tatami puzzles. In: Finocchi, I., Georgiadis, L. (eds.) Algorithms and Complexity - 14th International Conference, CIAC 2025, Rome, Italy, June 10-12, 2025, Proceedings, Part I. Lecture Notes in Computer Science, vol. 15679, pp. 105–118. Springer, Cham (2025). https://doi.org/10.1007/978-3-031-92932-8_8

Miyahara, D., Robert, L., Lafourcade, P., Mizuki, T.: Zkp protocols for Usowan, Herugolf, and Five Cells. Tsinghua Science and Technology 29(6), 1651–1666 (2024) https://doi.org/10.26599/TST.2023.9010153

Iwamoto, C., Thanasine, C.: Shimashimaropu and Kuralin are NP-complete. Unpublished manuscript, submitted to an international journal (2026)