In secure multiparty computation (MPC), modulus conversion turns a sharing of a value x modulo q into a sharing of the same value modulo t, without leaking anything about x. One important application of modulus conversion is in threshold decryption for lattice-based cryptosystems, where a sharing modulo the ciphertext modulus has to be moved to the plaintext modulus before it can be opened. The most efficient protocols so far (Damgård et al., Asiacrypt 2026) are in the preprocessing model, assume x is bounded away from q by a constant factor and take two rounds for a prime target modulus, three rounds for arbitrary moduli, and one round when all moduli are 2-powers. We improve upon this by constructing three new modulus conversion protocols in the preprocessing model: - Our first conversion protocol takes a single round for arbitrary moduli, consisting of just one opening. - Our second conversion protocol is a variant of the first protocol, where in the preprocessing most of the secure multiplications are replaced by private inputs, which are checked in a batch using fully linear interactive oracle proofs (FLIOPs). This makes the preprocessing cheaper (amortized over a batch of conversions) when the number N of parties is small. This comes at the cost of making the bound on x a factor N stronger. - Our third conversion protocol avoids the bound on x altogether but takes two rounds. All our protocols are stated in the arithmetic black box (ABB) model, so they can run on top of a wide variety of MPC protocols, inheriting their corruption threshold and security model. To allow the third conversion protocol to run in two rounds, we construct the first one-round comparison protocol in the ABB model for comparing a bitwise shared n-bit value against a public threshold with polynomial-size preprocessing. Concretely, the preprocessing size is O(n^2) in general, and O(n^2 / log n) in our case where the secret value is fixed in preprocessing. We also construct constant-round ABB protocols without preprocessing for computing symmetric functions and comparisons of values shared bitwise modulo powers of arbitrary primes (e.g., 2^k), at communication quasi-linear in the number of input bits. Previously, this required either a sufficiently large prime or polynomially larger communication. Finally, we give an impossibility result for non-interactive modulus conversion, demonstrating that a single round is optimal: unless t divides q, every non-interactive conversion for inputs x < q/\beta is incorrect with probability at least ≈ 1/(4\beta).
In secure multiparty computation (MPC), modulus conversion turns a sharing of a value x modulo q into a sharing of the same value modulo t, without leaking anything about x. One important application of modulus conversion is in threshold decryption for lattice-based cryptosystems, where a sharing modulo the ciphertext modulus has to be moved to the plaintext modulus before it can be opened. The most efficient protocols so far (Damgård et al., Asiacrypt 2026) are in the preprocessing model, assume x is bounded away from q by a constant factor and take two rounds for a prime target modulus, three rounds for arbitrary moduli, and one round when all moduli are 2-powers. We improve upon this by constructing three new modulus conversion protocols in the preprocessing model: - Our first conversion protocol takes a single round for arbitrary moduli, consisting of just one opening. - Our second conversion protocol is a variant of the first protocol, where in the preprocessing most of the secure multiplications are replaced by private inputs, which are checked in a batch using fully linear interactive oracle proofs (FLIOPs). This makes the preprocessing cheaper (amortized over a batch of conversions) when the number N of parties is small. This comes at the cost of making the bound on x a factor N stronger. - Our third conversion protocol avoids the bound on x altogether but takes two rounds. All our protocols are stated in the arithmetic black box (ABB) model, so they can run on top of a wide variety of MPC protocols, inheriting their corruption threshold and security model. To allow the third conversion protocol to run in two rounds, we construct the first one-round comparison protocol in the ABB model for comparing a bitwise shared n-bit value against a public threshold with polynomial-size preprocessing. Concretely, the preprocessing size is O(n^2) in general, and O(n^2 / log n) in our case where the secret value is fixed in preprocessing. We also construct constant-round ABB protocols without preprocessing for computing symmetric functions and comparisons of values shared bitwise modulo powers of arbitrary primes (e.g., 2^k), at communication quasi-linear in the number of input bits. Previously, this required either a sufficiently large prime or polynomially larger communication. Finally, we give an impossibility result for non-interactive modulus conversion, demonstrating that a single round is optimal: unless t divides q, every non-interactive conversion for inputs x < q/\beta is incorrect with probability at least ≈ 1/(4\beta).
Secure multiparty computation (MPC) allows a set of mutually distrustful parties to compute a public function on their private inputs without revealing anything beyond the output of the computation. This paper focuses on the specific case of actively secure three-party computation with an honest majority. In particular, we are interested in solutions which allow to evaluate arithmetic circuits over real-world CPU word sizes, like 32- and 64-bit words. Our starting point is the novel compiler of Damgård et al. from CRYPTO 2018. First, we present an improved version of it which reduces the online communication complexity by a factor of 2. Next, we replace their preprocessing protocol (with arithmetic modulo a large prime) with a more efficient preprocessing which only performs arithmetic modulo powers of two. Finally, we present a novel "postprocessing" check which replaces the preprocessing phase. These protocols offer different efficiency tradeoffs and can therefore outperform each other in different deployment settings. We demonstrate this with benchmarks in a LAN and different WAN settings. Concretely, we achieve a throughput of 1 million 64-bit multiplications per second with parties located in different continents and 3 million in one location.
Secure multi-party computation (MPC) enables distrustful parties to jointly perform computations while guaranteeing both the privacy of their inputs and the correctness of the computation.
This thesis explores two aspects of secure multi-party computation: adaptive security and round efficiency. Adaptive security is concerned with an adversary that adaptively determines who and when to corrupt during the course of the computation. Even though this is a very natural and realistic assumption about the adversary, most of the MPC literature addresses security only against a static adversary — an adversary that chooses (and fixes) which parties to corrupt before the protocol starts executing. A protocol is called round-efficient if it runs in a small number of rounds. Constructing such protocols is important since efficiency of a protocol is greatly influenced by its round complexity.
The security in this thesis is formulated in the universal composability (UC) framework introduced by Canetti [Can01]. Protocols secure in the UC framework remain secure even when executed concurrently with other arbitrary protocols running in some larger network, and can be used as subroutines of larger protocols in a modular fashion. This property is important considering that nowadays many protocols are executed concurrently with others in the Internet.
With the focus on adaptive security and round efficiency, we obtain the following results:
(1) We show that with access to an ideal commitment functionality, there exists a protocol that UC realizes any well-formed multi-party functionality against a malicious, adaptive adversary that may corrupt any number of parties, with black-box access to any protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary.
(2) We show that there exists a protocol that UC realizes oblivious transfer against a semi-honest, adaptive adversary, with black-box access to a cryptographic primitive called a trapdoor simulatable cryptosystem, which is a natural relaxation of a simulatable cryptosystem introduced by Damgard and Nielsen [3N00].
We also show that the primitive can be constructed based on hardness of factoring.
(3) We present a single-message protocol that UC realizes two-party computing with encrypted data (a variant of secure two-party computation), based on the DDH assumption and non- interactive zero-knowledge arguments. The protocol achieves security against a malicious, static adversary.
(4) We present two round-efficient protocols that UC realize multi-party computing with encrypted data (a variant of secure multi-party computation), based on the DDH assumption and non-interactive zero-knowledge arguments. The first (resp. second) protocol requires one round (resp. two rounds) with appropriate preprocessing, which is independent of the exact circuit and actual inputs of the specific instance problem to solve — only the bound on the circuit size is known. Although the first protocol is more round-efficient, the preprocessing of the second is sometimes better under some efficiency considerations. Both protocols achieve security against a malicious, static adversary that may corrupt up to all but one parties.
Bit-decomposition is an important primitive in multi-party computation (MPC). Given a sharing of secret x, it allows the parties to compute the sharings of the bits of x in constant rounds. With the help of bit-decomposition, we will be able to construct constant-rounds protocols for various MPC problems, such as equality test, comparison, public modulo reduction and private exponentiation, which are four main applications of bit-decomposition. However, when considering perfect security, bit-decomposition does not have a linear communication complexity. Thus any protocols involving bit-decomposition inherit this inefficiency, i.e. the communication complexity is non-linear. Constructing protocols for MPC problems without relying on bit-decomposition is a meaningful work because this may provide us with perfect secure protocols with linear communication complexity. It is already proved that equality test, comparison and public modulo reduction can be solved without involving bit-decomposition and the communication complexity can be reduced to linear. However, it remains an open problem whether private exponentiation could be done without relying on bit-decomposition. In this paper, maybe somewhat surprisingly, we show that it can. That is to say, we construct
Multiparty computation (MPC) is a powerful and generic cryptographic framework capable of realizing essentially any cryptographic task (functionality) while preserving privacy and robustness. In the MPC model, a group of mutually distrustful parties seek to jointly compute a function f of their privately held inputs x1, ..., xn, while revealing no information about those inputs beyond what is entailed by the function output(s). Some portion of these players may be corrupted, controlled by a centralized adversary who directs their (mis)behavior and seeks to gain information on private inputs or to disrupt the protocol execution.
In this work, we examine the resource requirements of information-theoretically secure multiparty computation. In particular, we look at trade-offs involving what we call assumptions, by which we mean two aspects of the model's setup: (1) the extent to which parties are connected by secure, pairwise communication channels; and (2) the usage (as a black box) of a channel—a primitive which enforces consistency among views by allowing a single party to send a message to all other parties which is guaranteed to be consistent, even if the broadcaster is corrupted.
Part I of this work focuses on the first network-model assumption, that of the graph's connectivity by pairwise channels. We show upper and lower bounds on communication complexity in the Secure Message Transmission with Public Discussion (SMT-PD) model, as a function of the threshold of corrupted parties. The SMT-PD model, which abstracts the problem of secure communication over a partially connected network, includes two components: a public and a set of simple channels. We show significant improvements in both areas: on the channel, we reduce communication to logarithmic in terms of the message's bit-length m, where the previous best result was linear in m; on the simple channels, we reduce from O(mn) to O(mn/(n−t)), where n is the number of simple channels and t is a bound on the number of corrupted channels. Using tools from information theory, we show this amount of simple-wire communication is essentially optimal. Finally, we give an amortized solution which drastically improves communication over channel when the protocol is repeated many times sequentially.
Part II shifts focus to the second network-model assumption, the use of an atomic broadcast primitive. Here we show that three broadcast rounds suffice for general secure computation, while two broadcast rounds are necessary. In particular we show that even for the natural and important functionality of Weak Secret Sharing—a type of distributed commitment—there is no protocol which uses only a single broadcast and achieves better than an explicit constant probability of success (so the protocol's success cannot be a function of a security parameter).
Secure Multiparty Computation (MPC) allows a set of parties, each having its own private data, to compute a function of their joint data such that the parties only learn the output of this function and everything else about their data is hidden. MPC is a fundamental cryptographic abstraction that captures many other natural cryptographic primitives as special cases. It also has a wide range of practical applications such as conducting secure electronic auctions, delegating sensitive computation to untrusted cloud service providers, secure computation on genomic data and training machine learning models on private data.A long-standing open problem in this area is to construct MPC protocols that have {\\it optimal} (two-round) round complexity under the {\\it weakest} possible cryptographic hardness assumptions.We {\\it completely resolve} this problem by showing lower bounds and matching upper bounds on the hardness assumptions required for constructing round-optimal MPC. Specifically, we obtain the following results.\\begin{itemize}\\item \\textbf{Black-Box Separation.} We show that there exists no construction of two-round semi-honest MPC protocol for general functions that makes black-box use of a two-round oblivious transfer. As a corollary, a similar separation holds when starting with any 2-party functionality other than oblivious transfer. \\item \\textbf{Non-Black-Box Construction.} We show that the above negative result can be bypassed by making non-black-box use of a two-round oblivious transfer. Specifically, starting from a semi-honest (resp. malicious) secure two-round oblivious transfer protocol, we construct a two-round MPC protocol against semi-honest (resp. malicious) adversaries. \\end{itemize}Since any two-round MPC protocol for general functionalities implies a two-round oblivious transfer as a special case, the above two results show that non-black-box use of oblivious transfer is {\\it necessary and sufficient} to construct round-optimal MPC protocols.
Abstract. When secure arithmetic is required, computation based on secure multiplication (MULT) is much more efficient than computation based on secure boolean circuits. However, a typical application can also require other building blocks, such as comparison, exponentiation and the modulo (MOD) operation. Secure solutions for these functions proposed in the literature rely on bit-decomposition or other bit-oriented methods, which require O(ℓ) MULTs for ℓ-bit inputs. In the absence of a known bit-length independent solution, the complexity of the whole computation is often dominated by these non-arithmetic functions. To resolve the above problem, we start with a general modular conversion, which converts secret shares over distinct moduli. For this, we proposed a probabilistically correct protocol for this with a complexity that is independent of ℓ. Then, we show that when these non-arithmetic functions are based on secure modular conversions, they can be computed in constant rounds and O(k) MULTs, where k is a parameter for an error rate of 2 −Ω(k). To promote our protocols to be actively secure, we apply O(k) basic zero-knowledge proofs, which cost at most O(k) exponentiation computation, O(1) rounds and O(k(ℓ + κ)) communication bits, where κ is the security parameter used in the commitment scheme.