Paper 2026/2704

Card-Based Protocols with Mixed Encoding: Computable Functions and the Minimum Number of Cards

Abstract

Card-based cryptography performs secure computation with physical cards, where a bit is usually encoded by two cards but can also be encoded by a single card. We study mixed encoding, in which one player gives a single-card commitment and the other a two-card commitment, for perfectly secure protocols with finite runtime and public actions. Mizuki (Theoretical Computer Science, vol.~622, 2016) proposed an AND protocol with mixed encoding as a building block for the conjunction of many variables. To give a single-card commitment, a player chooses one of two cards of different types and must keep the other card hidden. We call this card a frozen card and include it in the number of cards. We show that a secure protocol in committed format never turns over a single-card input, and use this to determine the functions that can be computed when all inputs are single-card commitments and to characterize those that can be computed with mixed encoding, which include AND but not XOR. We prove that Mizuki's five-card protocol is card-minimal. No AND protocol with mixed encoding uses four cards, including the frozen card, even with arbitrary shuffles and a non-committed output. For formal verification, we express the existence of a protocol as a quantified Boolean formula (QBF) in which security is a quantifier alternation, and confirm this lower bound with QBF solvers for a class of protocols. We discuss the number and type of shuffles, and analyze Mizuki's protocol under injection attacks that change only the input.