nach oben

New Generation Computing

Erschienen in:

22.10.2020

Physical Zero-Knowledge Proof for Numberlink Puzzle and k Vertex-Disjoint Paths Problem

verfasst von: Suthee Ruangwises, Toshiya Itoh

Erschienen in: New Generation Computing | Ausgabe 1/2021

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

Numberlink is a logic puzzle with an objective to connect all pairs of cells with the same number 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 prover to convince a verifier that he/she knows a solution without revealing it. In particular, the protocol shows how to physically 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. Finally, we show that our protocol can be modified to verify a solution of the well-known k vertex-disjoint paths problem, both the undirected and directed settings.

Vorheriger Artikel Preface: Special Issue on Card-Based Cryptography

Nächster Artikel Card-Based Cryptographic Logical Computations Using Private Operations

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Step 5 is not necessary when verifying the last cell in the grid.

Adcock, A., Demaine, E.D., Demaine, M.L., O’Brien, M.P., Reidl, F., Villaamil, F.S., Sullivan, B.D.: Zig-zag numberlink is NP-complete. J. Inf. Process. 23(3), 239–245 (2015)

Bultel, X., Dreier, J., Dumas, J.-G., Lafourcade, P.: Physical zero-knowledge proofs for Akari, Takuzu, Kakuro and KenKen. In: Proceedings of the 8th International Conference on Fun with Algorithms (FUN), pp. 8:1–8:20 (2016)

Bultel, X., Dreier, J., Dumas, J.-G., Lafourcade, P., Miyahara, D., Mizuki, T., Nagao, A., Sasaki, T., Shinagawa, K., Sone, H.: Physical zero-knowledge proof for Makaro. In: Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 111–125 (2018)

Chien, Y.-F., Hon, W.-K.: Cryptographic and physical zero-knowledge proof: from Sudoku to Nonogram. In: Proceedings of the 5th International Conference on Fun with Algorithms (FUN), pp. 102–112 (2010)

Dumas, J.-G., Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: Interactive physical zero-knowledge proof for Norinori. In: Proceedings of the 25th International Computing and Combinatorics Conference (COCOON), pp. 166–177 (2019)

Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10(2), 111–121 (1980)MathSciNetCrossRef

Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. J. ACM 38(3), 691–729 (1991)CrossRef

Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRef

Google Play: Numberlink. https://play.google.com/store/search?q=Numberlink

10.

Gradwohl, R., Naor, M., Pinkas, B., Rothblum, G.N.: Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles. In: Proceedings of the 4th International Conference on Fun with Algorithms (FUN), pp. 166–182 (2007)

11.

Hashimoto, Y., Shinagawa, K., Nuida, K., Inamura, M., Hanaoka, G.: Secure grouping protocol using a deck of cards. In: Proceedings of the 10th International Conference on Information Theoretic Security (ICITS), pp. 135–152 (2017)

12.

Ibaraki, T., Manabe, Y.: 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), pp. 252–257 (2016)

13.

Ishikawa, R., Chida, E., Mizuki, T.: 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), pp. 215–226 (2015)

14.

Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5(1), 45–68 (1975)CrossRef

15.

Kotsuma, K., Takenaga, Y.: NP-completeness and enumeration of number link puzzle. IEICE Tech. Rep. 109(465), 1–7 (2010)

16.

Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: A Physical ZKP for slitherlink: how to perform physical topology-preserving computation. In: Proceedings of the 15th International Conference on Information Security Practice and Experience (ISPEC), pp. 135–151 (2019)

17.

Lynch, J.F.: The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newsl. 5(3), 31–36 (1975)CrossRef

18.

Miyahara, D., Sasaki, T., Mizuki, T., Sone, H.: Card-based physical zero-knowledge proof for Kakuro. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. E102.A(9), 1072–1078 (2019)CrossRef

19.

Nikoli: Numberlink. https://www.nikoli.co.jp/en/puzzles/numberlink.html

20.

Robertson, N., Seymour, P.D.: Disjoint paths— a survey. SIAM J. Algebr. Discret. Methods 6(2), 300–305 (1985)MathSciNetCrossRef

21.

Ruangwises, S., Itoh, T.: Physical zero-knowledge proof for numberlink. In: Proceedings of the 10th International Conference on Fun with Algorithms (FUN), pp. 22:1–22:11 (2020)

22.

Sasaki, T., Mizuki, T., Sone, H.: Card-based zero-knowledge proof for sudoku. In: Proceedings of the 9th International Conference on Fun with Algorithms (FUN), pp. 29:1–29:10 (2018)

23.

Shinagawa, K., Mizuki, T., Schuldt, J.C.N., Nuida, K., Kanayama, N., Nishide, T., Hanaoka, G., Okamoto, E.: Multi-party computation with small shuffle complexity using regular polygon cards. In: Proceedings of the 9th International Conference on Provable Security (ProvSec), pp. 127–146 (2015)

Titel: Physical Zero-Knowledge Proof for Numberlink Puzzle and k Vertex-Disjoint Paths Problem
verfasst von: Suthee Ruangwises
Toshiya Itoh
Publikationsdatum: 22.10.2020
Verlag: Ohmsha
Erschienen in: New Generation Computing / Ausgabe 1/2021
Print ISSN: 0288-3635
Elektronische ISSN: 1882-7055
DOI: https://doi.org/10.1007/s00354-020-00114-y

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Springer Professional "Technik"

Weitere Artikel der Ausgabe 1/2021

Analyzing Promising Researchers Using Network Centralities of Co-authorship Networks from Academic Literature

Learning Disjunctive Logic Programs from Nondeterministic Interpretation Transitions

Card-Based Cryptographic Logical Computations Using Private Operations

Card-Based Cryptography Meets Formal Verification

Jaccard Guided Perturbation for Eigenvector Localization

Tailored Network Splitting for Community Evolution Prediction in Dynamic Social Networks