Threshold decryption of public-key encryption schemes allows the decryption key to be distributed among trustees. Then, to decrypt the ciphertext it requires at least threshold t trustees to run the decryption protocol in order to get the plain text.

Now, most of the literature is either based on generic multiparty computation (which I am not keen on for some reason) or based on distributed RSA decryption and sharing RSA functions.

Are there any other ways of achieving distributed asymmetric key threshold decryption?
Will elliptic curves be a good choice for distributing the decryption?

  • $\begingroup$ You can create a random symmetric key for each message, apply shamir secret sharing to it (symmetric secret sharing) and then encrypt each share with a different public key. $\endgroup$ Sep 6 '13 at 10:09
  • $\begingroup$ I heard about this technique from a colleague. but could not locate the actual reference of the paper . do u have it ? $\endgroup$
    – sashank
    Sep 6 '13 at 13:12
  • $\begingroup$ No idea if anybody wrote a paper about it. It's just a straight forward and useful combination of asymmetric encryption and shamir secret sharing. I came up with it myself and I expect many others to have done so before me. $\endgroup$ Sep 8 '13 at 13:31
  • $\begingroup$ yes, some other colleague also impromptuly gave me this idea . but some how it is not fitting squarely in my application . thanks anyway ! $\endgroup$
    – sashank
    Sep 8 '13 at 15:03

I assume you say on the threshold encryption scheme, in which a dealer generates $(PK,SK_1,\dots,SK_n)$ and distributes the secret keys to users indexed by $1,\dots,n$, and if a combiner obtains $t$ partially-decrypted ciphertexts, it can retrieve a plaintext.

  • Dodis and Katz showed a generic construction of CCA-secure threshold encryption scheme from a secret sharing scheme and a CCA-secure labeled PKE scheme. See the paper, Dodis and Katz: Chosen-Ciphertext Security of Multiple Encryption (TCC 2005).
  • DDH-based constructions (in ROM) are proposed by Gennaro and Shoup: Securing threshold cryptosystems against chosen ciphertext attack (EUROCRYPT 1998, JoC 2002).
  • You can also find a pairing-based construction in Boneh, Boyen and Halevi: Chosen Ciphertext Secure Public Key Threshold Encryption Without Random Oracles (CT-RSA 2006).

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.