Paper 2026/2960
Impossibility Results for Single-Cut Full-Open Card-Based Protocols with Any Number of Cards
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
-
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}
}