{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T17:16:55Z","timestamp":1760203015158,"version":"3.37.3"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,10,22]],"date-time":"2020-10-22T00:00:00Z","timestamp":1603324800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,10,22]],"date-time":"2020-10-22T00:00:00Z","timestamp":1603324800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["New Gener. Comput."],"published-print":{"date-parts":[[2021,4]]},"DOI":"10.1007\/s00354-020-00114-y","type":"journal-article","created":{"date-parts":[[2020,10,22]],"date-time":"2020-10-22T13:02:58Z","timestamp":1603371778000},"page":"3-17","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":51,"title":["Physical Zero-Knowledge Proof for Numberlink Puzzle and k Vertex-Disjoint Paths Problem"],"prefix":"10.1007","volume":"39","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2820-1301","authenticated-orcid":false,"given":"Suthee","family":"Ruangwises","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1149-7046","authenticated-orcid":false,"given":"Toshiya","family":"Itoh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,10,22]]},"reference":[{"issue":"3","key":"114_CR1","first-page":"239","volume":"23","author":"A Adcock","year":"2015","unstructured":"Adcock, A., Demaine, E.D., Demaine, M.L., O\u2019Brien, M.P., Reidl, F., Villaamil, F.S., Sullivan, B.D.: Zig-zag numberlink is NP-complete. J. Inf. Process. 23(3), 239\u2013245 (2015)","journal-title":"J. Inf. Process."},{"key":"114_CR2","unstructured":"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\u20138:20 (2016)"},{"key":"114_CR3","doi-asserted-by":"crossref","unstructured":"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\u2013125 (2018)","DOI":"10.1007\/978-3-030-03232-6_8"},{"key":"114_CR4","doi-asserted-by":"crossref","unstructured":"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\u2013112 (2010)","DOI":"10.1007\/978-3-642-13122-6_12"},{"key":"114_CR5","doi-asserted-by":"crossref","unstructured":"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\u2013177 (2019)","DOI":"10.1007\/978-3-030-26176-4_14"},{"issue":"2","key":"114_CR6","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1016\/0304-3975(80)90009-2","volume":"10","author":"S Fortune","year":"1980","unstructured":"Fortune, S., Hopcroft, J., Wyllie, J.: The directed subgraph homeomorphism problem. Theoret. Comput. Sci. 10(2), 111\u2013121 (1980)","journal-title":"Theoret. Comput. Sci."},{"issue":"3","key":"114_CR7","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O Goldreich","year":"1991","unstructured":"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\u2013729 (1991)","journal-title":"J. ACM"},{"issue":"1","key":"114_CR8","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186\u2013208 (1989)","journal-title":"SIAM J. Comput."},{"key":"114_CR9","unstructured":"Google Play: Numberlink. https:\/\/play.google.com\/store\/search?q=Numberlink"},{"key":"114_CR10","doi-asserted-by":"crossref","unstructured":"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\u2013182 (2007)","DOI":"10.1007\/978-3-540-72914-3_16"},{"key":"114_CR11","doi-asserted-by":"crossref","unstructured":"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\u2013152 (2017)","DOI":"10.1007\/978-3-319-72089-0_8"},{"key":"114_CR12","doi-asserted-by":"crossref","unstructured":"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\u2013257 (2016)","DOI":"10.1109\/MCSI.2016.054"},{"key":"114_CR13","doi-asserted-by":"crossref","unstructured":"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\u2013226 (2015)","DOI":"10.1007\/978-3-319-21819-9_16"},{"issue":"1","key":"114_CR14","doi-asserted-by":"publisher","first-page":"45","DOI":"10.1002\/net.1975.5.1.45","volume":"5","author":"RM Karp","year":"1975","unstructured":"Karp, R.M.: On the computational complexity of combinatorial problems. Networks 5(1), 45\u201368 (1975)","journal-title":"Networks"},{"issue":"465","key":"114_CR15","first-page":"1","volume":"109","author":"K Kotsuma","year":"2010","unstructured":"Kotsuma, K., Takenaga, Y.: NP-completeness and enumeration of number link puzzle. IEICE Tech. Rep. 109(465), 1\u20137 (2010)","journal-title":"IEICE Tech. Rep."},{"key":"114_CR16","doi-asserted-by":"crossref","unstructured":"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\u2013151 (2019)","DOI":"10.1007\/978-3-030-34339-2_8"},{"issue":"3","key":"114_CR17","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1061425.1061430","volume":"5","author":"JF Lynch","year":"1975","unstructured":"Lynch, J.F.: The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newsl. 5(3), 31\u201336 (1975)","journal-title":"ACM SIGDA Newsl."},{"issue":"9","key":"114_CR18","doi-asserted-by":"publisher","first-page":"1072","DOI":"10.1587\/transfun.E102.A.1072","volume":"E102.A","author":"D Miyahara","year":"2019","unstructured":"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\u20131078 (2019)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"key":"114_CR19","unstructured":"Nikoli: Numberlink. https:\/\/www.nikoli.co.jp\/en\/puzzles\/numberlink.html"},{"issue":"2","key":"114_CR20","doi-asserted-by":"publisher","first-page":"300","DOI":"10.1137\/0606030","volume":"6","author":"N Robertson","year":"1985","unstructured":"Robertson, N., Seymour, P.D.: Disjoint paths\u2014 a survey. SIAM J. Algebr. Discret. Methods 6(2), 300\u2013305 (1985)","journal-title":"SIAM J. Algebr. Discret. Methods"},{"key":"114_CR21","unstructured":"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\u201322:11 (2020)"},{"key":"114_CR22","unstructured":"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\u201329:10 (2018)"},{"key":"114_CR23","doi-asserted-by":"crossref","unstructured":"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\u2013146 (2015)","DOI":"10.1007\/978-3-319-26059-4_7"}],"container-title":["New Generation Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-020-00114-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00354-020-00114-y\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00354-020-00114-y.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,10,21]],"date-time":"2021-10-21T23:45:40Z","timestamp":1634859940000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00354-020-00114-y"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,10,22]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2021,4]]}},"alternative-id":["114"],"URL":"https:\/\/doi.org\/10.1007\/s00354-020-00114-y","relation":{},"ISSN":["0288-3635","1882-7055"],"issn-type":[{"type":"print","value":"0288-3635"},{"type":"electronic","value":"1882-7055"}],"subject":[],"published":{"date-parts":[[2020,10,22]]},"assertion":[{"value":"5 May 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"6 October 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"22 October 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}