Modular exponentiation is a vital function in public key cryptography. Dozens of protocols, including encryption schemes, signature schemes, pseudorandom functions, and more, perform this operation on a secret base and/or a secret exponent. In a multiparty computation setting, these secret data might be shared over multiple parties who wish to compute this modular exponentiation in a secure and distributed way. However, whereas typical frameworks for secure multiparty computation based on secret sharing provide a basic tool box of secure distributed computation of, most importantly, randomness generation, addition, and multiplication, the status quo of secure distributed modular exponentiation is unsatisfactory. In this work, we provide a complete and comprehensive overview on existing protocols for perfectly secure distributed exponentiation differing depending on whether the inputs and outcomes are public or shared. We perform a detailed complexity computation of the currently existing protocols, observing that earlier authors have overestimated the complexity of their own protocols, and close the remaining open problem: protocols for secure distributed exponentiation with secret base, secret exponent, and public outcome. We prove that the presented protocol is universally composably secure in the presence of malicious adversaries. We finally exemplify the practical relevance of the new protocol by demonstrating how it can be used for pseudorandom generation and signing.
Modular exponentiation is a vital function in public key cryptography. Dozens of protocols, including encryption schemes, signature schemes, pseudorandom functions, and more, perform this operation on a secret base and/or a secret exponent. In a multiparty computation setting, these secret data might be shared over multiple parties who wish to compute this modular exponentiation in a secure and distributed way. However, whereas typical frameworks for secure multiparty computation based on secret sharing provide a basic tool box of secure distributed computation of, most importantly, randomness generation, addition, and multiplication, the status quo of secure distributed modular exponentiation is unsatisfactory. In this work, we provide a complete and comprehensive overview on existing protocols for perfectly secure distributed exponentiation differing depending on whether the inputs and outcomes are public or shared. We perform a detailed complexity computation of the currently existing protocols, observing that earlier authors have overestimated the complexity of their own protocols, and close the remaining open problem: protocols for secure distributed exponentiation with secret base, secret exponent, and public outcome. We prove that the presented protocol is universally composably secure in the presence of malicious adversaries. We finally exemplify the practical relevance of the new protocol by demonstrating how it can be used for pseudorandom generation and signing.
In recent years, multi-party computation (MPC) frameworks based on replicated secret sharing schemes (RSSS) have attracted the attention as a method to achieve high efficiency among known MPCs. However, the RSSS-based MPCs are still inefficient for several heavy computations like algebraic operations, as they require a large amount and number of communication proportional to the number of multiplications in the operations (which is not the case with other secret sharing-based MPCs). In this paper, we propose RSSS-based three-party computation protocols for modular exponentiation, which is one of the most popular algebraic operations, on the case where the base is public and the exponent is private. Our proposed schemes are simple and efficient in both of the asymptotic and practical sense. On the asymptotic efficiency, the proposed schemes require O(n)-bit communication and O(1) rounds,where n is the secret-value size, in the best setting, whereas the previous scheme requires O(n2)-bit communication and O(n) rounds. On the practical efficiency, we show the performance of our protocol by experiments on the scenario for distributed signatures, which is useful for secure key management on the distributed environment (e.g., distributed ledgers). As one of the cases, our implementation performs a modular exponentiation on a 3,072-bit discrete-log group and 256-bit exponent with roughly 300ms, which is an acceptable parameter for 128-bit security, even in the WAN setting.
Secure multi-party computation (MPC) allows participating parties to jointly compute a function over their inputs while keeping them private. In particular, MPC based on additive secret sharing has been widely studied as a tool to obtain efficient protocols secure against a dishonest majority, including the important two-party case. In this paper, we propose a two-party protocol for an exponentiation functionality based on an additive secret sharing scheme. Our proposed protocol aims to securely compute a public base exponentiation ax mod p for an odd prime p, where the exponent x ∈ ℤp is a (shared) secret and the base a ∈ ℤp is public. Our protocol is based on a new simple but efficient approach involving quotient transfer that allows the parties to perform the most expensive part of the computation locally, but requires the base a ∈ ℤp to be a quadratic residue. To address scenarios where the base does not fulfill this, we combine our exponentiation protocol with a new efficient modulus conversion protocol which might be of independent interest. Even taking into account a potential modulus conversion, our exponentiation protocol only requires 3 rounds and 4 invocations of multiplication.
A secure multi-party computation problem deals with computing a function on any input, in a distributed network, ensuring that no more information is revealed to a player in the computation. New protocols are developed for the following interesting variation on a typical problem of secure multi-party computation: Given secrets shared among a group of players, compute the function value of basic computations, such as interpolation, addition, multiplication or inversion, in the exponent. The protocols can be proven robust and secure in standard computation models.
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.
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.
Secure multi-party computation is a conceptual framework in which distrusting parties engage in a protocol to securely perform a computational task. Depending on the precise model of security, different sets of tasks admit secure protocols. We take a complexity-theoretic approach to studying the inherent difficulty of securely realizing tasks in various standard security models. * We give the first alternate characterization of secure realizability in the framework of universally composable (UC) security. This is the first characterization in any model to consider completely arbitrary computational tasks and completely arbitrary communication channels. * The most long-standing class of computational tasks studied are those in which two parties evaluate a deterministic function. For these tasks, we give the first complete, combinatorial characterizations of secure realizability in the passive, standalone, and universally composable security models, against computationally unbounded adversaries. * Say that a task G has ``as much cryptographic complexity'' as another task F if there is a secure protocol for F that uses access to a secure implementation of G. We show that there is an infinite hierarchy of tasks with strictly increasing cryptographic complexities, with respect to computationally unbounded security. We also show that there exist tasks whose cryptographic complexities are incomparable. * In contrast, we show that under a standard cryptographic assumption, there exist only two distinct levels of cryptographic complexity with respect to polynomial-time security. Every task either has a trivial protocol using plain communication channels, or is complete (i.e., given access to a secure implementation of this task, there are secure protocols for all other tasks). This is the first result to derive a characterization of completeness for a class of arbitrary interactive tasks. In light of these characterizations, the only tasks which are securely realizable in the demanding framework of universal composition are those related to secure communication. Indeed, the framework has been used to define the security of encryption schemes, which has allowed for modular design and analysis of protocols. We consider a similar approach for homomorphic encryption schemes. A homomorphic scheme is one in which anyone can obtain an encryption of f(m_1, ..., m_n), given only the encryptions of unknown messages m_1, ..., m_n, for a specific set of functions f. * We give a construction of a homomorphic encryption scheme in which the allowed homomorphic operation is as full-featured as possible --- namely, one can derive a correctly-distributed encryption of f(m) given an encryption of unknown message m, for some functions f --- yet it is computationally infeasible to generate a ciphertext that is related to other ciphertexts in any other way. Our contributions involve developing new appropriate security definitions as well as new constructions. * We show that schemes with such powerful security guarantees can be used to build conceptually simple, efficient, UC-secure protocols for verifiable computations on encrypted data. We show protocols for two tasks related to aggregating encrypted data.