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

• URL: http://arxiv.org/abs/2510.17308v1
• Date: Mon, 20 Oct 2025 08:52:23 GMT
• Title: Single-Shuffle Full-Open Card-Based Protocols for Any Function
• Abstract summary: 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.
• Score: 4.039245878626346
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A card-based secure computation protocol is a method for $n$ parties to compute a function $f$ on their private inputs $(x_1,\ldots,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,\ldots,x_n)$. A \textit{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 \textit{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.

Related papers

• SLIDE: Shuffle Shamir Secret Shares Uniformly with Linear Online Communication and Guaranteed Output Delivery [7.706875592040788]
  We propose two new shuffle protocols for Shamir secret sharing.<n>First protocol is concretely efficient, while the second achieves the best-known $O(nml)$ online communication and $O(n)$ rounds.<n> Experiments show significant improvements in online efficiency and total cost over prior work.
  arXiv  Detail & Related papers  (2026-08-27T13:44:17Z)
• The Optimal Rate Function in Covariant Quantum State Tomography [40.87574349486165]
  We characterize quantum tomography protocols by their emphrate function<n>This function governs the exponential rate at which a protocol assigns probability to a particular estimate $$ of the true state $$.<n>For any $$ and $$ we construct a family of protocols whose rate functions converge to the quantum relative entropy $D(|)$.
  arXiv  Detail & Related papers  (2026-06-15T16:47:46Z)
• A Complexity Hierarchy of Shuffles in Card-Based Protocols [0.0]
  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.
  arXiv  Detail & Related papers  (2026-03-19T08:27:02Z)
• Cryptographic Choreographies [37.66265825228905]
  We present CryptoChoreo, a choreography language for the specification of cryptographic protocols.<n>We define the semantics of CryptoChoreo by translation to a process calculus.
  arXiv  Detail & Related papers  (2026-02-13T14:35:19Z)
• Protocol Testing with I/O Grammars [45.68497486907946]
  We propose a novel approach to protocol testing that combines input generation and output checking in a single framework.<n>We demonstrate that I/O grammars can specify advanced protocol features correctly and completely, while also enabling output validation of the programs under test.
  arXiv  Detail & Related papers  (2025-09-24T16:41:04Z)
• Impossibility Results of Card-Based Protocols via Mathematical Optimization [1.18885605647513]
  This paper introduces mathematical optimization as a new method for proving impossibility results in the field of card-based cryptography.<n>The significance of this work is that it provides a new framework for proving impossibility results and delivers a proof that is valid for any number of cards, as long as all additional cards have the same color.
  arXiv  Detail & Related papers  (2025-09-22T11:17:57Z)
• A Note on Single-Cut Full-Open Protocols [0.36832029288386137]
  A single-cut full-open protocol is one that obtains an output value by applying a random cut to an input sequence of cards, after which all cards are opened.<n>We propose three single-cut full-open protocols: two protocols for three-variable functions and one protocol for a four-variable function.
  arXiv  Detail & Related papers  (2025-07-04T06:17:52Z)
• Augmented Shuffle Protocols for Accurate and Robust Frequency Estimation under Differential Privacy [4.527947047128005]
  We propose three concrete protocols providing DP and robustness against the two attacks.<n>Our first protocol generates the number of dummy values for each item from a binomial distribution.<n>Our second protocol significantly improves the utility of our first protocol by introducing a novel dummy-count distribution.
  arXiv  Detail & Related papers  (2025-04-10T01:06:05Z)
• MORSE: An Efficient Homomorphic Secret Sharing Scheme Enabling Non-Linear Operation [37.45826289062067]
  Homomorphic secret sharing (HSS) enables two servers to locally perform functions on encrypted data directly and obtain the results in the form of shares. A Paillier-based HSS solution seamlessly achieves multiplicative homomorphism and consumes less communication costs. We propose MORSE, an efficient homomorphic secret sharing scheme enabling non-linear operation.
  arXiv  Detail & Related papers  (2024-10-09T03:29:50Z)
• The Latency Price of Threshold Cryptosystem in Blockchains [52.359230560289745]
  We study the interplay between threshold cryptography and a class of blockchains that use Byzantine-fault tolerant (BFT) consensus protocols.<n>Our measurements from the Aptos mainnet show that the optimistic approach reduces latency overhead by 71%.
  arXiv  Detail & Related papers  (2024-07-16T20:53:04Z)
• 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)
• A Quantum Approach For Reducing Communications in Classical Secure Computations with Long Outputs [2.3465488122819123]
  We study the classical cryptographic problem that two parties would like to perform secure computations with long outputs.<n>In this work, we first design a quantum cryptographic protocol that achieves secure function sampling with approximate security.
  arXiv  Detail & Related papers  (2023-10-08T16:07:46Z)
• Simple Opinion Dynamics for No-Regret Learning [38.61048016579232]
  We study a cooperative multi-agent bandit setting in the distributed GOSSIP model. We introduce and analyze families of memoryless and time-independent protocols for this setting. For stationary reward settings, we prove for the first time that these simple protocols exhibit best-of-both-worlds behavior.
  arXiv  Detail & Related papers  (2023-06-14T17:59:15Z)
• Secure Computation with Shared EPR Pairs (Or: How to Teleport in Zero-Knowledge) [26.90896904213257]
  We show that em secure teleportation through quantum channels is possible. Specifically, given the description of any quantum operation $Q$, a sender with (quantum) input $rho$ can send a single classical message that securely transmits $Q(rho)$ to a receiver.
  arXiv  Detail & Related papers  (2023-04-20T17:29:26Z)
• Counterfactual Concealed Telecomputation [22.577469136318836]
  We devise a distributed blind quantum computation protocol to perform a universal two-qubit controlled unitary operation. It is shown that the protocol is valid for general input states and that single-qubit unitary teleportation is a special case of CCT. The protocol becomes deterministic with simplified circuit implementation if the initial composite state of Alice and Bob is a Bell-type state.
  arXiv  Detail & Related papers  (2020-12-09T10:07:58Z)
• Oblivious Transfer is in MiniQCrypt [20.72168448608258]
  MiniQCrypt is a world where quantum-secure one-way functions exist, and quantum communication is possible. We construct an oblivious transfer protocol in MiniQCrypt that achieves simulation-security in the plain model against malicious quantum-time adversaries.
  arXiv  Detail & Related papers  (2020-11-30T16:51:17Z)
• Quantum copy-protection of compute-and-compare programs in the quantum random oracle model [48.94443749859216]
  We introduce a quantum copy-protection scheme for a class of evasive functions known as " compute-and-compare programs" We prove that our scheme achieves non-trivial security against fully malicious adversaries in the quantum random oracle model (QROM) As a complementary result, we show that the same scheme fulfils a weaker notion of software protection, called "secure software leasing"
  arXiv  Detail & Related papers  (2020-09-29T08:41:53Z)
• On the Round Complexity of the Shuffle Model [25.454520433661646]
  The shuffle model of differential privacy was proposed as a viable model for performing distributed differentially private computations. We show how two parties can use one round of the shuffle to send secret messages without having to first establish a secret key. We examine differentially private computations in the shuffle model that do not require the assumption of an honest majority.
  arXiv  Detail & Related papers  (2020-09-28T17:57:42Z)
• On Distributed Differential Privacy and Counting Distinct Elements [52.701425652208734]
  We study the setup where each of $n$ users holds an element from a discrete set. The goal is to count the number of distinct elements across all users.
  arXiv  Detail & Related papers  (2020-09-21T04:13:34Z)

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.