{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,15]],"date-time":"2026-07-15T10:12:31Z","timestamp":1784110351847,"version":"3.55.0"},"publisher-location":"Singapore","reference-count":11,"publisher":"Springer Nature Singapore","isbn-type":[{"value":"9789819610891","type":"print"},{"value":"9789819610907","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"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":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-981-96-1090-7_20","type":"book-chapter","created":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T16:33:07Z","timestamp":1741105987000},"page":"239-251","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["NP-Completeness and\u00a0Physical Zero-Knowledge Proof of\u00a0Hotaru Beam"],"prefix":"10.1007","author":[{"given":"Taisei","family":"Otsuji","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2324-2323","authenticated-orcid":false,"given":"Peter","family":"Fulla","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3285-2876","authenticated-orcid":false,"given":"Takuro","family":"Fukunaga","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2025,3,5]]},"reference":[{"key":"20_CR1","unstructured":"Wikipedia: Hotaru beam. https:\/\/en.wikipedia.org\/wiki\/Hotaru_Beam"},{"issue":"3","key":"20_CR2","doi-asserted-by":"publisher","first-page":"187","DOI":"10.1142\/S0218195912500045","volume":"22","author":"M de Berg","year":"2012","unstructured":"de Berg, M., Khosravi, A.: Optimal binary space partitions for segments in the plane. Inter. J. Comp. Geom. Appl. 22(3), 187\u2013206 (2012)","journal-title":"Inter. J. Comp. Geom. Appl."},{"key":"20_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"166","DOI":"10.1007\/978-3-030-26176-4_14","volume-title":"Computing and Combinatorics","author":"J-G Dumas","year":"2019","unstructured":"Dumas, J.-G., Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: Interactive physical zero-knowledge proof for Norinori. In: Du, D.-Z., Duan, Z., Tian, C. (eds.) COCOON 2019. LNCS, vol. 11653, pp. 166\u2013177. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26176-4_14"},{"issue":"3","key":"20_CR4","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 for all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691\u2013729 (1991)","journal-title":"J. ACM"},{"key":"20_CR5","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: Sedgewick, R. (ed.) Proceedings of the STOC, pp. 291\u2013304. ACM (1985)","DOI":"10.1145\/22145.22178"},{"issue":"2","key":"20_CR6","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, G.N.: Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles. Theor. Comp. Sys. 44(2), 245\u2013268 (2009)","journal-title":"Theor. Comp. Sys."},{"key":"20_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1007\/978-3-030-34339-2_8","volume-title":"Information Security Practice and Experience","author":"P Lafourcade","year":"2019","unstructured":"Lafourcade, P., Miyahara, D., Mizuki, T., Sasaki, T., Sone, H.: A Physical ZKP for Slitherlink: how to perform physical topology-preserving computation. In: Heng, S.-H., Lopez, J. (eds.) ISPEC 2019. LNCS, vol. 11879, pp. 135\u2013151. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-34339-2_8"},{"key":"20_CR8","doi-asserted-by":"crossref","unstructured":"Nishimura, A., Hayashi, Y., Mizuki, T., Sone, H.: Pile-shifting scramble for card-based protocols. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 101-A(9), 1494\u20131502 (2018)","DOI":"10.1587\/transfun.E101.A.1494"},{"key":"20_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/978-3-030-80049-9_37","volume-title":"Connecting with Computability","author":"L Robert","year":"2021","unstructured":"Robert, L., Miyahara, D., Lafourcade, P., Mizuki, T.: Interactive physical ZKP for\u00a0connectivity: applications to\u00a0nurikabe\u00a0and hitori. In: De Mol, L., Weiermann, A., Manea, F., Fern\u00e1ndez-Duque, D. (eds.) CiE 2021. LNCS, vol. 12813, pp. 373\u2013384. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-80049-9_37"},{"issue":"1","key":"20_CR10","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.: Physical zero-knowledge proof for numberlink puzzle and k vertex-disjoint paths problem. New Gener. Comp. 39(1), 3\u201317 (2021)","journal-title":"New Gener. Comp."},{"key":"20_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"149","DOI":"10.1007\/978-3-030-87993-8_10","volume-title":"Unconventional Computation and Natural Computation","author":"S Ruangwises","year":"2021","unstructured":"Ruangwises, S., Itoh, T.: Physical ZKP for connected spanning subgraph: applications to bridges puzzle and other problems. In: Kostitsyna, I., Orponen, P. (eds.) UCNC 2021. LNCS, vol. 12984, pp. 149\u2013163. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-87993-8_10"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-981-96-1090-7_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,9,6]],"date-time":"2025-09-06T07:06:10Z","timestamp":1757142370000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-981-96-1090-7_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9789819610891","9789819610907"],"references-count":11,"URL":"https:\/\/doi.org\/10.1007\/978-981-96-1090-7_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"5 March 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"COCOON","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Computing and Combinatorics Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Shanghai","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2024","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 August 2024","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 August 2024","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"30","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"cocoon2024","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/anl.sjtu.edu.cn\/cocoon2024\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}