2026-07-24T00:57:12Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22897 2025-10-02T13:36:50Z ddc:004 open_access

Card-Based Protocols Imply PSM Protocols Shinagawa, Kazumasa Nuida, Koji Card-based cryptography private simultaneous messages Card-based cryptography is the art of cryptography using a deck of physical cards. While this area is known as a research area of recreational cryptography and is recently paid attention in educational purposes, there is no systematic study of the relationship between card-based cryptography and the other "conventional" cryptography. This paper establishes the first generic conversion from card-based protocols to private simultaneous messages (PSM) protocols, a special kind of secure multiparty computation. Our compiler supports "simple" card-based protocols, which is a natural subclass of finite-runtime protocols. The communication complexity of the resulting PSM protocol depends on how many cards are opened in total in all possible branches of the original card-based protocol. This result shows theoretical importance of such "opening complexity" of card-based protocols, which had not been focused in this area. As a consequence, lower bounds for PSM protocols imply those for simple card-based protocols. In particular, if there exists no PSM protocol with subexponential communication complexity for a function f, then there exists no simple card-based protocol with subexponential opening complexity for the same f. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Kazumasa Shinagawa and Koji Nuida 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.72 urn:nbn:de:0030-drops-228975 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.72 eng https://creativecommons.org/licenses/by/4.0/legalcode