{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T10:16:55Z","timestamp":1769854615838,"version":"3.49.0"},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T00:00:00Z","timestamp":1740787200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T00:00:00Z","timestamp":1740787200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"JSPS KAKENHI","award":["JP21K17702, JP23H00479, JP23H00479"],"award-info":[{"award-number":["JP21K17702, JP23H00479, JP23H00479"]}]},{"name":"JST CREST","award":["JPMJCR22M1"],"award-info":[{"award-number":["JPMJCR22M1"]}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2025,3]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Old Maid is a popular card game. While typically played with three or more players, it is less enjoyable with only two people. To address this, we propose a protocol to create a virtual player, Carol, by making use of card-based cryptography when only two people, Alice and Bob, are available to play Old Maid. Specifically, we design a card-based protocol to remove any pair of cards having the same number in Carol\u2019s hand (namely, the virtual player\u2019s hand) without leaking any information about Carol\u2019s hand (more than necessary); our protocol uses additional cards aside from playing cards that are used in Old Maid. Using our protocol, without any third human player, Alice and Bob can have fun with Old Maid!<\/jats:p>","DOI":"10.1007\/s00224-024-10203-w","type":"journal-article","created":{"date-parts":[[2025,3,1]],"date-time":"2025-03-01T02:03:48Z","timestamp":1740794628000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["How to Play Old Maid with Virtual Players"],"prefix":"10.1007","volume":"69","author":[{"given":"Kazumasa","family":"Shinagawa","sequence":"first","affiliation":[]},{"given":"Daiki","family":"Miyahara","sequence":"additional","affiliation":[]},{"given":"Takaaki","family":"Mizuki","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,3,1]]},"reference":[{"key":"10203_CR1","doi-asserted-by":"publisher","unstructured":"Boer, BD.: More efficient match-making and satisfiability the five card trick. In: Quisquater JJ, Vandewalle J (eds) EUROCRYPT 1989, LNCS, vol 434. Springer, Heidelberg, pp. 208\u2013217, (1990) https:\/\/doi.org\/10.1007\/3-540-46885-4_23","DOI":"10.1007\/3-540-46885-4_23"},{"key":"10203_CR2","doi-asserted-by":"publisher","unstructured":"Cr\u00e9peau, C., Kilian, J.: Discreet solitary games. In: Stinson DR (ed) Advances in Cryptology\u2014CRYPTO\u2019 93, LNCS, vol 773. Springer, Berlin, Heidelberg, pp. 319\u2013330, (1994) https:\/\/doi.org\/10.1007\/3-540-48329-2_27","DOI":"10.1007\/3-540-48329-2_27"},{"key":"10203_CR3","doi-asserted-by":"publisher","unstructured":"Gradwohl, R., Naor, M., Pinkas, B., et\u00a0al.: Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles. In: Crescenzi P, Prencipe G, Pucci G (eds) Fun with Algorithms, LNCS, vol. 4475. Springer, Berlin, Heidelberg, pp. 166\u2013182, (2007) https:\/\/doi.org\/10.1007\/978-3-540-72914-3_16","DOI":"10.1007\/978-3-540-72914-3_16"},{"key":"10203_CR4","doi-asserted-by":"publisher","unstructured":"Haga, R., Hayashi, Y., Miyahara, D., et\u00a0al.: Card-minimal protocols for three-input functions with standard playing cards. In: Batina L, Daemen J (eds) AFRICACRYPT 2022, LNCS, vol. 13503. Springer, Cham, pp. 448\u2013468, (2022) https:\/\/doi.org\/10.1007\/978-3-031-17433-9_19","DOI":"10.1007\/978-3-031-17433-9_19"},{"key":"10203_CR5","doi-asserted-by":"publisher","unstructured":"Hand, S., Koch, A., Lafourcade, P., et\u00a0al. Check alternating patterns: A physical zero-knowledge proof for Moon-or-Sun. In: Shikata J, Kuzuno H (eds). Advances in Information and Computer Security, LNCS, vol. 14128. Springer, Cham, pp. 255\u2013272, (2023) https:\/\/doi.org\/10.1007\/978-3-031-41326-1_14","DOI":"10.1007\/978-3-031-41326-1_14"},{"key":"10203_CR6","doi-asserted-by":"publisher","unstructured":"Hashimoto, Y., Nuida, K., Shinagawa, K., et\u00a0al.: Toward finite-runtime card-based protocol for generating a hidden random permutation without fixed points. IEICE Trans. Fundam. E101. A(9), 1503\u20131511 (2018a) https:\/\/doi.org\/10.1587\/transfun.E101.A.1503","DOI":"10.1587\/transfun.E101.A.1503"},{"key":"10203_CR7","doi-asserted-by":"publisher","unstructured":"Hashimoto, Y., Shinagawa, K., Nuida, K., et\u00a0al.: Secure grouping protocol using a deck of cards. IEICE Trans. Fundam. E101. A(9), 1512\u20131524 (2018b) https:\/\/doi.org\/10.1587\/transfun.E101.A.1512","DOI":"10.1587\/transfun.E101.A.1512"},{"key":"10203_CR8","doi-asserted-by":"publisher","unstructured":"Hatsugai, K., Asano, K., Abe, Y.: A physical zero-knowledge proof for Sumplete, a puzzle generated by ChatGPT. In: Wu W, Tong G (eds) Computing and Combinatorics, LNCS, vol. 14422. Springer, Cham, pp. 398\u2013410, (2024) https:\/\/doi.org\/10.1007\/978-3-031-49190-0_29","DOI":"10.1007\/978-3-031-49190-0_29"},{"key":"10203_CR9","doi-asserted-by":"publisher","unstructured":"Ibaraki, T., Manabe, Y.: A more efficient card-based protocol for generating a random permutation without fixed points. In: Mathematics and Computers in Sciences and in Industry (MCSI), pp. 252\u2013257, (2016) https:\/\/doi.org\/10.1109\/MCSI.2016.054","DOI":"10.1109\/MCSI.2016.054"},{"key":"10203_CR10","doi-asserted-by":"publisher","unstructured":"Ishikawa, R., Chida, E., Mizuki, T.: Efficient card-based protocols for generating a hidden random permutation without fixed points. In: Calude CS, Dinneen MJ (eds) Unconventional Computation and Natural Computation, LNCS, vol. 9252. Springer, Cham, pp. 215\u2013226, (2015) https:\/\/doi.org\/10.1007\/978-3-319-21819-9_16","DOI":"10.1007\/978-3-319-21819-9_16"},{"key":"10203_CR11","unstructured":"Kazumasa, S., Daiki, M., Takaaki, M.: How to play old maid with virtual players. In: Frontiers of Algorithmic Wisdom - International Joint Conference, IJTCS-FAW 2024. Springer, to appear (2024)"},{"key":"10203_CR12","doi-asserted-by":"publisher","unstructured":"Koch, A., Schrempp, M., Kirsten, M.: Card-based cryptography meets formal verification. In: Galbraith SD, Moriai S (eds) Advances in Cryptology\u2013ASIACRYPT 2019, LNCS, vol. 11921. Springer, Cham, pp. 488\u2013517, (2019) https:\/\/doi.org\/10.1007\/978-3-030-34578-5_18","DOI":"10.1007\/978-3-030-34578-5_18"},{"key":"10203_CR13","doi-asserted-by":"publisher","unstructured":"Koyama, H., Miyahara, D., Mizuki, T., et\u00a0al.: A secure three-input AND protocol with a standard deck of minimal cards. In: Santhanam R, Musatov D (eds). Computer Science \u2013 Theory and Applications, LNCS, vol. 12730. Springer, Cham, pp. 242\u2013256, (2021) https:\/\/doi.org\/10.1007\/978-3-030-79416-3_14","DOI":"10.1007\/978-3-030-79416-3_14"},{"key":"10203_CR14","doi-asserted-by":"publisher","unstructured":"Manabe, Y., Ono, H.: Card-based cryptographic protocols with a standard deck of cards using private operations. In: Cerone A, \u00d6lveczky PC (eds) Theoretical Aspects of Computing \u2013 ICTAC 2021, LNCS, vol. 12819. Springer, Cham, pp. 256\u2013274, (2021) https:\/\/doi.org\/10.1007\/978-3-030-85315-0_15","DOI":"10.1007\/978-3-030-85315-0_15"},{"key":"10203_CR15","doi-asserted-by":"publisher","unstructured":"Mizuki, T.: Efficient and secure multiparty computations using a standard deck of playing cards. In: Foresti S, Persiano G (eds). Cryptology and Network Security, LNCS, vol. 10052. Springer, Cham, pp. 484\u2013499, (2016) https:\/\/doi.org\/10.1007\/978-3-319-48965-0_29","DOI":"10.1007\/978-3-319-48965-0_29"},{"key":"10203_CR16","doi-asserted-by":"publisher","unstructured":"Mizuki, T., Shizuya, H.: A formalization of card-based cryptographic protocols via abstract machine. Int. J. Inf. Secur. 13(1), 15\u201323 (2014). https:\/\/doi.org\/10.1007\/s10207-013-0219-4","DOI":"10.1007\/s10207-013-0219-4"},{"key":"10203_CR17","doi-asserted-by":"publisher","unstructured":"Mizuki, T., Sone, H.: Six-card secure AND and four-card secure XOR. In: Deng X, Hopcroft JE, Xue J (eds). Frontiers in Algorithmics, LNCS, vol. 5598. Springer, Berlin, Heidelberg, pp. 358\u2013369, (2009) https:\/\/doi.org\/10.1007\/978-3-642-02270-8_36","DOI":"10.1007\/978-3-642-02270-8_36"},{"key":"10203_CR18","doi-asserted-by":"publisher","unstructured":"Murata, S., Miyahara, D., Mizuki, T., et\u00a0al.: Efficient generation of a card-based uniformly distributed random derangement. In: Uehara R, Hong SH, Nandy SC (eds). WALCOM: Algorithms and Computation, LNCS, vol. 12635. Springer, Cham, pp. 78\u201389, (2021) https:\/\/doi.org\/10.1007\/978-3-030-68211-8_7","DOI":"10.1007\/978-3-030-68211-8_7"},{"issue":"1\u20132","key":"10203_CR19","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/S0304-3975(97)00107-2","volume":"191","author":"V Niemi","year":"1998","unstructured":"Niemi, V., Renvall, A.: Secure multiparty computations without computers. Theor. Comput. Sci. 191(1\u20132), 173\u2013183 (1998). https:\/\/doi.org\/10.1016\/S0304-3975(97)00107-2","journal-title":"Theor. Comput. Sci."},{"key":"10203_CR20","doi-asserted-by":"publisher","unstructured":"Robert, L., Miyahara, D., Lafourcade, P., et al.: Physical ZKP protocols for Nurimisaki and Kurodoko. Theor. Comput. Sci. 972, 114071 (2023). https:\/\/doi.org\/10.1016\/j.tcs.2023.114071","DOI":"10.1016\/j.tcs.2023.114071"},{"key":"10203_CR21","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1007\/s00354-021-00146-y","volume":"40","author":"S Ruangwises","year":"2022","unstructured":"Ruangwises, S.: Two standard decks of playing cards are sufficient for a ZKP for Sudoku. New Gener. Comput. 40, 49\u201365 (2022). https:\/\/doi.org\/10.1007\/s00354-021-00146-y","journal-title":"New Gener. Comput."},{"key":"10203_CR22","doi-asserted-by":"publisher","unstructured":"Ruangwises, S.: Physical zero-knowledge proof for ball sort puzzle. In: Vedova GD, Dundua B, Lempp S, et\u00a0al (eds). Unity of Logic and Computation, LNCS, vol. 13967. Springer, Cham, pp. 246\u2013257, (2023a) https:\/\/doi.org\/10.1007\/978-3-031-36978-0_20","DOI":"10.1007\/978-3-031-36978-0_20"},{"key":"10203_CR23","doi-asserted-by":"publisher","unstructured":"Ruangwises, S.: Physical zero-knowledge proofs for Five Cells. In: Aly A, Tibouchi M (eds) Progress in Cryptology \u2013 LATINCRYPT 2023, LNCS, vol. 14168. Springer, Cham, pp. 315\u2013330, (2023b) https:\/\/doi.org\/10.1007\/978-3-031-44469-2_16","DOI":"10.1007\/978-3-031-44469-2_16"},{"key":"10203_CR24","doi-asserted-by":"publisher","unstructured":"Ruangwises, S.: Physically verifying the first nonzero term in a sequence: Physical ZKPs for ABC end view and Goishi Hiroi. In: Li M, Sun X, Wu X (eds) Frontiers of Algorithmics, LNCS, vol. 13933. Springer, Cham, pp. 171\u2013183, (2023c) https:\/\/doi.org\/10.1007\/978-3-031-39344-0_13","DOI":"10.1007\/978-3-031-39344-0_13"},{"key":"10203_CR25","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., et al.: Efficient card-based zero-knowledge proof for Sudoku. Theor. Comput. Sci. 839, 135\u2013142 (2020). https:\/\/doi.org\/10.1016\/j.tcs.2020.05.036","journal-title":"Theor. Comput. Sci."},{"key":"10203_CR26","doi-asserted-by":"publisher","unstructured":"Shinoda, Y., Miyahara, D., Shinagawa, K., et\u00a0al.: Card-based covert lottery. In: Maimut D, Oprina AG, Sauveron D (eds). Innovative Security Solutions for Information Technology and Communications, LNCS, vol. 12596. Springer, Cham, pp. 257\u2013270, (2021) https:\/\/doi.org\/10.1007\/978-3-030-69255-1_17","DOI":"10.1007\/978-3-030-69255-1_17"},{"key":"10203_CR27","doi-asserted-by":"publisher","unstructured":"Tanaka, K., Mizuki, T.: Two UNO decks efficiently perform zero-knowledge proof for Sudoku. In: Fernau H, Jansen K (eds). Fundamentals of Computation Theory, LNCS, vol. 14292. Springer, Cham, pp. 406\u2013420, (2023) https:\/\/doi.org\/10.1007\/978-3-031-43587-4_29","DOI":"10.1007\/978-3-031-43587-4_29"}],"updated-by":[{"DOI":"10.1007\/s00224-025-10218-x","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2025,4,2]],"date-time":"2025-04-02T00:00:00Z","timestamp":1743552000000}}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10203-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00224-024-10203-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-024-10203-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,4,8]],"date-time":"2025-04-08T17:16:57Z","timestamp":1744132617000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00224-024-10203-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,3]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2025,3]]}},"alternative-id":["10203"],"URL":"https:\/\/doi.org\/10.1007\/s00224-024-10203-w","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,3]]},"assertion":[{"value":"18 November 2024","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 March 2025","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 March 2025","order":3,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Update","order":4,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The original version of this paper was updated to remove the \u201cUncorrected Proof\u201d watermark in the PDF.","order":5,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 April 2025","order":6,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":7,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"A Correction to this paper has been published:","order":8,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"https:\/\/doi.org\/10.1007\/s00224-025-10218-x","URL":"https:\/\/doi.org\/10.1007\/s00224-025-10218-x","order":9,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}],"article-number":"13"}}