We describe efficient techniques for a number of parties to jointly generate an RSA key. At the end of the protocol an RSA modulus N = pq is publicly known. None of the parties know the factorization of N . In addition a public encryption exponent is publicly known and each party holds a share of the private exponent that enables threshold decryption. Our protocols are efficient in computation and communication. All results are presented in the honest but curious scenario (passive adversary).
We describe efficient techniques for a number of parties to jointly generate an RSA key. At the end of the protocol an RSA modulus N = pq is publicly known. None of the parties know the factorization of N . In addition a public encryption exponent is publicly known and each party holds a share of the private exponent that enables threshold decryption. Our protocols are efficient in computation and communication. All results are presented in the honest but curious scenario (passive adversary).
The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is a complete Paillier (in: EUROCRYPT, pp 223–238, 1999 ) threshold encryption scheme in the two-party setting with security against malicious attacks. We further describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation protocol is comprised of the following subprotocols: ( i ) a distributed protocol for generation of an RSA composite and ( ii ) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite for the public key and is comprised of the following subprotocols: ( i ) a distributed generation of the corresponding secret key shares and ( ii ) a distributed decryption protocol for decrypting according to Paillier.
The problem of generating an RSA composite in a distributed manner without leaking its factorization is particularly challenging and useful in many cryptographic protocols. Our first contribution is the first non-generic fully simulatable protocol for distributively generating an RSA composite with security against malicious behavior. Our second contribution is complete Paillier [Pai99] threshold encryption scheme in the two-party setting with security against malicious behavior. Furthermore, we describe how to extend our protocols to the multiparty setting with dishonest majority. Our RSA key generation is comprised of the following: (i) a distributed protocol for generation of an RSA composite, and (ii) a biprimality test for verifying the validity of the generated composite. Our Paillier threshold encryption scheme uses the RSA composite as public key and is comprised of: (i) a distributed generation of the corresponding secret-key shares and, (ii) a distributed decryption protocol for decrypting according to Paillier.
An efficient two party RSA secret key sharing generation scheme based on a homomorphic encryption, which is semantically secure under the prime residuosity assumption, is proposed in this paper. At the stage of computing RSA modulo N , an initial distributed primality test protocol is used to reduce the computation complexity and increase the probability of N being a two-prime product. On the other aspect, the homomorphic encryption based sharing conversion protocols is devised and adopted in multi-party computing modulus N and secret key d . Comparing to any sharing conversion protocols based on oblivious transfer protocol, the homomorphic encryption based sharing conversion protocols are of high performance. Our scheme resists the passive attack and since a method of verifying the sharing was introduced in, the scheme can resists any cheating behaviors too. Security proof, computation complexity and communication complexity analysis are given at last.
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.
Cryptography grew to be much more than "the study of secret writing". Modern cryptography is concerned with establishing properties such as privacy, integrity and authenticity in protocols for secure communication and computation. This comes at a price: Cryptographic tools usually introduce an overhead, both in terms of communication complexity (that is, number and size of messages transmitted) and computational efficiency (that is, time and memory required). As in many settings communication between the parties involved is the bottleneck, this thesis is concerned with improving communication complexity in cryptographic protocols. One direction towards this goal is scalable cryptography: In many cryptographic schemes currently deployed, the security degrades linearly with the number of instances (e.g. encrypted messages) in the system. As this number can be huge in contexts like cloud computing, the parameters of the scheme have to be chosen considerably larger - and in particular depending on the expected number of instances in the system - to maintain security guarantees. We advance the state-of-the-art regarding scalable cryptography by constructing schemes where the security guarantees are independent of the number of instances. This allows to choose smaller parameters, even when the expected number of instances is immense. - We construct the first scalable encryption scheme with security against active adversaries which has both compact public keys and ciphertexts. In particular, we significantly reduce the size of the public key to only about 3% of the key-size of the previously most efficient scalable encryption scheme. (Gay,Hofheinz, and Kohl, CRYPTO, 2017) - We present a scalable structure-preserving signature scheme which improves both in terms of public-key and signature size compared to the previously best construction to about 40% and 56% of the sizes, respectively. (Gay, Hofheinz, Kohl, and Pan, EUROCRYPT, 2018) Another important area of cryptography is secure multi-party computation, where the goal is to jointly evaluate some function while keeping each party’s input private. In traditional approaches towards secure multi-party computation either the communication complexity scales linearly in the size of the function, or the computational efficiency is poor. To overcome this issue, Boyle, Gilboa, and Ishai (CRYPTO, 2016) introduced the notion of homomorphic secret sharing. Here, inputs are shared between parties such that each party does not learn anything about the input, and such that the parties can locally evaluate functions on the shares. Homomorphic secret sharing implies secure computation where the communication complexity only depends on the size of the inputs, which is typically much smaller than the size of the function. A different approach towards efficient secure computation is to split the protocol into an input-independent preprocessing phase, where long correlated strings are generated, and a very efficient online phase. One example for a useful correlation are authenticated Beaver triples, which allow to perform efficient multiplications in the online phase such that privacy of the inputs is preserved and parties deviating the protocol can be detected. The currently most efficient protocols implementing the preprocessing phase require communication linear in the number of triples to be generated. This results typically in high communication costs, as the online phase requires at least one authenticated Beaver triple per multiplication. We advance the state-of-the art regarding efficient protocols for secure computation with low communication complexity as follows. - We construct the first homomorphic secret sharing scheme for computing arbitrary functions in NC 1 (that is, functions that are computably by circuits with logarithmic depth) which supports message spaces of arbitrary size, has only negligible correctness error, and does not require expensive multiplication on ciphertexts. (Boyle, Kohl, and Scholl, EUROCRYPT, 2019) - We introduce the notion of a pseudorandom correlation generator for general correlations. Pseudorandom correlation generators allow to locally extend short correlated seeds into long pseudorandom correlated strings. We show that pseudorandom correlation generators can replace the preprocessing phase in many protocols, leading to a preprocessing phase with sublinear communication complexity. We show connections to homomorphic secret sharing schemes and give the first instantiation of pseudorandom correlation generators for authenticated Beaver triples at reasonable computational efficiency. (Boyle, Couteau, Gilboa, Ishai, Kohl, and Scholl, CRYPTO, 2019)
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.