IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Secure Multiparty Computation for Comparator Networks

Gembu Morohashi, Koji Chida, K. HIROTA, H. KIKUCHI

Published Sep 1, 2008• 6 citations

Abstract

We propose a multiparty protocol for comparator networks which are used to compute various functions in statistical analysis, such as the maximum, minimum, median, and quartiles, for example, through sorting and searching. In the protocol, all values which are inputted to a comparator network and all intermediate outputs are kept secret assuming the presence of an honest majority. We also introduce an application of the protocol for a secure (M+1)-st price auction.

DOI: 10.1093/ietfec/e91-a.9.2349

Related papers

Secure Sorting and Selection via Function Secret Sharing

Amit Agarwal, Elette Boyle, Nishanth Chandran +5 more

We revisit the problem of concretely efficient secure computation of sorting and selection (e.g., maximum, median, or top-k) on secret-shared data, focusing on the case of security against a single semi-honest party. Previous solutions either have a high communication overhead or many rounds of interaction, even when allowing input-independent preprocessing.

ACM SIGSAC Conference on Computer and Communications Security (CCS)Dec 2, 202412 citations

Implementation of a Secure Multiparty Computation Protocol

Tahsin C. M. Dönmez

Secure multiparty computation (SMC) allows a set of parties to jointly compute a function on private inputs such that, they learn only the output of the function, and the correctness of the output is guaranteed even when a subset of the parties is controlled by an adversary. SMC allows data to be kept in an uncompromisable form and still be useful, and it also gives new meaning to data ownership, allowing data to be shared in a useful way while retaining its privacy. Thus, applications of SMC hold promise for addressing some of the security issues information-driven societies struggle with. In this thesis, we implement two SMC protocols. Our primary objective is to gain a solid understanding of the basic concepts related to SMC. We present a brief survey of the field, with focus on SMC based on secret sharing. In addition to the protocol im- plementations, we implement circuit randomization, a common technique for efficiency improvement. The implemented protocols are run on a simulator to securely evaluate some simple arithmetic functions, and the round complexities of the implemented protocols are compared. Finally, we attempt to extend the implementation to support more general computations.

Dec 20, 20170 citations

Performance Analysis of Secure Multiparty Computation Protocol

Samiksha Shukla, Durgesh Kumar Mishra

In this paper we address the issue related to privacy, security, complexity and Implementation, various adversaries exist which hamper the secure multiparty computation. In the secure multiparty computation, a set of parties wishes to jointly compute some function of their inputs. Such a computation must preserve certain security properties, like privacy and correctness, even if some of the participating parties or an external adversary colludes to attack the honest parties.

Mapana Journal of SciencesMay 31, 20090 citations

Performance Comparison of Secure Comparison Protocols

Florian Kerschbaum, Debmalya Biswas, Sebastiaan J. A. de Hoogh

Secure multiparty computation (SMC) has gained tremendous importance with the growth of the Internet and e-commerce, where mutually untrusted parties need to jointly compute a function of their private inputs. However, SMC protocols usually have very high computational complexities, rendering them practically unusable. In this paper, we tackle the problem of comparing two input values in a secure distributed fashion. We propose efficient secure comparison protocols for both the homomorphic encryption and secret sharing schemes. We also give experimental results to show their practical relevance.

International Workshop on Database and Expert Systems Applications (DEXA)Aug 1, 200954 citations

On Achieving the “Best of Both Worlds” in Secure Multiparty Computation

Yuval Ishai, Jonathan I. Katz, Eyal Kushilevitz Z +2 more

Two settings are traditionally considered for secure multiparty computation, depending on whether or not a majority of the parties are assumed to be honest. Existing protocols that assume an honest majority provide “full security” (and, in particular, guarantee output delivery and fairness) when this assumption holds, but are completely insecure if this assumption is violated. On the other hand, known protocols tolerating an arbitrary number of corruptions do not guarantee fairness or output delivery even if only a single party is dishonest. It is natural to wonder whether it is possible to achieve the “best of both worlds”: namely, a single protocol that simultaneously achieves the best possible security in both the above settings. Here, we rule out this possibility (at least for general functionalities) and show some positive results regarding what can be achieved.

SIAM Journal on ComputingJan 1, 201132 citations

On Protocol Security in the Cryptographic Model

Jesper Buus Nielsen, Jesper Buus Nielsen

It seems to be a generally acknowledged fact that you should never trust a computer and that you should trust the person operating the computer even less. This in particular becomes a problem when the party that you do not trust is one which is separated from you and is one on which you depend, e.g. because that party is the holder of some data or some capability that you need in order to operate correctly. How do you perform a given task involving interaction with other parties while allowing these parties a minimal influence on you and, if privacy is an issue, allowing them to learn as little about you as possible. This is the general problem of secure multiparty computation. The usual way of formalizing the problem is to say that a number of parties who do not trust each other wish to compute some function of their local inputs, while keeping their inputs as secret as possible and guaranteeing the correctness of the output. Both goals should be obtained even if some parties stop participating or some malevolent coalition of the parties start deviating arbitrarily from the agreed protocol. The task is further complicated by the fact that besides their mutual distrust, nor do the parties trust the channels by which they communicate. A general solution to the secure multiparty computation problem is a compiler which given any feasible function describes an efficient protocol which allows the parties to compute the function securely on their local inputs over an open network. Over the past twenty years the secure multiparty computation problem has been the subject of a large body of research, both research into the models of multiparty computation and research aimed at realizing general secure multiparty computation. The main approach to realizing secure multiparty computation has been based on verifiable secret sharing as computation, where each party holds a secret share of each input and during the execution computes secret shares of all intermediate values. This approach allows the parties to keep all inputs and intermediate values secret and to pool the shares of the output values to learn exactly these values. More recently an approach based on joint homomorphic encryption was introduced, allowing for an efficient realization of general multiparty computation secure against an eavesdropper. A joint encryption scheme is an encryption scheme where all parties can encrypt, but where it takes the participation of all parties to open an encryption. The computation then starts by all parties broadcasting encryptions of their inputs and progresses through computing encryptions of the intermediary values using the homomorphic properties of the encryption scheme. The encryptions of the outputs can then be jointly decrypted. In this dissertation we extend this approach by using threshold homomorphic encryption to provide full-fledged security against an active attacker which might control some of the parties and which might take over parties during the course of the protocol execution. As opposed to a joint encryption scheme a threshold encryption scheme only requires that a given number of the parties are operating correctly for decryption to be possible. In this dissertation we show that threshold homomorphic encryption allows to solve the secure general multiparty computation problem more efficiently than previous approaches to the problem. Starting from an open point-to-point network there is a long way to general secure multiparty computation. The dissertation contains contributions at several points along the way. In particular we investigate how to realize secure channels. We also show how threshold signature schemes can be used to efficiently realize a broadcast channel and how threshold cryptography can be used to provide the parties of the network with a source of shared randomness. All three tools are well-known to be extremely powerful resources in a network, and our principle contribution is to provide efficient realizations. The dissertation also contains contributions to the definitional part of the field of multiparty computation. Most significantly we augment the recent model of universally composable security with a formal notion of what it means for a protocol to only realize a given problem under a given restricted input-output behavior of the environment. This e.g. allows us to give the first specification of a universally composable zero-knowledge proof of membership which does not at the same time require the proof system to be a proof of knowledge.

Jan 1, 20039 citations