Securing threshold cryptosystems against chosen ciphertext attack (Q1601827)

In a threshold cryptosystem the secret key of a public key cryptosystem is shared among a set of decryption servers, so that a quorum of these servers can be used to decrypt a given ciphertext. The article focuses on two important aspects of threshold cryptosystems, namely practicality and security. Particularly, two practical threshold cryptosystems are presented, and their security against a chosen ciphertext attack in the random oracle model is proved. First, after a brief introduction, threshold cryptosystems and their applications are discussed, followed by a survey of constructions of (non-threshold) chosen ciphertext secure cryptosystems. Then difficulties in securing threshold cryptosystems against chosen ciphertext attacks are considered, followed by a brief survey of the random oracle model. This introductory part ends with a description of a simple threshold cryptosystem that has been claimed in several papers to be secure against a chosen ciphertext attack, however the authors argue that these claims are not justified. The authors then present a formal model for a \(k\) out of \(n\) threshold cryptosystem and make precise what is meant by security against chosen ciphertext attack and consistency of decryptions. In the next section basic tools, namely threshold secret sharing and zero-knowledge proof of discrete logarithm identities are reviewed. Then two practical threshold cryptosystems are proposed and their security in the random oracle model is proved. The first scheme is secure assuming the hardness of the computational Diffie-Hellman problem, while the second, more efficient scheme is secure assuming the hardness of the decisional Diffie-Hellman problem. Finally, some implementation issues are briefly discussed and some open problems outlined.