Efficient Multi-Party Secure Comparison over Different Domains with Preprocessing Assistance

• URL: http://arxiv.org/abs/2602.19604v1
• Date: Mon, 23 Feb 2026 08:45:47 GMT
• Title: Efficient Multi-Party Secure Comparison over Different Domains with Preprocessing Assistance
• Authors: Kaiwen Wang, Xiaolin Chang, Yuehan Dong, Ruichen Zhang,
• Abstract summary: A critical performance bottleneck in comparison protocols is their preprocessing phase.<n>Recent frameworks introduce a passive, non-colluding dealer to accelerate preprocessing.<n>We present the first dealer-assisted $n$-party LTBits (Less-Than-Bits) and MSB (Most Significant Bit) extraction protocols over both $mathbbF_p$ and $mathbbZ_2k$.
• Score: 10.27710213197667
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Secure comparison is a fundamental primitive in multi-party computation, supporting privacy-preserving applications such as machine learning and data analytics. A critical performance bottleneck in comparison protocols is their preprocessing phase, primarily due to the high cost of generating the necessary correlated randomness. Recent frameworks introduce a passive, non-colluding dealer to accelerate preprocessing. However, two key issues still remain. First, existing dealer-assisted approaches treat the dealer as a drop-in replacement for conventional preprocessing without redesigning the comparison protocol to optimize the online phase. Second, most protocols are specialized for particular algebraic domains, adversary models, or party configurations, lacking broad generality. In this work, we present the first dealer-assisted $n$-party LTBits (Less-Than-Bits) and MSB (Most Significant Bit) extraction protocols over both $\mathbb{F}_p$ and $\mathbb{Z}_{2^k}$, achieving perfect security at the protocol level. By fully exploiting the dealer's capability to generate rich correlated randomness, our $\mathbb{F}_p$ construction achieves constant-round online complexity and our $\mathbb{Z}_{2^k}$ construction achieves $O(\log_n k)$ rounds with tunable branching factor. All protocols are formulated as black-box constructions via an extended ABB model, ensuring portability across MPC backends and adversary models. Experimental results demonstrate $1.79\times$ to $19.4\times$ speedups over state-of-the-art MPC frameworks, highlighting the practicality of our protocols for comparison-intensive MPC applications.

Related papers

• Polybasic Speculative Decoding Through a Theoretical Perspective [68.71678077009386]
  Inference latency is a critical bottleneck in the large-scale deployment of Large Language Models.<n>We introduce a novel emphpolybasic speculative decoding framework, underpinned by a comprehensive theoretical analysis.<n>We show that our approach yields speedup ratios ranging from $3.31times$ to $4.01times$ for LLaMA2-Chat 7B, up to $3.87 times$ for LLaMA3-8B, up to $4.43 times$ for Vicuna-7B and up to $3.85 times$ for Qwen2-7B.
  arXiv  Detail & Related papers  (2025-10-30T14:20:24Z)
• Cost-Aware Contrastive Routing for LLMs [57.30288453580456]
  We introduce Cost-Spectrum Contrastive Routing (CSCR), a lightweight framework that maps both prompts and models into a shared embedding space.<n>CSCR consistently outperforms baselines, improving the accuracy-cost tradeoff by up to 25%.
  arXiv  Detail & Related papers  (2025-08-17T20:16:44Z)
• Provably Sample-Efficient Robust Reinforcement Learning with Average Reward [4.530028899565083]
  We propose a new algorithm designed for robust Markov Decision Processes (MDPs) with transition uncertainty characterized by $ell_p$-norm and contamination models.<n>Our algorithm operates without requiring any prior knowledge of the robust MDP.<n>Our work provides essential theoretical understanding of sample efficiency of robust average reward RL.
  arXiv  Detail & Related papers  (2025-05-18T15:34:45Z)
• Breaking Free: Efficient Multi-Party Private Set Union Without Non-Collusion Assumptions [5.030459935922802]
  Multi-party private set union (MPSU) protocol enables $m$ $(m > 2)$ parties, each holding a set, to collectively compute the union of their sets. We propose the first MPSU protocol based on oblivious transfer and symmetric-key techniques in the standard semi-honest model. We show that our protocol requires only $4.4$ seconds in online phase for 3 parties with sets of $220$ items each.
  arXiv  Detail & Related papers  (2024-06-11T07:10:45Z)
• Projection by Convolution: Optimal Sample Complexity for Reinforcement Learning in Continuous-Space MDPs [56.237917407785545]
  We consider the problem of learning an $varepsilon$-optimal policy in a general class of continuous-space Markov decision processes (MDPs) having smooth Bellman operators. Key to our solution is a novel projection technique based on ideas from harmonic analysis. Our result bridges the gap between two popular but conflicting perspectives on continuous-space MDPs.
  arXiv  Detail & Related papers  (2024-05-10T09:58:47Z)
• Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation [53.17668583030862]
  We study infinite-horizon average-reward Markov decision processes (AMDPs) in the context of general function approximation. We propose a novel algorithmic framework named Local-fitted Optimization with OPtimism (LOOP) We show that LOOP achieves a sublinear $tildemathcalO(mathrmpoly(d, mathrmsp(V*)) sqrtTbeta )$ regret, where $d$ and $beta$ correspond to AGEC and log-covering number of the hypothesis class respectively
  arXiv  Detail & Related papers  (2024-04-19T06:24:22Z)
• Secure and Efficient Two-party Quantum Scalar Product Protocol With Application to Privacy-preserving Matrix Multiplication [2.770988618353868]
  Two-party quantum scalar product (S2SP) is a promising research area within secure multiparty computation (SMC) Existing quantum S2SP protocols are not efficient enough, and the complexity is usually close to exponential level. In this paper, a novel secure two-party quantum scalar product (S2QSP) protocol based on Fourier states is proposed to achieve higher efficiency.
  arXiv  Detail & Related papers  (2023-09-23T14:33: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)
• Fast Online Value-Maximizing Prediction Sets with Conformal Cost Control [63.90454433380153]
  Many real-world multi-label prediction problems involve set-valued predictions that must satisfy specific requirements dictated by downstream usage. We focus on a typical scenario where such requirements, separately encoding $textitvalue$ and $textitcost$, compete with each other. We present a general pipeline, dubbed as FavMac, to maximize the value while controlling the cost in such scenarios.
  arXiv  Detail & Related papers  (2023-02-02T02:53:12Z)
• The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning [34.630300910399036]
  We characterize the fundamental communication cost required to obtain the best accuracy under $varepsilon$ central DP. Our results show that $tildeOleft( min(n2varepsilon2, d) right)$ bits per client are both sufficient and necessary. This provides a significant improvement relative to state-of-the-art SecAgg distributed DP schemes.
  arXiv  Detail & Related papers  (2022-03-07T22:56:09Z)
• Permutation Compressors for Provably Faster Distributed Nonconvex Optimization [68.8204255655161]
  We show that the MARINA method of Gorbunov et al (2021) can be considered as a state-of-the-art method in terms of theoretical communication complexity. Theory of MARINA to support the theory of potentially em correlated compressors, extends to the method beyond the classical independent compressors setting.
  arXiv  Detail & Related papers  (2021-10-07T09:38:15Z)

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.