pith. sign in

arxiv: 2603.18608 · v2 · pith:V7GK2P7Fnew · submitted 2026-03-19 · 💻 cs.CR

A Complexity Hierarchy of Shuffles in Card-Based Protocols

Tomoki Ono , Suthee Ruangwises This is my paper

Pith reviewed 2026-05-15 08:58 UTC · model grok-4.3

classification 💻 cs.CR
keywords card-based cryptographyshuffle operationscomplexity hierarchysecure multi-party computationphysical protocolsimplementation complexity
0
0 comments X

The pith

Shuffles in card-based cryptography form a complexity hierarchy with provable separations between levels.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper classifies shuffle operations used in card-based cryptography into several levels according to how difficult they are to perform in practice. It proves separation results showing that certain shuffles cannot be realized using only operations from lower levels in the hierarchy. The classification draws from both the practical challenges of physical execution and theoretical requirements for secure protocols. The authors then propose using the highest level of shuffle required as a new measure for the overall complexity of a card-based protocol.

Core claim

Shuffle operations are partitioned into levels ordered by implementation complexity, with formal proofs that some shuffles at higher levels cannot be achieved by any combination of operations from strictly lower levels, yielding a new complexity measure for protocols based on the highest level employed.

What carries the argument

A multi-level hierarchy of shuffle operations ordered by physical implementation complexity, with separation proofs establishing that higher levels are irreducible to lower ones.

If this is right

  • Card-based protocols can be ranked and compared by the highest shuffle level they require.
  • Protocol designers gain an incentive to minimize the maximum level of shuffle used.
  • Existing protocols may need re-assessment based on the shuffle levels they actually employ.
  • New protocols can be constructed to rely exclusively on lower levels when security permits.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same hierarchy idea could be applied to classify other physical operations in card-based systems.
  • Standardizing only the lower-level shuffles might make many protocols easier to deploy in practice.
  • Similar ordering approaches could classify complexity in other physical or manual cryptographic methods.

Load-bearing premise

That the practical difficulty of performing different shuffles can be ordered into strict levels that remain separated no matter how the physical cards are handled or executed.

What would settle it

A concrete physical procedure that achieves a higher-level shuffle using only sequences of lower-level shuffles would falsify the separation.

Figures

Figures reproduced from arXiv: 2603.18608 by Suthee Ruangwises, Tomoki Ono.

