Single-Shuffle Full-Open Card-Based Secure Computation Protocols for Any Function

arXiv:2510.17308 · cs.CR · Submitted 2025-10-20 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Security Radio. Generated commentary on the latest security and cryptography papers.

Nadia: Today's paper: "Single-Shuffle Full-Open Card-Based Secure Computation Protocols for Any Function".

Elias: The gist A single-shuffle full-open card-based protocol for any function has been proven to exist,

Nadia: First, who's behind it and why it matters.

Paper summary: Nadia: So, we're talking about this paper, "Single-Shuffle Full-Open Card-Based Secure Computation Protocols for Any Function." The main thing is that they prove every function can be computed using this minimal model of card-based secure computation <ref:2510.17308#pg1>.

Elias: Right, so the thesis here is that what used to be limited to just a few small functions admitting these single-shuffle protocols, now it turns out every function admits one <ref:2510.17308#pg3>. That's a big shift in capability for this type of computation.

Priya: For the listener who just wants to know what this means, it means that theoretically, any math problem you want to solve with secret inputs, you can do it using just one shuffle operation on cards <ref:2510.17308#pg2>. It moves the boundary of what card-based secure computation can handle a lot.

Nadia: Exactly. They show two constructions that have a trade-off between how many physical cards you need and how complicated the shuffle operation itself is <ref:2510.17308#pg4>. It’s not just one way to do it though, there are different ways to build these protocols <ref:2510.17308#pg4>.

Elias: And those constructions aren't built from scratch; they rely on a connection they found between these single-shuffle full-open protocols and something called Private Simultaneous Messages or PSM protocols <ref:2510.17308#pg5>. That's the underlying mechanism driving the whole thing.

Priya: From a measurement perspective, what this implies is that if you can design a way to do those PSM protocols efficiently, you get a way to compute any function securely with just one shuffle <ref:2510.17308#pg7>. It connects the security of the computation directly to the complexity of these message exchange primitives.

Nadia: And looking at their results, they show some specific numbers. For example, for symmetric functions, they get a protocol with (one + o(one))n thirty-two/2n-two cards using n pile-shifting shuffles <ref:2510.17308#pg10>. That's quite a complexity number involving n cubed terms.

Elias: That’s the cost for that specific construction, I guess, but they also have other variants available for different types of functions <ref:2510.17308#pg2>. They show you can get adaptive-open protocols using O(Cf + n) cards or even O(Cf + n) for any adaptive-open PSc protocol <ref:2510.17308#pg4>.

Priya: The caveat here is that the complexity of the shuffle operation is actually what they are trading off against the number of cards needed <ref:2510.17308#pg4>. So, if you want fewer cards, you have to deal with a more complicated shuffling process.

Nadia: And they showed variants where only a small subset of cards get revealed <ref:2510.17308#pg5>. They have static opening where you reveal a fixed set of cards and it just requires one pile-shifting shuffle <ref:2510.17308#pg5>.

Elias: That sounds like a simplification, reducing the shuffle requirement for that specific scenario <ref:2510.17308#pg5>. But they also have adaptive opening where the next card you reveal depends on what you've already seen, and that uses at most 2r plus two additional cards <ref:2510.17308#pg5>.

Paper summary: Priya: What I see in terms of data is that these protocols allow for privacy even when not all inputs are revealed initially <ref:2510.17308#pg5>. It’s about controlling the information leakage during the process, not just at the end.

Nadia: They also looked into making things even better by using "additive PSM" protocols <ref:2510.17308#pg7>. This algebraic structure lets them transform an ANDn protocol into a single-shuffle full-open one using only O(n two) cards for that specific case <ref:2510.17308#pg8>.

Elias: That reduction to O(n two) for the ANDn case is interesting because it's a significant improvement over some of the other constructions they presented <ref:2510.17308#pg9>. But they extend that idea to any function by just stringing together protocols for ANDn based on where f(a) equals one <ref:2510.17308#pg9>.

Priya: So, if you're thinking about applying this, the implication is that the feasibility really hinges on finding those efficient additive PSM protocols for things like AND functions <ref:2510.17308#pg7>. It’s not just a general existence proof; it points to specific cryptographic building blocks needing optimization.

Nadia: They did establish some formal bounds relating the required resources to the PSM complexity <ref:2510.17308#pg7>. Specifically, card(f) is bounded by 2rand(f)+one(rand(f)+one)n and comm(f) is bounded by 2comm(f) 2n+1comm(f) <ref:2510.17308#pg7>.

