Source-linked AI summary
Card-Based Computation in the Virtual Player Simulation Model
Suthee Ruangwises
TL;DR
Player simulation seeks to let virtual players act correctly in physical card games while keeping their hands secret and preserving the game state. This paper develops generic ranked-card protocols: Play-Minimum for distinct-valued decks and Sorting for hands that may contain equal ranks.
Problem
Generic computational capabilities in the virtual player simulation model, including minimum, maximum, and sorting operations, had not been systematically studied despite their relevance to constructing virtual players.
Method
The paper proposes Play-Minimum, which securely plays a minimum-rank card while preserving the remaining hand, and Sorting, which orders the virtual player's hand without revealing cards.
Results
Play-Minimum applies to decks with distinct card values and can symmetrically play a maximum-rank card, while Sorting also handles multiple cards with the same rank.
Takeaways & Limitations
The protocols provide reusable generic computational primitives for virtual players across a wider variety of physical card games and clarify the model's computational capabilities.
Takeaways & Limitations
The one-to-one correspondence between game cards and physical cards is desirable but not strictly necessary, and the Play-Minimum protocol assumes distinct card values.
Abstract
from arXiv · showhide
Player simulation has recently emerged as a new direction in card-based cryptography, with protocols developed for simulating virtual players in physical card games such as Old Maid, UNO, and President. Unlike conventional card-based secure computation, player simulation imposes additional constraints: the cards represent a persistent game state, the remaining cards in a virtual player's hand must be preserved after each action, and it is desirable to represent each card in the game by a single physical card. In this paper, we study generic card-based computation in the virtual player simulation model. We focus on games whose cards admit a publicly known ranking and propose two fundamental protocols. First, we present the Play-Minimum protocol, which securely selects and plays the minimum-value card from a virtual player's hand when all cards in the deck have distinct values. By symmetry, the protocol can also be used to play the maximum-value card. Second, we present the Sorting protocol, which securely arranges a virtual player's hand in nondecreasing order and remains applicable when multiple cards have the same value. These protocols provide generic computational primitives independent of any particular card game and constitute a step toward understanding the computational capabilities of the virtual player simulation model.
1 Introduction
Player simulation seeks generic, physically verifiable ways to operate on a hidden virtual player’s hand while preserving secrecy and the game state. This paper studies rankable-card settings and introduces Play-Minimum and Sorting as reusable protocols.
- 1.1 Player Simulation Protocol: Physical player simulation must hide the virtual player’s hand while allowing human participants to verify valid actions.The model jointly executes card operations without entrusting private information to one participant.
- 1.1 Player Simulation Protocol: Unlike conventional card-based computation, player simulation should preserve the virtual player’s remaining hand and preferably use one physical card per game card.The one-to-one correspondence requirement limits the direct applicability of standard encodings.
- 1.1 Player Simulation Protocol: Existing protocols target particular games, leaving generic minimum, maximum, and sorting operations largely unexplored.Generic protocols would provide reusable building blocks for virtual players across physical games.
- 1.2 Our Contribution: The paper studies generic computation when cards have a publicly known ranking and develops two protocols that preserve the secrecy of a virtual player’s hand.The setting treats rankability as a public ordering of card values.
- 1.2 Our Contribution: Play-Minimum securely identifies and plays the minimum-rank card without revealing the remaining cards, assuming all deck values are distinct.Reversing the card ordering gives a corresponding maximum-rank operation.
- 1.2 Our Contribution: Sorting arranges the entire hidden hand in nondecreasing rank order and also supports decks containing repeated ranks.Together, the protocols are independent of any particular game’s rules and demonstrate nontrivial hidden-hand computation.
2 Preliminaries
The preliminaries specify the physical-card assumptions and introduce shuffles that hide column order. These operations use the actual game cards alongside auxiliary labels and markers.
- 2 Preliminaries: The protocols use indistinguishable card backs and the actual game cards, supplemented by auxiliary labels and markers.Because auxiliary cards are required, multiple physical copies of the deck may be needed.
- 2 Preliminaries: Cards are assumed to be rankable under a publicly known total order on their values.Play-Minimum additionally requires distinct game-card values, whereas Sorting permits repeated values.
- 2 Preliminaries: A pile-scramble shuffle applies a uniformly random permutation to matrix columns that is unknown to all parties.Its physical implementation can use separate envelopes or bound column piles before random permutation.
- 2 Preliminaries: A pile-shifting shuffle applies a uniformly random cyclic shift to matrix columns unknown to all parties.Participants can implement it with stacked envelopes and secret Hindu cuts, provided at least one cut is random and secret.
3 Play-Minimum Protocol
The Play-Minimum protocol securely plays the minimum-rank card from a virtual player’s hand while preserving the ownership of all remaining cards. It is correct and secure under distinct-card values, with a practical variant that preserves uncertainty about cards remaining in play.
- Protocol construction: The protocol represents player hands and the unplayed deck as face-down columns with ownership labels and markers identifying the virtual player’s cards.A pile-scramble shuffle hides column ownership before card values are revealed.
- Protocol execution: After revealing and sorting first-row card values increasingly, the first revealed α identifies the minimum-value card belonging to the virtual player.The selected card is played, while the remaining columns stay hidden during subsequent processing.
- Protocol execution: Remaining cards are returned to their original owners using the revealed ownership labels, so the virtual player’s unplayed hand is preserved.The protocol removes the selected column and restores the other first-row cards to the indicated players.
- Correctness and security: The protocol reveals only information implied by the public game state or the selected minimum card, and its shuffled arrangements hide ownership information.The first-row set is determined by the public history, while sequential β revelations only establish that smaller cards are not in the virtual player’s hand.
- Practical variant: A practical variant treats the discard pile as an additional hypothetical player, so revealing and sorting the full deck does not disclose which cards remain in play.This preserves uncertainty that human players may otherwise lose when they do not remember previously played cards.
- Extension: Reversing the sorting order yields Play-Maximum, which securely plays the maximum-rank card under the same distinct-value setting.Sorting columns from maximum to minimum makes the first α correspond to the maximum-value card in the virtual player’s hand.
- Correctness and security: The Play-Minimum protocol is correct and secure, assuming all game cards have distinct values.The paper’s security argument is information-theoretic.
4 Sorting Protocol
The Sorting protocol securely arranges a virtual player’s hand in nondecreasing order, including when card values repeat. It uses ownership labels, an α marker, and shuffles to preserve privacy while restoring the sorted hand.
- Protocol purpose: The protocol arranges P1’s hand in nondecreasing order and supports decks with repeated values.Unlike Play-Minimum, it remains applicable when multiple cards have the same value.
- Setup: Ownership labels θ1,…,θn are placed beneath cards, while α marks the boundary needed to restore linear order.The unplayed deck is treated as the hand of hypothetical player Pn.
- Protocol procedure: After revealing and sorting the first row, pile-shifting shuffles and selective removals eliminate columns belonging to other players without exposing hidden card values.Step 9 reveals only a second-row ownership label; removed cards are privately returned to their owners.
- Protocol procedure: The protocol stops with P1’s cards and α, then shifts α to the rightmost position and removes it, leaving P1’s hand sorted.The α column preserves cyclic order during the removals and identifies the boundary of the sorted sequence.
- Security: The Sorting protocol is both correct and secure under the information-theoretic card-based cryptography model.Its correctness follows from sorted columns, preserved cyclic order, and α-based restoration.
- Security: The revealed first-row multiset is public, and the randomized column positions ensure that Step 9 reveals only information determined by public hand sizes.The final second-row revelation also provides no additional information.
5 Future Work
The paper identifies broader protocol development and efficiency improvements as future directions. It also leaves open the general characterization of securely computable functions in the virtual player simulation model.
- Future directions: Future protocols could select the k-th smallest card without sorting the entire hand or count cards with a particular property.These are proposed as additional fundamental operations.
- Future directions: Improving the protocols’ efficiency in additional cards and shuffles is another stated direction.
- Open problem: Characterizing which functions can be securely computed under the virtual player simulation restrictions remains an open problem.