Paper 2026/2960

Impossibility Results for Single-Cut Full-Open Card-Based Protocols with Any Number of Cards

Koji Nuida, Kyushu University, National Institute of Advanced Industrial Science and Technology
Kazumasa Shinagawa, University of Tsukuba, Kyushu University, National Institute of Advanced Industrial Science and Technology
Yasuhide Numata, Hokkaido University, Kyushu University
Abstract

Card-based protocols are cryptographic protocols using a deck of physical cards instead of electronic computers, where information is encoded into a sequence of face-down cards and decoded by opening the cards, and random operations are realized by shuffles of cards. In this research area, there are known impossibility results for protocol construction, but most of the existing results (except for one result for a specific function under a non-standard encoding rule) are conditional on the number of cards used in a protocol, i.e., just giving lower bounds for the number of cards. In contrast, in this paper we give impossibility results, unconditional on the number of cards, for some kind of protocols computing wide classes of functions. Technically, our result is given by deepening a recently explored connection between card-based protocols and combinatorics on words. Specifically, we consider card-based protocols with the following two properties: (1) just a single random cut is used as shuffles; (2) an opening operation is used just once, where all cards are opened at the same time. It has been known that an arbitrary function can be computed by slightly relaxing (1) to "a single shuffle" (not necessarily a random cut) or (2) to "a part of cards are opened". As opposed to them, in this paper we prove that for protocols satisfying both (1) and (2), for the case of symmetric Boolean functions and Boolean functions without redundant variables, the currently known protocols are essentially all of the possible cases; for any other function (in the sense of NPN non-equivalence), such a protocol is shown to be impossible regardless of the number of cards. We also partially extend the impossibility result to functions with non-binary outputs.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Preprint.
Keywords
Card-based cryptographySingle-cut full-open protocolsImpossibility
Contact author(s)
nuida @ imi kyushu-u ac jp
History
2026-11-22: approved
2026-11-20: received
See all versions
Short URL
https://ia.cr/2026/2960
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2026/2960,
      author = {Koji Nuida and Kazumasa Shinagawa and Yasuhide Numata},
      title = {Impossibility Results for Single-Cut Full-Open Card-Based Protocols with Any Number of Cards},
      howpublished = {Cryptology {ePrint} Archive, Paper 2026/2960},
      year = {2026},
      url = {https://eprint.iacr.org/2026/2960}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.