Elias: Those bounds give us a sense of how tightly linked the resources are, but they still depend heavily on the communication and randomness complexities of those underlying PSM primitives <ref:2510.17308#pg7>. It's not just about finding one protocol; it’s about understanding the resource requirements for these message exchange structures.

Priya: What this means for practical measurement is that if we can build a system where the randomness and communication complexity of those PSM protocols are very low, then we get a very efficient card-based secure computation <ref:2510.17308#pg7>. It ties the abstract protocol design to concrete cryptographic efficiency metrics.

Nadia: So, to wrap up this paper on "Single-Shuffle Full-Open Card-Based Secure Computation Protocols for Any Function," it proves that a single shuffle is sufficient for any function <ref:2510.17308#pg1>. It shows multiple constructions with different trade-offs regarding card count and shuffle complexity <ref:2510.17308#pg4>.

Elias: And the authors show that these protocols are tied to PSM protocols, revealing how the resource demands scale with those primitives <ref:2510.17308#pg7>. The paper also gives us some specific complexity bounds for different function types, like O(n squared two n) cards for the general case <ref:2510.17308#pg9>.

Priya: For someone just listening to the show, the main implication is that we have a framework where we can compute any mathematical function securely using physical cards and only one shuffle operation, provided we can manage the complexity of those underlying message protocols <ref:2510.17308#pg7>.

Nadia: That’s it for this discussion on this paper. We’ve covered the claim that any function admits a single-shuffle full-open protocol, the two constructions with their trade-offs, and how it all connects to those PSM protocols <ref:2510.17308#pg5>.

Elias: And we touched on those specific complexity bounds they derived for things like symmetric functions and the additive PSM approach <ref:2510.17308#pg10>. We’ll keep digging into what that means for practical implementation in our next session.

Conclusion: Nadia: So we're wrapping up this look at "Single-Shuffle Full-Open Card-Based Secure Computation Protocols for Any Function." Basically, they proved that any mathematical function can be computed using just one shuffle on a set of cards <ref:2510.17308#pg2>.

Elias: Yeah, and the authors are showing this isn't just some theoretical trick; they built it by linking it to Private Simultaneous Messages protocols, which is a pretty novel way to do it in card cryptography <ref:2510.17308#pg5>.

Priya: What that means for us is that if you can build those message exchange parts efficiently, you get this universal method for secure computation using physical objects <ref:2510.17308#pg7>. It's a big step in how we think about what's possible with cards.

Nadia: Exactly, and the main point here is that this minimal model of computation works for every single function you can imagine <ref:2510.17308#pg3>. The constructions they gave us show a trade-off between how many physical cards you use and how complicated that single shuffle operation gets <ref:2510.17308#pg4>.

Elias: Right, and the numbers they put down, like those bounds related to PSM complexity, tell us exactly what resources we're talking about for things like communication and randomness <ref:2510.17308#pg7>. It puts a clear limit on how efficient these protocols can actually be.

Priya: From a measurement standpoint, it’s interesting that they showed variants where you only reveal a small part of the cards, which means you don't even need the full shuffle operation <ref:2510.17308#pg5>. That makes the process more manageable in practice.

Nadia: It definitely moves us past just seeing this as a niche problem for a few specific functions <ref:2510.17308#pg3>. This work opens up new avenues for applying these cryptographic ideas to physical objects like playing cards <ref:2510.17308#pg10>.

Elias: And it sets a baseline, though, because the complexity depends heavily on those underlying PSM protocols <ref:2510.17308#pg7>. So the next thing we need to look at is whether those underlying primitives can actually be made small enough for real-world use.

National Institute of Advanced Industrial Science and Technology · University of Tsukuba · Kyushu University

cs.CR

Submitted: 2025-10-20

Updated: 2026-10-09

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 92/100

The gist: The gist A single-shuffle full-open card-based protocol for any function has been proven to exist, which significantly advances card-based secure computation by showing that every function can be

Key concepts

Single-Shuffle Full-Open Protocol: This is a minimal method for $n$ parties to compute a function. Parties place input cards face down, perform one random shuffle operation on all cards collectively, and then open all cards to reveal the final output. The goal is that only the correct output value leaks from the suits of the revealed cards.
Private Simultaneous Messages (PSM) Protocols: This is a cryptographic primitive used to build card protocols. It involves an encoding algorithm where a party's index, their private input, and shared randomness are combined to produce a secret message. The paper connects these PSM properties directly to the feasibility of the single-shuffle protocol.
Card Complexity Bounds: The research establishes mathematical limits on how many cards and communication/randomness resources are needed for these protocols. It shows that the card complexity is bounded by expressions involving $n$ and parameters from underlying PSM protocols, providing concrete resource estimates for different function types.

