3
$\begingroup$

I am looking for an asymmetric encryption algorithm, which allows to encrypt a secret with multiple public keys, but to reveal the secret all private keys must be used. You shouldn't be able to tell how many times secret was encrypted from ciphertext length. Ciphertext can be decrypted in reverse sequence as it was encrypted.

RSA would be perfect, but it can only encrypt shorter messages than its key length. And the output is same as key length.

$\endgroup$

migrated from security.stackexchange.com Jul 14 '15 at 12:46

This question came from our site for information security professionals.

4
$\begingroup$

@Erez points to the simple and often good enough solution. In more general terms, you want to split the private key knowledge into several "shares" such that all of them are needed to actually obtain the private key. This calls for a few comments:

  • To make the splitting/sharing easier, you can do things indirectly: generate a random symmetric key K, encrypt the RSA private key with K, and so the splitting over K. Thus, whatever splitting mechanism you use, you need to do it only on K, which is small enough to make it easy and allow for short "shares"; it is also "structureless" (it is a bunch of uniformly random bits) which may avoid some problems.

  • The simplest form of splitting of a secret into n shares is a XOR: for a secret K, generate n-1 random values ri of the same size. Share si is then the value ri, except for the last share sn which is equal to the XOR of K and all the ri together. It is easily shown that the XOR of all shares yields K, and without all the shares you have absolutely no information on the secret K.

    Shamir's secret sharing, that @Erez points to, is just a generalization of that XOR mechanism, to support for a threshold: making n shares such that any t of them (t is lower than n) allow reconstruction, but t-1 shares yield no information whatsoever. When t = n, Shamir's secret sharing becomes the XOR-based mechanism described above.

  • A very nice feature of such "private key split" is that it is entirely done on the key holders side. From the point of view of whoever encrypts, this is plain asymmetric encryption (say, RSA).

  • When you use a private key sharing, there is a potential conceptual problem: though all shares are needed to decrypt the data, the reconstruction must occur "somewhere", and all people who witness the reconstruction learns the complete secret. This gives them the power to decrypt alone other messages encrypted with the same key. Depending on your context, this may or may not be a problem.

    Protocols that solve that issue are called "group decryption" or more generally "multi-party computation". Such a protocol would make share holders participate in a common decryption, such that at the end of the protocol all participants learn the decrypted value, but not the shares from other share holders. There are many variants depending on the threshold you want to achieve, the number of communication rounds, the sizes of individual messages, the number of passively or actively cheating share holders you want to tolerate, whether you want traitors to be revealed... This is a complex research area. Start with this question for some pointers.

$\endgroup$
2
$\begingroup$

You are looking for a secret sharing algorithms. Such schemes are used in products such as PGP, originally Shamir offered a solution, called Shamir's secret sharing algorithm.

$\endgroup$

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.