Figure 2
Figure 2. Figure 2: Small envelopes inside a large [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes a complexity hierarchy for shuffle operations in card-based cryptographic protocols. It classifies shuffles into several levels according to implementation complexity, motivates the hierarchy from practical and theoretical perspectives, proves separation results by showing that certain shuffles cannot be realized using only lower-level operations, and proposes a new complexity measure for evaluating card-based protocols.

Significance. If the separations hold, the hierarchy offers a structured framework for assessing the practicality of card-based protocols, which could inform the selection of shuffles in secure multi-party computation designs. The dual practical-theoretical motivation and the introduction of a new measure are positive contributions, though their impact depends on the robustness of the underlying formal model.

major comments (2)
  1. [Hierarchy definition and separation proofs] The formal model of primitive operations defining each level (introduced in the section on the hierarchy) is load-bearing for the separation claims, yet the manuscript provides no independent verification that the listed primitives exhaust all physically realizable shuffles; additional human-induced micro-moves could allow a level-k shuffle to be realized at level k-1.
  2. [Separation results] The separation results rest on treating shuffles as exact functions under a closed set of moves; the proofs do not address whether non-uniform randomness or partial-visibility effects from physical execution violate the model assumptions and collapse the claimed strict separations.
minor comments (2)
  1. The new complexity measure is defined but no concrete computation is shown for any existing card-based protocol, leaving its utility unclear.
  2. Notation for shuffle types and levels would benefit from a summary table or running example to improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the constructive comments, which help clarify the scope and assumptions of our formal model. We address each major point below and will make targeted revisions to improve the manuscript.

read point-by-point responses

  1. Referee: [Hierarchy definition and separation proofs] The formal model of primitive operations defining each level (introduced in the section on the hierarchy) is load-bearing for the separation claims, yet the manuscript provides no independent verification that the listed primitives exhaust all physically realizable shuffles; additional human-induced micro-moves could allow a level-k shuffle to be realized at level k-1.

    Authors: The hierarchy is defined relative to a specific formal model of primitive operations chosen to reflect standard physical implementations described in the card-based cryptography literature. We do not claim these primitives form an exhaustive list of all conceivable physical actions; additional micro-moves could indeed allow certain simulations. The separation theorems are proved strictly inside this model. We will revise the manuscript to state the model's scope explicitly and add a paragraph discussing its limitations with respect to arbitrary physical realizations. revision: partial

  2. Referee: [Separation results] The separation results rest on treating shuffles as exact functions under a closed set of moves; the proofs do not address whether non-uniform randomness or partial-visibility effects from physical execution violate the model assumptions and collapse the claimed strict separations.

    Authors: All separation proofs are carried out under the model's assumptions of exact functions, uniform randomness, and ideal (full-visibility) physical execution. Real-world deviations such as non-uniform randomness or partial visibility are outside the model we analyze. We will add a dedicated subsection clarifying these assumptions and noting that the strict separations are guaranteed only within the idealized model standard in the field; we do not claim robustness against arbitrary physical noise. revision: partial

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 1 invented entities

The work rests on the domain assumption that shuffles possess distinguishable implementation complexities that admit a strict hierarchy; no free parameters or new physical entities are introduced.

axioms (1)
  • domain assumption Shuffle operations possess distinguishable degrees of implementation complexity that can be ordered into discrete levels.
    This assumption underpins the entire classification and is motivated from practical considerations in the abstract.
invented entities (1)
  • Shuffle complexity hierarchy no independent evidence
    purpose: To classify existing shuffles and define a new measure for protocol complexity
    Newly introduced construct that organizes prior shuffle types; no independent evidence outside the paper is provided.

pith-pipeline@v0.9.0 · 5380 in / 1177 out tokens · 47257 ms · 2026-05-15T08:58:56.242936+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Y. Abe, Y. Hayashi, T. Mizuki and H. Sone. Five-Card AND Computations in Com- mitted Format Using Only Uniform Cyclic Shuffles.New Generation Computing, 39(1): 97–114 (2021)

    work page 2021

  2. [2]

    Bultel, J

    X. Bultel, J. Dreier, J.-G. Dumas, P. Lafourcade, D. Miyahara, T. Mizuki, A. Nagao, T. Sasaki, K. Shinagawa and H. Sone. Physical Zero-Knowledge Proof for Makaro. In Proceedings of the 20th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), pp. 111–125 (2018)

    work page 2018

  3. [3]

    den Boer

    B. den Boer. More Efficient Match-Making and Satisfiability: the Five Card Trick. In Proceedings of the Workshop on the Theory and Application of of Cryptographic Tech- niques (EUROCRYPT ’89), pp. 208–217 (1990)

    work page 1990

  4. [4]

    Gradwohl, M

    R. Gradwohl, M. Naor, B. Pinkas and G.N. Rothblum. Cryptographic and Physical Zero-Knowledge Proof Systems for Solutions of Sudoku Puzzles.Theory of Computing Systems, 44(2): 245–268 (2009)

    work page 2009

  5. [5]

    Ishikawa, E

    R. Ishikawa, E. Chida and T. Mizuki. Efficient Card-Based Protocols for Generating a Hidden Random Permutation Without Fixed Points. InProceedings of the 14th Interna- tional Conference on Unconventional Computation and Natural Computation (UCNC), pp. 215–226 (2015)

    work page 2015

  6. [6]

    Koch and S

    A. Koch and S. Walzer. Foundations for Actively Secure Card-Based Cryptography. In Proceedings of the 10th International Conference on Fun with Algorithms (FUN), pp. 17:1–17:23 (2020)

    work page 2020

  7. [7]

    A. Koch, S. Walzer and K. H¨ artel. Card-Based Crypto-graphic Protocols Using a Mini- mal Number of Cards. InProceedings of the 21st International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), pp. 783–807 (2015)

    work page 2015

  8. [8]

    Miyahara, I

    D. Miyahara, I. Ueda, Y. Hayashi, T. Mizuki and H. Sone. Evaluating card-based pro- tocols in terms of execution time.International Journal of Information Security, 20(5): 729–740 (2021)

    work page 2021

  9. [9]

    Miyamoto and K

    K. Miyamoto and K. Shinagawa. Graph Automorphism Shuffles from Pile-Scramble Shuffles. New Generation Computing, 40(1): 199–223 (2022)

    work page 2022

  10. [10]

    Mizuki, M

    T. Mizuki, M. Kumamoto and H. Sone. The Five-Card Trick Can Be Done with Four Cards. InProceedings of the 18th International Conference on the Theory and Application of Cryptology and Information Security (ASIACRYPT), pp. 598–606 (2012). 11

    work page 2012

  11. [11]

    Mizuki and H

    T. Mizuki and H. Shizuya. A formalization of card-based cryptographic protocols via abstract machine.International Journal of Information Security, 13(1): 15–23 (2014)

    work page 2014

  12. [12]

    Mizuki and H

    T. Mizuki and H. Sone. Six-Card Secure AND and Four-Card Secure XOR. InPro- ceedings of the 3rd International Frontiers of Algorithmics Workshop (FAW), pp. 358–369 (2009)

    work page 2009

  13. [13]

    Nishida, T

    T. Nishida, T. Mizuki and H. Sone. Securely Computing the Three-Input Majority Function with Eight Cards. InProceedings of the 2nd International Conference on the Theory and Practice of Natural Computing (TPNC), pp. 193–204 (2013)

    work page 2013

  14. [14]

    Nishimura, Y

    A. Nishimura, Y. Hayashi, T. Mizuki and H. Sone. An Implementation of Non-Uniform Shuffle for Secure Multi-Party Computation. InProceedings of the 3rd ACM International Workshop on ASIA Public-Key Cryptography (APKC), pp. 49–55 (2016)

    work page 2016

  15. [15]

    Nishimura, Y

    A. Nishimura, Y. Hayashi, T. Mizuki and H. Sone. Pile-Shifting Scramble for Card- Based Protocols.IEICE Trans. Fundamentals, E101.A(9): 1494–1502 (2018)

    work page 2018

  16. [16]

    Nishimura, T

    A. Nishimura, T. Nishida, Y. Hayashi, T. Mizuki and H. Sone. Card-based protocols using unequal division shuffles.Soft Computing, 22(2): 361–371 (2018)

    work page 2018

  17. [17]

    Ruangwises and T

    S. Ruangwises and T. Itoh. Securely Computing then-Variable Equality Function with 2nCards.Theoretical Computer Science, 887: 99–110 (2021)

    work page 2021

  18. [18]

    Saito, D

    T. Saito, D. Miyahara, Y. Abe, T. Mizuki and H. Shizuya. How to Implement a Non- uniform or Non-closed Shuffle. InProceedings of the 9th International Conference on the Theory and Practice of Natural Computing (TPNC), pp. 107–118 (2020)

    work page 2020

  19. [19]

    Sasaki, D

    T. Sasaki, D. Miyahara, T. Mizuki and H. Sone. Efficient card-based zero-knowledge proof for Sudoku.Theoretical Computer Science, 839: 135–142 (2020)

    work page 2020

  20. [20]

    Shinagawa and T

    K. Shinagawa and T. Mizuki. The Six-Card Trick: Secure Computation of Three-Input Equality. InProceedings of the 21st Annual International Conference on Information Security and Cryptology (ICISC), pp. 123–131 (2018)

    work page 2018

  21. [21]

    Shinagawa, T

    K. Shinagawa, T. Mizuki, J.C.N. Schuldt, K. Nuida, N. Kanayama, T. Nishide, G. Hanaoka and E. Okamoto. Card-Based Protocols Using Regular Polygon Cards.IEICE Trans. Fundamentals, E100.A(9): 1900–1909 (2017)

    work page 1900

  22. [22]

    Toyoda, D

    K. Toyoda, D. Miyahara and T. Mizuki. Another Use of the Five-Card Trick: Card- Minimal Secure Three-Input Majority Function Evaluation. InProceedings of the 22nd International Conference on Cryptology in India (INDOCRYPT), pp. 536–555 (2021)

    work page 2021

  23. [23]

    I. Ueda, D. Miyahara, A. Nishimura, Y. Hayashi, T. Mizuki and H. Sone. Secure im- plementations of a random bisection cut.International Journal of Information Security, 19(4): 445–452 (2020). 12

    work page 2020