Card-Based Overwriting Protocol for Equality Function and Applications

• URL: http://arxiv.org/abs/2402.16290v2
• Date: Fri, 16 Aug 2024 12:43:22 GMT
• Title: Card-Based Overwriting Protocol for Equality Function and Applications
• Abstract summary: 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.
• Score: 0.34952465649465553
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Research in the area of secure multi-party computation with an unconventional method of using a physical deck of playing cards began in 1989 when den Boer proposed a protocol to compute the logical AND function using five cards. Since then, the area has gained interest from many researchers and several card-based protocols to compute various functions have been developed. In this paper, we propose a card-based protocol called the overwriting protocol that can securely compute the $k$-candidate $n$-variable equality function $f: \{0,1,\ldots ,k-1\}^n \rightarrow \{0,1\}$. We also apply the technique used in this protocol to compute other similar functions.

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)
• 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)
• Ehrenfeucht-Haussler Rank and Chain of Thought [51.33559894954108]
  We show that the rank of a function $f$ corresponds to the minimum number of Chain of Thought steps required by a single-layer transformer decoder. We also analyze the problem of identifying the position of the $k$-th occurrence of 1 in a Boolean sequence, proving that it requires $k$ CoT steps.
  arXiv  Detail & Related papers  (2025-01-22T16:30:58Z)
• Balance-Based Cryptography: Physically Computing Any Boolean Function [0.0]
  We introduce the use of a balance scale and coins as new physical tools for secure multi-party computation. In particular, we develop four protocols that can securely compute any $n$-variable Boolean function using a balance scale and coins.
  arXiv  Detail & Related papers  (2025-01-21T12:11:00Z)
• Provably Efficient Reinforcement Learning with Multinomial Logit Function Approximation [67.8414514524356]
  We study a new class of MDPs that employs multinomial logit (MNL) function approximation to ensure valid probability distributions over the state space. introducing the non-linear function raises significant challenges in both computational and statistical efficiency. We propose an algorithm that achieves the same regret with only $mathcalO(1)$ cost.
  arXiv  Detail & Related papers  (2024-05-27T11:31:54Z)
• On the Power of Interactive Proofs for Learning [3.785008536475385]
  We continue the study of doubly-efficient proof systems for verifying PAC learning. We construct an interactive protocol for learning the largest Fourier characters of a given function $f colon 0,1n to 0,1$ up to an arbitrarily small error. We show that if we do not insist on doubly-efficient proof systems, then the model becomes trivial.
  arXiv  Detail & Related papers  (2024-04-11T23:16:21Z)
• 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)
• Study of Zero-Knowledge protocols and Elliptic Curve Cryptography and their implementation in Smart Card environments using Java Card [0.0]
  This paper studies the problem of Zero-Knowledge Protocol (ZKP) and elliptic curve cryptographic implementation in a computationally limited environment. It is explained how the zero-knowledge protocol was selected to implement it on a smart card and how the benchmarking was conducted to select this protocol.
  arXiv  Detail & Related papers  (2023-08-31T12:15:03Z)
• Communication complexity of entanglement assisted multi-party computation [11.820804392113294]
  We consider a multi-party computation problem with $n$ players, where players $2, dots, n$ need to communicate appropriate information to player 1. We exhibit a quantum protocol (with complexity $(n-1) log n$ bits) and a classical protocol (with complexity $(n-1)2 (log n2$) bits) This demonstrates that our quantum protocol is strictly better than classical protocols.
  arXiv  Detail & Related papers  (2023-05-08T03:10:08Z)
• Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees [79.59010418610625]
  We study differentially private approximation algorithms for hierarchical clustering. We show strong lower bounds for the problem: that any $epsilon$-DP algorithm must exhibit $O(|V|2/ epsilon)$-additive error for an input dataset. We propose a private $1+o(1)$ approximation algorithm which also recovers the blocks exactly.
  arXiv  Detail & Related papers  (2023-01-31T19:14:30Z)
• 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)
• Faster Privacy Accounting via Evolving Discretization [54.32252900997422]
  We introduce a new algorithm for numerical composition of privacy random variables. Our algorithm achieves a running time and memory usage of $mathrmpolylog(k)$ for the task of self-composing a mechanism.
  arXiv  Detail & Related papers  (2022-07-10T04:25:37Z)
• Quantum Resources Required to Block-Encode a Matrix of Classical Data [56.508135743727934]
  We provide circuit-level implementations and resource estimates for several methods of block-encoding a dense $Ntimes N$ matrix of classical data to precision $epsilon$. We examine resource tradeoffs between the different approaches and explore implementations of two separate models of quantum random access memory (QRAM) Our results go beyond simple query complexity and provide a clear picture into the resource costs when large amounts of classical data are assumed to be accessible to quantum algorithms.
  arXiv  Detail & Related papers  (2022-06-07T18:00:01Z)
• Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
  We provide an efficient exact algorithm for the paired-permutation test for a family of structured test statistics. Our exact algorithm was $10$x faster than the Monte Carlo approximation with $20000$ samples on a common dataset.
  arXiv  Detail & Related papers  (2022-05-03T11:00:59Z)
• Universal construction of decoders from encoding black boxes [4.511923587827301]
  We propose a universal protocol for isometry inversion that constructs a decoder from multiple calls of the encoding operation. For a qubit ($d=2$) encoded in $n$ qubits, our protocol achieves an exponential improvement over any tomography-based or unitary-embedding method.
  arXiv  Detail & Related papers  (2021-10-01T08:33:38Z)
• Nearly Optimal Regret for Learning Adversarial MDPs with Linear Function Approximation [92.3161051419884]
  We study the reinforcement learning for finite-horizon episodic Markov decision processes with adversarial reward and full information feedback. We show that it can achieve $tildeO(dHsqrtT)$ regret, where $H$ is the length of the episode. We also prove a matching lower bound of $tildeOmega(dHsqrtT)$ up to logarithmic factors.
  arXiv  Detail & Related papers  (2021-02-17T18:54:08Z)

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.