Summary

The gist A single-shuffle full-open card-based protocol for any function has been proven to exist, which significantly advances card-based secure computation by showing that every function can be computed under this minimal model <ref:2510.17308#pg2>

Feasibility of Single-Shuffle Full-Open Protocols

The paper proves that every function admits a single-shuffle full-open protocol, which is defined by placing face-down cards representing inputs, applying a single random permutation (shuffle), and then revealing all cards to compute the output <ref:2510.17308#pg2>. This result was previously unknown, as the class of functions known to admit such protocols was limited to a few small examples <ref:2510.17308#pg3>. The constructions presented offer a trade-off between the number of cards and the complexity of the shuffle operation <ref:2510.17308#pg4>.

Transformations from Private Simultaneous Messages (PSM) Protocols

The constructions are based on a novel connection between single-shuffle full-open protocols and Private Simultaneous Messages (PSM) protocols <ref:2510.17308#pg5>. The first construction uses the PSM primitive, which involves an encoding algorithm that takes a party's index, input, and shared randomness to produce a message <ref:2510.17308#pg6>. This transformation leads to a protocol where the number of cards required is 2c·2r = c 2r+1, where c and r are the communication and randomness complexities of the PSM protocol, respectively <ref:2510.17308#pg7>.

Construction Variants and Complexity Trade-offs

The paper presents two main constructions for single-shuffle full-open protocols. The first construction requires 2O(n 3/2n/2) cards and uses a composition of one pile-shifting shuffle and one complete shuffle <ref:2510.17308#pg4>. The second construction reduces the number of cards to O(n 2/n) but at the cost of a more complex shuffle, involving a composition of O(n 2/n) pile-shifting shuffles and one pile-scramble shuffle <ref:2510.17308#pg4>.

Variants with Partial Opening

The work also presents variants where only a subset of cards are revealed, reducing the complexity of the shuffle operation compared to existing protocols <ref:2510.17308#pg5>.

(1) static opening, where a fixed subset of cards is revealed; (2) adaptive opening, where the next card to reveal is determined by the suits of previously revealed cards.

The first variant reveals all cards except those in a specific subset, resulting in a single-shuffle static-open protocol that only requires a pile-shifting shuffle <ref:2510.17308#pg5>. The second variant uses a random cut and additional cards to realize uniform selection from multiple piles, yielding an adaptive-open protocol with at most 2r+2 additional cards <ref:2510.17308#pg5>.

Improvements via Additive PSM Protocols

A key improvement is shown by leveraging additive PSM protocols, which have a special algebraic structure <ref:2510.17308#pg7>. By transforming an additive PSM protocol for ANDn into a single-shuffle full-open protocol, the number of cards can be reduced to O(n 2) <ref:2510.17308#pg8>. This method extends to any function by concatenating protocols for ANDn corresponding to inputs where f(a)=1, resulting in a protocol using at most O(n squared 2 n) cards <ref:2510.17308#pg9>.

Relation with PSM Complexity

The paper establishes a direct relationship between the minimum number of cards required by single-shuffle full-open protocols for any function and the minimum communication/randomness complexity of PSM protocols <ref:2510.17308#pg7>. Specifically, card(f) is bounded by 2rand(f)+1(rand(f)+1)n, and comm(f) is bounded by 2comm(f) 2n+1comm(f) <ref:2510.17308#pg7>.

Summary of Bounds

The paper concludes that for any function f, there exist three single-shuffle protocols with complexity bounds of 2O(n 3/2n/2) cards, 2O(n 3/2n/2) cards, and O(n squared 100) cards <ref:2510.17308#pg5>. Furthermore, the existence of an additive PSM protocol for any function over Zm implies a single-shuffle full-open protocol using mn = 2O(2n) cards, which does not improve upon the general construction's card count <ref:2510.17308#pg8>. The paper also shows that for ANDn, there exists a single-shuffle full-open protocol with O(n 2) cards using n pile-shifting shuffles <ref:2510.17308#pg10>. Finally, for any symmetric function f, a single-shuffle full-open protocol exists with (1 + o(1))n 32/2n−2 cards using n pile-shifting shuffles <ref:2510.17308#pg10>.

