Non-interactive CCA-Secure threshold cryptosystems with adaptive security: new framework and constructions

Benoit Libert
Proceedings of the 9th international conference on Theory of Cryptography, Springer-Verlag, Berlin, Heidelberg (2012), pp. 75-93

Abstract

In threshold cryptography, private keys are divided into n shares, each one of which is
given to a di fferent server in order to avoid single points of failure. In the case of threshold public-key encryption, at least t ≤ n servers need to contribute to the decryption process. A threshold primitive is said robust if no coalition of t malicious servers can prevent remaining honest servers from successfully completing private key operations. So far, most practical non-interactive threshold cryptosystems, where no interactive conversation is required among decryption servers, were only proved secure against static corruptions. In the adaptive corruption scenario (where the adversary can corrupt servers at any time, based on its complete view), all existing robust threshold encryption schemes that also resist chosen-ciphertext attacks (CCA) till recently require interaction in the decryption phase. A specific method (in composite order groups) for getting rid of interaction was recently suggested, leaving the question of more generic frameworks and constructions with better security and better
exibility (i.e., compatibility with distributed key generation).

This paper describes a general construction of adaptively secure robust non-interactive threshold cryptosystems with chosen-ciphertext security. We de ne the notion of all-but-one perfectly sound threshold hash proof systems that can be seen as (threshold) hash proof systems with publicly verifi able and simulation-sound proofs. We show that this notion generically implies threshold cryptosystems combining the aforementioned properties. Then, we provide ecient instantiations under well-studied assumptions in bilinear groups (e.g., in such groups of prime order). These instantiations have a tighter security proof and are indeed compatible with distributed key generation protocols.