Search papers, labs, and topics across Lattice.
This paper formalizes the complexity of shuffle operations used in card-based cryptography, categorizing them into a hierarchy based on implementation difficulty. It establishes separation results, proving that certain shuffle operations cannot be implemented using simpler shuffle primitives. The authors then introduce a new complexity measure for evaluating card-based protocols based on this shuffle hierarchy.
Not all card shuffles are created equal: this work exposes a provable hierarchy of shuffle complexities in card-based cryptography, revealing fundamental limits on what can be achieved with simpler shuffling primitives.
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.
