Impossibility Results of Card-Based Protocols via Mathematical Optimization

• URL: http://arxiv.org/abs/2509.17595v2
• Date: Tue, 23 Sep 2025 12:45:38 GMT
• Title: Impossibility Results of Card-Based Protocols via Mathematical Optimization
• Abstract summary: 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.
• Score: 1.18885605647513
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: This paper introduces mathematical optimization as a new method for proving impossibility results in the field of card-based cryptography. While previous impossibility proofs were often limited to cases involving a small number of cards, this new approach establishes results that hold for a large number of cards. The research focuses on single-cut full-open (SCFO) protocols, which consist of performing one random cut and then revealing all cards. The main contribution is that for any three-variable Boolean function, no new SCFO protocols exist beyond those already known, under the condition that all additional cards have the same color. 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.

Related papers

• 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)
• 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)
• Cyclic Equalizability of Words and Its Application to Card-Based Cryptography [0.36832029288386137]
  We show that two binary words of equal length and equal Hamming weight are cyclically equalizable.<n>As applications of cyclic equalizability to card-based cryptography, we describe its applications to the information erasure problem and to single-cut full-open protocols.
  arXiv  Detail & Related papers  (2025-07-07T12:03:36Z)
• 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)
• Provably Secure Public-Key Steganography Based on Admissible Encoding [66.38591467056939]
  The technique of hiding secret messages within seemingly harmless covertext is known as provably secure steganography (PSS)<n>PSS evolves from symmetric key steganography to public-key steganography, functioning without the requirement of a pre-shared key.<n>This paper proposes a more general elliptic curve public key steganography method based on admissible encoding.
  arXiv  Detail & Related papers  (2025-04-28T03:42:25Z)
• Cloning Games, Black Holes and Cryptography [50.022147589030304]
  We introduce a new toolkit for analyzing cloning games.<n>This framework allows us to analyze a new cloning game based on binary phase states.<n>We show that the binary phase variantally optimal bound offers quantitative insights into information scrambling in idealized models of black holes.
  arXiv  Detail & Related papers  (2024-11-07T14:09:32Z)
• Quantum One-Wayness of the Single-Round Sponge with Invertible Permutations [49.1574468325115]
  Sponge hashing is a widely used class of cryptographic hash algorithms.<n>Intrepid permutations have so far remained a fundamental open problem.<n>We show that finding zero-pairs in a random $2n$-bit permutation requires at least $Omega (2n/2)$ many queries.
  arXiv  Detail & Related papers  (2024-03-07T18:46:58Z)
• 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 Modular Approach to Unclonable Cryptography [4.336971448707467]
  We propose unclonable puncturable obfuscation (UPO) and study its implications for unclonable cryptography. We present modular (and arguably, simple) constructions of many primitives in unclonable cryptography. We show that any cryptographic functionality can be copy-protected as long as this functionality satisfies a notion of security.
  arXiv  Detail & Related papers  (2023-11-20T16:22:52Z)
• General Cutting Planes for Bound-Propagation-Based Neural Network Verification [144.7290035694459]
  We generalize the bound propagation procedure to allow the addition of arbitrary cutting plane constraints. We find that MIP solvers can generate high-quality cutting planes for strengthening bound-propagation-based verifiers. Our method is the first verifier that can completely solve the oval20 benchmark and verify twice as many instances on the oval21 benchmark.
  arXiv  Detail & Related papers  (2022-08-11T10:31:28Z)
• Multiway Non-rigid Point Cloud Registration via Learned Functional Map Synchronization [105.14877281665011]
  We present SyNoRiM, a novel way to register multiple non-rigid shapes by synchronizing the maps relating learned functions defined on the point clouds. We demonstrate via extensive experiments that our method achieves a state-of-the-art performance in registration accuracy.
  arXiv  Detail & Related papers  (2021-11-25T02:37:59Z)
• Logical Credal Networks [87.25387518070411]
  This paper introduces Logical Credal Networks, an expressive probabilistic logic that generalizes many prior models that combine logic and probability. We investigate its performance on maximum a posteriori inference tasks, including solving Mastermind games with uncertainty and detecting credit card fraud.
  arXiv  Detail & Related papers  (2021-09-25T00:00:47Z)
• Rethinking Space-Time Networks with Improved Memory Coverage for Efficient Video Object Segmentation [68.45737688496654]
  We establish correspondences directly between frames without re-encoding the mask features for every object. With the correspondences, every node in the current query frame is inferred by aggregating features from the past in an associative fashion. We validated that every memory node now has a chance to contribute, and experimentally showed that such diversified voting is beneficial to both memory efficiency and inference accuracy.
  arXiv  Detail & Related papers  (2021-06-09T16:50:57Z)
• Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
  We introduce a novel learning problem for dense subgraph discovery. We first propose a edge-time algorithm that obtains a nearly-optimal solution with high probability. We then design a more scalable algorithm with a theoretical guarantee.
  arXiv  Detail & Related papers  (2020-06-24T11:37: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.