{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,7]],"date-time":"2026-03-07T14:17:19Z","timestamp":1772893039941,"version":"3.50.1"},"reference-count":34,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2024,5,1]],"date-time":"2024-05-01T00:00:00Z","timestamp":1714521600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2024,5,1]],"date-time":"2024-05-01T00:00:00Z","timestamp":1714521600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Comb Optim"],"published-print":{"date-parts":[[2024,5]]},"DOI":"10.1007\/s10878-024-01170-6","type":"journal-article","created":{"date-parts":[[2024,5,5]],"date-time":"2024-05-05T12:01:32Z","timestamp":1714910492000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Verifying the first nonzero term: physical ZKPs for ABC End View, Goishi Hiroi, and Toichika"],"prefix":"10.1007","volume":"47","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2820-1301","authenticated-orcid":false,"given":"Suthee","family":"Ruangwises","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2024,5,5]]},"reference":[{"key":"1170_CR1","doi-asserted-by":"crossref","unstructured":"Andersson D (2007) HIROIMONO is NP-complete. In: Proceedings of the 4th international conference on fun with algorithms (FUN), pp 30\u201339","DOI":"10.1007\/978-3-540-72914-3_5"},{"key":"1170_CR2","unstructured":"Bultel X, Dreier J, Dumas J-G, Lafourcade P (2016) 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"},{"key":"1170_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 (2018) 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","DOI":"10.1007\/978-3-030-03232-6_8"},{"key":"1170_CR4","doi-asserted-by":"crossref","unstructured":"Chien Y-F, Hon W-K (2010) 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","DOI":"10.1007\/978-3-642-13122-6_12"},{"key":"1170_CR5","doi-asserted-by":"crossref","unstructured":"Dumas J-G, Lafourcade P, Miyahara D, Mizuki T, Sasaki T, Sone H (2019) Interactive physical zero-knowledge proof for Norinori. In: Proceedings of the 25th international computing and combinatorics conference (COCOON), pp 166\u2013177","DOI":"10.1007\/978-3-030-26176-4_14"},{"key":"1170_CR6","doi-asserted-by":"crossref","unstructured":"Fukusawa T, Manabe Y (2022) Card-based zero-knowledge proof for the nearest neighbor property: zero-knowledge proof of ABC End View. In: Proceedings of the 12th international conference on security, privacy and applied cryptographic engineering (SPACE), pp 147\u2013161","DOI":"10.1007\/978-3-031-22829-2_9"},{"issue":"3","key":"1170_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 (1991) Proofs that yield nothing but their validity and a methodology of cryptographic protocol design. J ACM 38(3):691\u2013729","journal-title":"J ACM"},{"issue":"1","key":"1170_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 (1989) The knowledge complexity of interactive proof systems. SIAM J Comput 18(1):186\u2013208","journal-title":"SIAM J Comput"},{"issue":"2","key":"1170_CR9","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1007\/s00224-008-9119-9","volume":"44","author":"R Gradwohl","year":"2009","unstructured":"Gradwohl R, Naor M, Pinkas B, Rothblum GN (2009) Cryptographic and physical zero-knowledge proof systems for solutions of sudoku puzzles. Theory Comput Syst 44(2):245\u2013268","journal-title":"Theory Comput Syst"},{"key":"1170_CR10","doi-asserted-by":"crossref","unstructured":"Hand S, Koch A, Lafourcade P, Miyahara D, Robert L (2023) Check alternating patterns: a physical zero-knowledge proof for moon-or-sun. In: Proceedings of the 18th international workshop on security (IWSEC), pp 255\u2013272","DOI":"10.1007\/978-3-031-41326-1_14"},{"key":"1170_CR11","doi-asserted-by":"crossref","unstructured":"Hatsugai K, Asano K, Abe Y (2023) A physical Zero-knowledge proof for sumplete, a puzzle generated by ChatGPT. In: Proceedings of the 29th international computing and combinatorics conference (COCOON), in press","DOI":"10.1007\/978-3-031-49190-0_29"},{"key":"1170_CR12","unstructured":"Koch A, Walzer S (2020) Foundations for actively secure card-based cryptography. In: Proceedings of the 10th international conference on fun with algorithms (FUN), pp 17:1\u201317:23"},{"key":"1170_CR13","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/j.tcs.2021.07.019","volume":"888","author":"P Lafourcade","year":"2021","unstructured":"Lafourcade P, Miyahara D, Mizuki T, Robert L, Sasaki T, Sone H (2021) How to construct physical zero-knowledge proofs for puzzles with a \u201csingle loop\u2019\u2019 condition. Theoret Comput Sci 888:41\u201355","journal-title":"Theoret Comput Sci"},{"key":"1170_CR14","unstructured":"Miyahara D, Robert L, Lafourcade P, Takeshige S, Mizuki T, Shinagawa K, Nagao A, Sone H (2020) Card-based ZKP protocols for Takuzu and Juosan. In: Proceedings of the 10th international conference on fun with algorithms (FUN), pp 20:1\u201320:21"},{"issue":"9","key":"1170_CR15","doi-asserted-by":"publisher","first-page":"1072","DOI":"10.1587\/transfun.E102.A.1072","volume":"E102A","author":"D Miyahara","year":"2019","unstructured":"Miyahara D, Sasaki T, Mizuki T, Sone H (2019) Card-based physical zero-knowledge proof for kakuro. IEICE Trans Fundam E102A(9):1072\u20131078","journal-title":"IEICE Trans Fundam"},{"key":"1170_CR16","unstructured":"Nikoli (2001) Goishi Hiroi. https:\/\/www.nikoli.co.jp\/ja\/puzzles\/goishi_hiroi\/"},{"issue":"B","key":"1170_CR17","doi-asserted-by":"publisher","first-page":"104858","DOI":"10.1016\/j.ic.2021.104858","volume":"285","author":"L Robert","year":"2022","unstructured":"Robert L, Miyahara D, Lafourcade P, Libralesso L, Mizuki T (2022) Physical zero-knowledge proof and NP-completeness proof of Suguru puzzle. Inf Comput 285(B):104858","journal-title":"Inf Comput"},{"issue":"1","key":"1170_CR18","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/s00354-022-00155-5","volume":"40","author":"L Robert","year":"2022","unstructured":"Robert L, Miyahara D, Lafourcade P, Mizuki T (2022) Card-based ZKP for connectivity: applications to Nurikabe, Hitori, and Heyawake. N Gener Comput 40(1):149\u2013171","journal-title":"N Gener Comput"},{"key":"1170_CR19","doi-asserted-by":"crossref","unstructured":"Robert L, Miyahara D, Lafourcade P, Mizuki T (2022) Hide a liar: card-based ZKP protocol for Usowan. In: Proceedings of the 17th annual conference on theory and applications of models of computation (TAMC), pp 201\u2013217","DOI":"10.1007\/978-3-031-20350-3_17"},{"key":"1170_CR20","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2023.114071","volume":"972","author":"L Robert","year":"2023","unstructured":"Robert L, Miyahara D, Lafourcade P, Mizuki T (2023) Physical ZKP protocols for Nurimisaki and Kurodoko. Theoret Comput Sci 972:114071","journal-title":"Theoret Comput Sci"},{"issue":"5","key":"1170_CR21","doi-asserted-by":"publisher","first-page":"122","DOI":"10.1007\/s10878-023-01050-5","volume":"45","author":"S Ruangwises","year":"2023","unstructured":"Ruangwises S (2023) An improved physical ZKP for nonogram and nonogram color. J Comb Optim 45(5):122","journal-title":"J Comb Optim"},{"key":"1170_CR22","doi-asserted-by":"crossref","unstructured":"Ruangwises S (2023) Physical zero-knowledge proof for ball sort puzzle. In: Proceedings of the 19th conference on computability in Europe (CiE), pp 246\u2013257","DOI":"10.1007\/978-3-031-36978-0_20"},{"key":"1170_CR23","doi-asserted-by":"crossref","unstructured":"Ruangwises S (2023) Physical zero-knowledge proofs for five cells. In: Proceedings of the 8th international conference on cryptology and information security in Latin America (LATINCRYPT), pp 315\u2013330","DOI":"10.1007\/978-3-031-44469-2_16"},{"key":"1170_CR24","doi-asserted-by":"crossref","unstructured":"Ruangwises S (2023) Physically verifying the first nonzero term in a sequence: physical ZKPs for ABC End View and Goishi Hiroi. In: Proceedings of the 17th conference on frontiers of algorithmic wisdom (FAW), pp 171\u2013183","DOI":"10.1007\/978-3-031-39344-0_13"},{"key":"1170_CR25","unstructured":"Ruangwises S (2023) Toichika is NP-complete. In: Proceedings of the 25th Indonesia\u2013Japan conference on discrete and computational geometry, graphs, and games (IJCDC$$\\text{G}^3$$), p 96"},{"issue":"1","key":"1170_CR26","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s00354-021-00146-y","volume":"40","author":"S Ruangwises","year":"2022","unstructured":"Ruangwises S (2022) Two standard decks of playing cards are sufficient for a ZKP for Sudoku. N Gener Comput 40(1):49\u201365","journal-title":"N Gener Comput"},{"key":"1170_CR27","unstructured":"Ruangwises S, Itoh T (2022) How to physically verify a rectangle in a grid: a physical ZKP for Shikaku. In: Proceedings of the 11th international conference on fun with algorithms (FUN), pp 24:1\u201324:12"},{"issue":"1","key":"1170_CR28","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00354-020-00114-y","volume":"39","author":"S Ruangwises","year":"2021","unstructured":"Ruangwises S, Itoh T (2021) Physical zero-knowledge proof for Numberlink puzzle and $$k$$ vertex-disjoint paths problem. N Gener Comput 39(1):3\u201317","journal-title":"N Gener Comput"},{"key":"1170_CR29","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1016\/j.tcs.2021.09.034","volume":"895","author":"S Ruangwises","year":"2021","unstructured":"Ruangwises S, Itoh T (2021) Physical zero-knowledge proof for ripple effect. Theoret Comput Sci 895:115\u2013123","journal-title":"Theoret Comput Sci"},{"key":"1170_CR30","doi-asserted-by":"crossref","unstructured":"Ruangwises S, Itoh T (2021) Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems. In: Proceedings of the 19th international conference on unconventional computation and natural computation (UCNC), pp 149\u2013163","DOI":"10.1007\/978-3-030-87993-8_10"},{"key":"1170_CR31","doi-asserted-by":"crossref","unstructured":"Ruangwises S, Itoh T (2022) Physical ZKP for Makaro using a standard deck of cards. In: Proceedings of the 17th annual conference on theory and applications of models of computation (TAMC), pp 43\u201354","DOI":"10.1007\/978-3-031-20350-3_5"},{"key":"1170_CR32","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/j.tcs.2020.05.036","volume":"839","author":"T Sasaki","year":"2020","unstructured":"Sasaki T, Miyahara D, Mizuki T, Sone H (2020) Efficient card-based zero-knowledge proof for Sudoku. Theoret Comput Sci 839:135\u2013142","journal-title":"Theoret Comput Sci"},{"issue":"A9","key":"1170_CR33","doi-asserted-by":"publisher","first-page":"1900","DOI":"10.1587\/transfun.E100.A.1900","volume":"E100","author":"K Shinagawa","year":"2017","unstructured":"Shinagawa K, Mizuki T, Schuldt JCN, Nuida K, Kanayama N, Nishide T, Hanaoka G, Okamoto E (2017) Card-based protocols using regular polygon cards. IEICE Trans Fundam E100(A9):1900\u20131909","journal-title":"IEICE Trans Fundam"},{"issue":"4","key":"1170_CR34","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/s10207-019-00463-w","volume":"19","author":"I Ueda","year":"2020","unstructured":"Ueda I, Miyahara D, Nishimura A, Hayashi Y, Mizuki T, Sone H (2020) Secure implementations of a random bisection cut. Int J Inf Secur 19(4):445\u2013452","journal-title":"Int J Inf Secur"}],"container-title":["Journal of Combinatorial Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01170-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10878-024-01170-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10878-024-01170-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,5,17]],"date-time":"2024-05-17T13:12:01Z","timestamp":1715951521000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10878-024-01170-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,5]]},"references-count":34,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,5]]}},"alternative-id":["1170"],"URL":"https:\/\/doi.org\/10.1007\/s10878-024-01170-6","relation":{},"ISSN":["1382-6905","1573-2886"],"issn-type":[{"value":"1382-6905","type":"print"},{"value":"1573-2886","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,5]]},"assertion":[{"value":"12 April 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"5 May 2024","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author has no relevant financial or non-financial interests to disclose.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of interest"}}],"article-number":"69"}}