A Complexity Hierarchy of Shuffles in Card-Based Protocols

• URL: http://arxiv.org/abs/2603.18608v1
• Date: Thu, 19 Mar 2026 08:27:02 GMT
• Title: A Complexity Hierarchy of Shuffles in Card-Based Protocols
• Abstract summary: We classify shuffle operations into several levels according to their implementation complexity.<n>We propose a new complexity measure for evaluating card-based protocols based on this hierarchy.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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.

Related papers

• Which Pieces Does Unigram Tokenization Really Need? [6.722891561991933]
  The Unigram tokenization algorithm offers a probabilistic alternative to the greedy adapters of Byte-Pair.<n>We bridge this gap between theory and practice by providing a clear guide to implementation and parameter choices.
  arXiv  Detail & Related papers  (2025-12-14T11:13:49Z)
• Single-Shuffle Full-Open Card-Based Protocols for Any Function [4.039245878626346]
  A textitsingle-shuffle full-open protocol is a minimal model of card-based secure computation.<n>We prove for the first time that every function admits a single-shuffle full-open protocol.
  arXiv  Detail & Related papers  (2025-10-20T08:52:23Z)
• Single-pass Adaptive Image Tokenization for Minimum Program Search [75.59409288259151]
  We propose a single-pass adaptive tokenizer, KARL, which predicts the appropriate number of tokens for an image in a single forward pass.<n> KARL matches the performance of recent adaptive tokenizers while operating in a single pass.
  arXiv  Detail & Related papers  (2025-07-10T17:59:53Z)
• EpiCoder: Encompassing Diversity and Complexity in Code Generation [66.43738008739555]
  Existing methods for code generation use code snippets as seed data.<n>We introduce a novel feature tree-based synthesis framework, which revolves around hierarchical code features.<n>Our framework provides precise control over the complexity of the generated code, enabling functionalities that range from function-level operations to multi-file scenarios.
  arXiv  Detail & Related papers  (2025-01-08T18:58:15Z)
• Efficient Fault-Tolerant Quantum Protocol for Differential Privacy in the Shuffle Model [2.0794380287086214]
  We present a quantum protocol which implicitly implements a random shuffle to realize differential privacy in the shuffle model. The shuffle model amplifies outcomes achievable from data contributors. Examples include implementing the shuffle via mix-networks, or shuffling via a trusted third-party. We propose a quantum version of the protocol using entanglement of quantum states and show that the shuffle can be implemented without these extra requirements.
  arXiv  Detail & Related papers  (2024-09-06T04:53:19Z)
• Card-Based Overwriting Protocol for Equality Function and Applications [0.34952465649465553]
  Research in the area of secure multi-party computation with an unconventional method of using a physical deck of playing cards began in 1989. We propose a card-based protocol called the overwriting protocol that can securely compute the $k$-candidate $n$-variable equality function.
  arXiv  Detail & Related papers  (2024-02-26T04:13:51Z)
• Minimum Description Length Clustering to Measure Meaningful Image Complexity [65.268245109828]
  We present a new image complexity metric through hierarchical clustering of patches. We use the minimum description length principle to determine the number of clusters and designate certain points as outliers and, hence, correctly assign white noise a low score.
  arXiv  Detail & Related papers  (2023-06-26T15:37:04Z)
• A Secure Multiparty Quantum Least Common Multiple Computation Protocol [1.4049484216292827]
  We present a secure multiparty computation protocol for least common multiple (LCM) based on Shor's quantum period-finding algorithm (QPA) Since QPA is a probabilistic algorithm, we also propose a one-vote-down vote protocol based on the existing secure multi-party quantum summation protocol.
  arXiv  Detail & Related papers  (2022-10-15T02:27:18Z)
• Beyond the Prototype: Divide-and-conquer Proxies for Few-shot Segmentation [63.910211095033596]
  Few-shot segmentation aims to segment unseen-class objects given only a handful of densely labeled samples. We propose a simple yet versatile framework in the spirit of divide-and-conquer. Our proposed approach, named divide-and-conquer proxies (DCP), allows for the development of appropriate and reliable information.
  arXiv  Detail & Related papers  (2022-04-21T06:21:14Z)
• Few-shot Sequence Learning with Transformers [79.87875859408955]
  Few-shot algorithms aim at learning new tasks provided only a handful of training examples. In this work we investigate few-shot learning in the setting where the data points are sequences of tokens. We propose an efficient learning algorithm based on Transformers.
  arXiv  Detail & Related papers  (2020-12-17T12:30:38Z)
• Entanglement purification by counting and locating errors with entangling measurements [62.997667081978825]
  We consider entanglement purification protocols for multiple copies of qubit states. We use high-dimensional auxiliary entangled systems to learn about number and positions of errors in the noisy ensemble.
  arXiv  Detail & Related papers  (2020-11-13T19:02:33Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.