zbMATH — the first resource for mathematics

An efficient threshold public key cryptosystem secure against adaptive chosen ciphertext attack. (English) Zbl 0948.94008
Stern, Jacques (ed.), Advances in cryptology - EUROCRYPT ’99. 17th annual Eurocrypt conference, international conference on The theory and application of cryptographic techniques, Prague, Czech Republic, May 2-6, 1999. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 1592, 90-106 (1999).
A threshold public-key cryptosystem (PKC) represents a natural extension of the idea of a PKC in the following sense – instead of a single party holding the private decryption key, there are \(n\) decryption servers, each of which holds a piece of the private decryption key. To decrypt a ciphertext \(c\) a user sends \(c\) to each decryption server, receives a piece of information from each, and uses the pieces collected to recover the cleartext.
Previously, various threshold PKC were proposed, however these proposals required interaction among the servers and the user. Also non-interactive threshold PKC secure against “chosen ciphertext attack” (CCA) has been proposed, in the random-oracle model and under the decisional Diffie-Hellman (DDH) intractability assumption. The random oracle was used both in the proof of security and to eliminate interaction. In the paper a new threshold PKC, provably secure against CCA based on the DDH intractability assumption is presented. The scheme makes no use of random oracles.
The paper begins with brief introduction and survey of its contributions. Then, a new definition of security for threshold PKC is outlined followed by the main section of the paper. The new proposal is based on the recent work by R. Cramer and V. Shoup [Crypto 1998, Lect. Notes Comput. Sci. 1462, 13–25 (1998; Zbl 0931.94018)]. A basic variant of the Cramer-Shoup scheme is first described and then slightly modified and shown to be secure against CCA (assuming the original scheme is secure against CCA). Subsequently the modified scheme is used to build the basic threshold scheme for the case where all servers follow their protocol. The last subsection deals with protecting against actively faulty decryption servers.
For the entire collection see [Zbl 0912.00038].

94A60 Cryptography
Full Text: DOI