Secure multi-party computation provides a wide array of protocols for mutually distrustful parties be able to securely evaluate functions of private inputs. Within recent years, many such protocols have been proposed representing a plethora of strategies to securely and efficiently handle such computation. These protocols have become increasingly efficient, but their performance still is impractical in many settings. We propose new approaches to some of these problems which are either more efficient than previous works within the same security models or offer better security guarantees with comparable efficiency. The goals of this research are to improve efficiency and security of secure multi-party protocols and explore the application of such approaches to novel threat scenarios. Some of the novel optimizations employed are dynamically switching domains of shared secrets, asymmetric computations, and advantageous functional transformations, among others. Specifically, this work presents a novel combination of Shamir and Additive secret sharing to be used in parallel which allows for the transformation of efficient protocols secure against passive adversaries to be secure against active adversaries. From this set of primitives we propose the construction of a comparison protocol which can be implemented under that approach with a complexity which is more efficient than other recent works for common domains of interest. Finally, we present a system which addresses a critical security threat for the protection and obfuscation of information which may be of high consequence.
Secure multi-party computation provides a wide array of protocols for mutually distrustful parties be able to securely evaluate functions of private inputs. Within recent years, many such protocols have been proposed representing a plethora of strategies to securely and efficiently handle such computation. These protocols have become increasingly efficient, but their performance still is impractical in many settings. We propose new approaches to some of these problems which are either more efficient than previous works within the same security models or offer better security guarantees with comparable efficiency. The goals of this research are to improve efficiency and security of secure multi-party protocols and explore the application of such approaches to novel threat scenarios. Some of the novel optimizations employed are dynamically switching domains of shared secrets, asymmetric computations, and advantageous functional transformations, among others. Specifically, this work presents a novel combination of Shamir and Additive secret sharing to be used in parallel which allows for the transformation of efficient protocols secure against passive adversaries to be secure against active adversaries. From this set of primitives we propose the construction of a comparison protocol which can be implemented under that approach with a complexity which is more efficient than other recent works for common domains of interest. Finally, we present a system which addresses a critical security threat for the protection and obfuscation of information which may be of high consequence.
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.
This paper investigates the application of quantum-inspired cryptographic principles to enhance the security and efficiency of secure multi-party computation (SMC) protocols. Traditional SMC protocols, such as Shamir's Secret Sharing, rely on classical cryptographic assumptions that are increasingly vulnerable to advancements in computing power, particularly with the rise of quantum computers. We propose a framework leveraging concepts from quantum mechanics, specifically superposition and probabilistic approaches, to construct novel SMC protocols. These protocols aim to achieve comparable security levels to existing methods while potentially offering improved performance characteristics and resilience against attacks exploiting classical vulnerabilities. The core of our approach involves replacing deterministic operations with probabilistic ones, mimicking the inherent uncertainty in quantum systems. This reduces the reliance on hard mathematical problems and introduces a layer of complexity that is more difficult for adversaries to analyze. The paper details the design of a modified Shamir Secret Sharing scheme incorporating these quantum-inspired elements and provides a theoretical analysis of its security properties. Ultimately, this work contributes to the exploration of a new paradigm in cryptography, adapting quantum-inspired techniques to bolster the security of distributed computing environments.
Secure multi-party computation (SMC) is an emerging topic which has been drawing growing attention during recent decades. There are many examples which show importance of SMC constructions in practice, such as privacy-preserving decision making and machine learning, auctions, private set intersection, and others. In this tutorial, we provide a comprehensive coverage of SMC techniques, starting from precise definitions and fundamental techniques. Consequently, a significant portion of the tutorial focuses on recent advances in general SMC constructions. We cover garbled circuit evaluation (GCE) and linear secret sharing (LSS) which are commonly used for secure two-party and multi-party computation, respectively. The coverage includes both standard adversarial models: semi-honest and malicious. For GCE, we start with the original Yao's garbled circuits construction [30] for semi-honest adversaries and consequently cover its recent optimizations such as the "free XOR,'' the garbled row reduction, the half-gates optimization, and the use of AES NI techniques. We follow with a discussion of techniques for making GCE resilient to malicious behavior, which includes the cut-and-choose approach and additional techniques to deter known attacks in the presence of malicious participants. In addition, we include the-state-of-the-art protocols for oblivious transfer (OT) and OT extension in the presence of semi-honest and malicious users. For LSS, we start from standard solutions for the semi-honest adversarial model including [5, 28] and consequently move to recent efficient constructions for semi-honest and malicious adversarial models. The coverage includes different types of corruption thresholds (with and without honest majority), which imply different guarantees with respect to abort.
Secure Multi-Party Computation (MPC) protocols allow a group of mutually distrusting users to compute a function jointly on their inputs without revealing any information beyond the output. For many years, implementations of MPC protocols have targeted security against semi-honest adversaries, i.e., attackers are assumed to execute the protocol honestly but try to learn private information after the fact. Protocols secure against stronger and more realistic malicious adversaries, who could behave arbitrarily during the protocol execution, were known to exist but were much less efficient. This thesis introduces a new paradigm to construct extremely efficient MPC protocols with malicious security. In particular, this thesis consists of three major contributions. 1. We introduce the authenticated garbling framework, and present an efficient concrete instantiation of the protocol. The resulting protocol partially closes the gap between semi-honest and malicious MPC protocols asymptotically; the implementation of the protocol represents the state-of-the-art system for malicious two-party computation. 2. We discuss how to apply authenticated garbling to the multi-party setting, where all-but-one parties can be corrupted by the adversary. The resulting protocol improves upon the best previous constant-round protocol by orders of magnitude. We also present a system that, for the first time, enables MPC executions among hundreds of parties, distributed globally. 3. We present a series of optimizations to two-party authenticated garbling by interpreting authenticated garbling in a new way. The improved malicious protocol has essentially the same concrete efficiency as the best semi-honest protocol in the preprocessing model. 4. We develop these protocols in EMP-toolkit, a practical and efficient MPC tool that can be used to build new protocols and to develop applications using our existing protocols.
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.
The contributions of this paper are three-fold. First, as an abstraction of previously proposed cryptographic protocols we propose two cryptographic primitives: homomorphic shared commitments and linear secret sharing schemes with an additional multiplication property. We describe new constructions for general secure multi-party computation protocols, both in the cryptographic and the information-theoretic (or secure channels) setting, based on any realizations of these primitives. Second, span programs, a model of computation introduced by Karchmer and Wigderson, are used as the basis for constructing new linear secret sharing schemes, from which the two above-mentioned primitives as well as a novel verifiable secret sharing scheme can efficiently be realized. Third, note that linear secret sharing schemes can have arbitrary (as opposed to threshold) access structures. If used in our construction, this yields multi-party protocols secure against general sets of active adversaries, as long as in the cryptographic (information-theoretic) model no two (no three) of these potentially misbehaving player sets cover the full player set. This is a strict generalization of the threshold-type adversaries and results previously considered in the literature. While this result is new for the cryptographic model, the result for the information-theoretic model was previously proved by Hirt and Maurer. However, in addition to providing an independent proof, our protocols are not recursive and have the potential of being more efficient.