CS Paper Radar

Card-Based Computation in the Virtual Player Simulation Model

Suthee Ruangwises

cs.CR ·submitted 2026-09-02 15:24 UTC · v2
published

Abstract

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.

Comment
This paper has appeared at SecITC 2026

Closest papers

Nearest neighbours by meaning across the whole index.

Riftbound is Turing Complete

cs.CC ·2026-09-27 ·Nathan Dalaklis, Beckett Fields
similarity 0.58
Abstract · 17 Pages, 4 Tables

Riftbound: League of Legends Trading Card Game is a trading card game about capturing and holding locations in a king-of-the-hill style contest. Originally released in China in August of 2025, and later released in the United States in October of 2025, the game has been well received for its depth and complexity. In this paper we demonstrate a facet of this complexity by providing sequences of valid game states which construct Universal Turing machines within the game. Each of these machines are constructed with tournament legal decks at the time of writing and strategies assigned are directed by the game state. We also show that given an appropriate board state the machine may be constructed and the computation may be performed in one game turn.

0.30

Device-Independent Conference Keys from Parity-Extended Games

cs.CR quant-ph ·2026-10-01 ·Suvradip Chakraborty, Ronak Ramachandran, Aniruddha Sen
theory similarity 0.54
Abstract · 32 pages, 4 figures

Device-independent conference key agreement (DI-CKA) lets a group of parties establish a shared secret key from untrusted quantum devices, with security certified by non-locality. Existing DI-CKA protocols are each built around a single Bell inequality, typically a multiparty variant of the CHSH game. DI-QKD protocols, in contrast, have been built from a much richer landscape of non-local games, and it has remained unclear how to carry this landscape over to the conference setting. We introduce $\textit{Parity-$G$ games}$, which extend any two-player game $G$ to $N$ players, for every $N$, provided $G$ has an optimal strategy in which one player measures Pauli observables. The extension preserves the quantum and classical values of $G$, and the security of the resulting $N$-party protocol follows from an analysis of the two-player game alone. Our framework recovers the Parity-CHSH game of Ribeiro, Murta and Wehner (Phys. Rev. A, 2018) as a special case. Applied to the Mermin--Peres Magic Square Game, it yields a new $N$-player pseudo-telepathy game, the $\textit{Parity Magic Square Game}$, which ideal devices win in every round. We use it to construct the $\textit{first}$ DI-CKA protocol based on a pseudo-telepathy game. We prove the protocol secure against coherent attacks. It produces up to two key bits per round, and at low noise its key rate exceeds that of the DI-CKA protocol based on the Parity-CHSH game.

0.61

Repeated-Game Security for Restaking-Based Verifiable Inference

cs.GT cs.CR ·2026-08-10 ·Zhenhang Shang, Yingzhe Yu, Kani Chen
similarity 0.52
Abstract · Length: 29 pages total (15 pages main text, plus appendix and references). Figures: 5. Artifact: https://anonymous.4open.science/r/Repeated-…

Restaking-based protocols enable verifiable LLM inference without the high proving cost of zkML or the hardware trust assumptions of TEEs. Their security is commonly justified by a one-round slashing condition: a rational provider should not cheat when the expected penalty exceeds the cost saving from dishonest inference. This paper shows that this condition can overstate security when inference is supplied repeatedly under the same stake. We model verifiable inference as a discounted repeated game and identify a repeated-game gap caused by proportional slashing: detected deviations reduce future penalty exposure, while cost savings are earned again across queries. We derive the gap in closed form, show that it persists under minimum-stake ejection, and extend it to memoryless bounded-slashing protocols covering deployed designs. We propose a deployable mechanism combining history-dependent challenges, reputation-weighted slashing, and stake vesting. The mechanism restores infinite-horizon subgame-perfect incentive compatibility against stationary mixed-strategy deviations above an explicit discount-factor threshold without per-query cryptographic verification. Evaluation across nine open-weight model pairs from 0.5B to 14B parameters shows that the audit signal has the required concave detectability response. A Stackelberg audit-budget analysis shows that improved signal responsiveness reduces the baseline audit rate by 2.6x at discount factor 0.95. Calibrated to deployed parameters, surveyed protocols pass one-round incentive compatibility but admit repeated-game deviations for discount factors between 0.92 and 0.98, with deviation-profit fractions of 1.5%--8%. Our mechanism reduces deviation profits by 31%--54% while maintaining low-latency economic verification.

0.50

Inner-Learning: From Hand-Coded Beliefs to Declarative Knowledge in Trick-Taking Games

cs.AI ·2026-10-28 ·Stefan Edelkamp
similarity 0.52
Abstract

We present a declarative approach to belief-state modeling in trick-taking card games. Starting from a state-of-the-art Skat player, we automatically extract its hand-coded inference rules into a domain-specific language built on the primitive $\neg\mathsf{holds}(P,C)$, denoting that player $P$ cannot hold any card in set $C$. Round-trip code generation verifies that the extracted rules reproduce the original engine's intended behavior, up to three audited bugs in the original that the declarative engine corrects. We then grow the rule base through symmetric derivation and annotation of an expert strategy document---unifying code, symmetry, and expertise in one representation. We extend the knowledge representation with \emph{cardinality constraints}: at-most-$k$ and at-least-$k$ bounds on the cards a player holds from a named group, expressed in the same declarative language and enforced at world-generation time. Confidence parameters connect symbolic rules to probabilistic belief updates. Self-play evaluation shows the declarative engine measurably improving winning percentage and score over the original hand-coded engine, with the extracted rules, the human-annotated rules, and the cardinality constraints each contributing to the effect.