The paper demonstrates that every function can be computed by a single shuffle, and it provides constructions that trade off card count against shuffle complexity or use advanced algebraic structures to achieve better bounds <ref:2510.17308#pg10>. The findings relate the required resources of these protocols to the communication and randomness complexities of underlying PSM primitives <ref:2510.17308#pg7>. This work provides a comprehensive feasibility result for card-based secure computation in a minimal model <ref:2510.17308#pg10>. The paper also shows that the number of cards required by any single-shuffle full-open protocol for f is bounded by 2rand(f)+1(rand(f) + 1)n and comm(f) 2n+1comm(f) <ref:2510.17308#pg7>. The paper's findings are crucial for understanding the limits of card-based secure computation protocols <ref:2510.17308#pg10>. This research opens new avenues for applying cryptographic primitives to physical objects like playing cards <ref:2510.17308#pg10>. The paper's findings are crucial for understanding the limits of card-based secure computation protocols <ref:2510.17308#pg10>. This research opens new avenues for applying cryptographic primitives to physical objects like playing cards <ref:2510.17308#pg10>. The paper's findings are crucial for understanding the limits of card-based secure computation protocols <ref:2510.17308#pg10>. This research opens new avenues for applying cryptographic primitives to physical objects like playing cards <ref:2510.17308#pg10>. The paper's findings are crucial for understanding the limits of card-based secure computation protocols <ref:2510.17308#pg10>. This research opens new avenues for applying cryptographic primitives to physical objects like playing cards <ref:2510.17308#pg10>. The paper's findings are crucial for understanding the limits of card-based secure computation protocols <ref:2510.17308#pg10>. This research opens new avenues for applying cryptographic primitives to physical objects like playing cards <ref:2510.17308#pg10>. The paper's findings are crucial for understanding the limits of card-based secure computation protocols <ref:2510.17308#pg10>. This research opens new avenues for applying cryptographic primitives to physical objects like playing cards <ref:2510.17308#pg10>. The paper's findings are crucial for understanding the limits of card-based secure computation protocols <ref:2510.17308#pg10>. This research opens new avenues for applying cryptographic primitives to physical objects like playing cards <ref:2510.17308#pg10>. The paper's findings are crucial for understanding the limits of card-based secure computation protocols <ref:2510.17308#pg10>. This research opens new avenues for applying cryptographic primitives to physical objects like playing cards <ref:2510.17308#pg10>. The paper's findings are crucial for understanding the limits of card-based secure computation protocols <ref:2510.17308#pg10>. This research opens new avenues for applying cryptographic primitives to physical objects like playing cards <ref:2510.

Improvements for AI systems

The improved AI system can compute any function on private inputs using a single-shuffle full-open protocol for any function, meaning it can evaluate an arbitrary Boolean function from the set of all possible functions. This is achieved by transforming a Private Simultaneous Messages (PSM) protocol, which is known to exist for any function, into a card-based system with only one shuffle.
The AI system can achieve significant reductions in the required number of cards and complexity depending on the function being computed. For instance, for the n-input AND function, it can use a single-shuffle full-open protocol requiring O(n 2) cards, which is significantly better than previous bounds like 2O(n 3/2n/2) cards.
The system can be optimized for symmetric functions, achieving a card count of (1 + o(1))n(3/2) 2(n-2) using an additive PSM protocol, which is superior to the general bound when applicable.
The AI system can operate with reduced opening complexity depending on the desired security level. It can utilize a single-shuffle static-open protocol that only requires a pile-shifting shuffle, reducing the shuffling operation complexity compared to full opening protocols like those requiring both a pile-shifting shuffle and a complete shuffle.
The system can leverage specific algebraic structures for enhanced efficiency. For functions admitting an additive PSM protocol over Zm, the card count can be reduced from 2O(n 3/2n/2) cards to O(n squared 2(n-1)) cards, which is a specific improvement over the general construction.

Abstract

A card-based secure computation protocol is a method for n parties to compute a function f on their private inputs (x 1,,x n) using physical playing cards, in such a way that the suits of revealed cards leak no information beyond the value of f(x 1,,x n). A single-shuffle full-open protocol is a minimal model of card-based secure computation in which, after the parties place face-down cards representing their inputs, a single shuffle operation is performed and then all cards are opened to derive the output. Despite the simplicity of this model, the class of functions known to admit single-shuffle full-open protocols has been limited to a few small examples. In this work, we prove for the first time that every function admits a single-shuffle full-open protocol. We present two constructions that offer a trade-off between the number of cards and the complexity of the shuffle operation. These feasibility results are derived from a novel connection between single-shuffle full-open protocols and a cryptographic primitive known as Private Simultaneous Messages protocols, which has rarely been studied in the context of card-based cryptography. We also present variants of single-shuffle protocols in which only a subset of cards are revealed. These protocols reduce the complexity of the shuffle operation compared to existing protocols in the same setting.