A Complexity Hierarchy of Shuffles in Card-Based Protocols
This work addresses the need for a systematic evaluation of shuffle complexity in card-based protocols, which is incremental as it builds on existing classifications.
The paper tackles the problem of classifying shuffle operations in card-based cryptography by establishing a complexity hierarchy, proving separation results between levels, and proposing a new complexity measure for evaluating protocols.
Card-based cryptography uses physical playing cards to construct protocols for secure multi-party computation. Existing card-based protocols employ various types of shuffles, some of which are easy to implement in practice while others are considerably more complex. In this paper, we classify shuffle operations into several levels according to their implementation complexity. We motivate this hierarchy from both practical and theoretical perspectives, and prove separation results between several levels by showing that certain shuffles cannot be realized using only operations from lower levels. Finally, we propose a new complexity measure for evaluating card-based protocols based on this hierarchy.