Get all the updates for this publication

Conferences

Round efficient unconditionally secure MPC and multiparty set intersection with optimal resiliencePublished in

2009

Volume: 5922 LNCS

Pages: 398 - 417

In information theoretic model, unconditionally secure multiparty computation (UMPC) allows a set of n parties to securely compute an agreed function f, even upto t < n/2 parties are under the control of an active adversary having unbounded computing power. The bound on the resilience/fault tolerance (i.e t < n/2 ) is optimal, as long as each party is connected with every other party by a secure channel and a common physical broadcast channel is available to the parties and a negligible error probability of 2 -Ω(κ) (for some security parameter κ) is allowed in the computation. Any UMPC protocol designed under the above settings is called as optimally resilient UMPC protocol. In this paper, we propose an optimally resilient UMPC protocol with n = 2t + 1, which requires only O(D) rounds, where D is the multiplicative depth of the arithmetic circuit representing f. To the best of our knowledge, our protocol is the first UMPC protocol with optimal resilience, to attain a round complexity that is independent of n. When D is constant, then our protocol requires only constant number of rounds. Our protocol is to be compared with the most round efficient, optimally resilient, UMPC protocol of [16] that requires O(log n + D) rounds in the same settings as ours. Thus our UMPC significantly reduces the round complexity of [16]. Moreover, our UMPC protocol requires the same communication complexity as that of [16]. As a tool for designing our UMPC protocol, we propose a new and robust multiplication protocol to generate t-sharing of the product of two t-shared secrets. As an interesting, practically-on-demand MPC problem, we present a protocol for unconditionally secure multiparty set intersection (UMPSI) with optimal resilience; i.e., with n = 2t + 1, having a negligible error probability in correctness. This protocol adapts the techniques used in our proposed general UMPC protocol. The protocol takes constant number rounds, incurs a private communication of O(m2n4κ) bits and broadcasts O((m2n4 + n5)κ) bits, where each party has a set of size m. To the best of our knowledge, this is the first ever UMPSI protocol with n = 2t + 1. This solves an open problem posed in [15] and [17], urging to design an UMPSI protocol with n = 2t + 1. Our UMPSI protocol is to be compared with the best known UMPSI protocol of [17] with n = 3t + 1 (i.e., non-optimal resilience), which takes constant number rounds, incurs a private communication of O((m2n3 + n4κ) κ) bits and broadcasts O((m2n3 + n 4κ)κ) bits. So even though the communication complexity of our UMPSI protocol is slightly larger than that of [17], our UMPSI protocol significantly improves the resilience of UMPSI protocol of [17]; i.e., from t < n / 3 to t < n / 2. © 2009 Springer-Verlag.

View more info for "Round Efficient Unconditionally Secure MPC and Multiparty Set Intersection with Optimal Resilience"

Content may be subject to copyright.

About the journal

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

ISSN | 03029743 |

Open Access | No |

Concepts (27)

- ACTIVE ADVERSARY
- Arithmetic circuit
- Broadcast channels
- Communication complexity
- Computing power
- Error probabilities
- MULTIPARTY COMPUTATION
- On-demand
- Open problems
- OPTIMAL RESILIENCE
- PRIVATE COMMUNICATION
- SECURE CHANNELS
- Secure multi-party computation
- SECURITY PARAMETERS
- SET INTERSECTION
- SHARED SECRETS
- Techniques used
- Theoretic model
- Communication
- Cryptography
- Information theory
- Model predictive control
- Network protocols
- Optimization
- Predictive control systems
- Probability
- Network security