0.29

Cryptographic Security Is Not Enough: Privacy Gaps in the Renegade Decentralized Dark Pool

cs.CR ·2026-09-22 ·Prerna Arote, Adrian Saiz, Oriol Saguillo, Lucianna Kiffer
similarity 0.52
Abstract · 18 pages, 9 figures

Dark pools are designed to provide pre-trade privacy, liveness, and post-trade confidentiality - concealing order flow before execution and limiting information leakage after. Decentralized dark pools, such as Renegade, aim to replicate these properties without custodial risk, using secure multi-party computation (MPC) and zero-knowledge proofs for private order matching and verifiable settlement. We show that Renegade's cryptographic guarantees do not deliver these dark pool properties in practice. MPC-with-abort ensures correctness but not fairness: a party may learn the match result and abort without penalty, breaking pre-trade privacy. We demonstrate that the protocol's discovery layer further leaks trading intent before MPC even begins, and that sustained probing via selective abort can probabilistically reconstruct counterparty order history, threatening post-trade confidentiality. We also show that the absence of input-consistency checks prior to MPC execution enables a griefing attack using invalid state commitments requiring no real token holdings that continuously locks honest users' wallets and wastes compute, breaking liveness under sustained conditions. We further analyze over 700,000 Renegade transactions on Base and probe the P2P layer, finding that the network is effectively centralized: 88% of traffic routes through a handful of relayers, with only four nodes sustaining the P2P layer. Since relayers hold their users' wallet state in plaintext, this concentration means the system operates as a centralized orderbook in practice - reproducing off-chain the information asymmetry that dark pools are designed to eliminate. Together, our results show that cryptographic privacy does not imply dark pool security: pre-trade privacy, liveness, and post-trade confidentiality each require additional protocol-level guarantees beyond MPC correctness.

0.49

I Prove, Therefore I Am: Spatiotemporal Multi-Party Computation

cs.CR quant-ph ·2026-09-22 ·Ziqing Guo, Fuyuki Kitagawa, Xiao Liang
similarity 0.51
Abstract · 50 pages

Secure multiparty computation (MPC) enables mutually distrustful parties to compute on private digital inputs. We initiate the study of spatiotemporal MPC, extending this paradigm to functionalities whose inputs additionally depend on physical facts such as the parties' locations, times, or trajectories. Such protocols must simultaneously hide spatiotemporal information and ensure its physical consistency: a malicious party should not be able to make the functionality operate on a spatiotemporal input inconsistent with its actual physical state. The main conceptual challenge is to formulate extraction of spatiotemporal information within the simulation-based security framework. We introduce arguments of spatiotemporal knowledge, following the principle "I prove, therefore I am:" rather than defining physical presence directly through a mathematical relation, we define it operationally through the ability to complete a sound spatiotemporal verification protocol. Accordingly, an extractor recovers a spatiotemporal point from a successful prover and certifies its physical validity by using the extracted prover to succeed in an auxiliary spatiotemporal verification protocol. Building on this notion, we define universally composable (UC) security for spatiotemporal MPC, capturing privacy, physical consistency, and composability. We provide constructions achieving this new MPC notion. We first construct UC-secure commit-and-prove of spatiotemporal knowledge: in the CRS model under LWE against quantum provers without pre-shared entanglement, and in the QROM against quantum provers with unbounded pre-shared entanglement. Using these protocols, we obtain UC-secure spatiotemporal MPC from semi-honest post-quantum MPC. We also extend our framework to support quantum functionalities with classical spatiotemporal input.

0.31

Cutting a Cake For Human Consumption: An Elementary $n$-agent Cake Cutting Protocol

cs.GT ·2026-10-21 ·Alexandros Psomas
similarity 0.51
Abstract

We give a bounded envy-free cake-cutting protocol for any number $n$ of agents in the Robertson--Webb model, with a short, self-contained, and elementary correctness proof. The protocol uses $2^{O(n \log n)}$ queries. Most ingredients are already known and well understood in the fair division literature; our main contribution is a simpler organization of these ideas into a protocol whose complete description and proof fit in a few pages.

0.38

Antichains for Concurrent Parameterized Games

cs.LO ·2026-10-08 ·Nathalie Bertrand, Patricia Bouyer, Gaëtan Staquet
published similarity 0.51
Abstract · In Proceedings GandALF 2026, arXiv:2610.08898. A full version of this paper, containing all proofs, appears at arXiv:2505.13460

Concurrent parameterized games involve a fixed yet arbitrary number of players. They are described by finite arenas in which the edges are labeled with languages that describe the possible move combinations leading from one vertex to another (n players yield a word of length n). Previous work showed that, when edge labels are regular languages, one can decide whether a distinguished player, called Eve, has a strategy to ensure a reachability objective, against any strategy profile of her arbitrarily many opponents. This decision problem is known to be PSPACE-complete. A basic ingredient in the PSPACE-membership proof is the reduction to the exponential-size knowledge game, a 2-player game that reflects the knowledge Eve has on the number of opponents. In this paper, we provide a symbolic approach, based on antichains, to compute Eve's winning region in the knowledge game. In words, it gives the minimal knowledge Eve needs at every vertex to win the concurrent parameterized reachability game. More precisely, we propose two fixed-point algorithms that compute, as an antichain, the maximal elements of the winning region for Eve in the knowledge game. We implemented these two algorithms in C++, as well as the one initially proposed, and report on their relative performances on various benchmarks.

0.46