Shamir's Secret Sharing allows a secret to be split into multiple shares so that it can be reconstructed later.

Is there a way to do the reverse? Can we combine a few secrets first and later split them into their original forms? More clearly: given two strings I want to "pack" them into single secret and later split them into respective strings. (I'm not sure how this would be called in literature.)

The simplest solution I could think of is concatenating all of the secrets and storing their relative positions, later string splitting them based on their positions. This would be too naive and there is no space advantage.

  • 1
    $\begingroup$ Actually, I think concatenating them is likely to be your best bet. Per information theory, if the secrets are uniformly distributed, you pretty much must use as much space as the secrets themselves to store the combined secrets. To avoid encoding the positions, too, you could use a standard secret width (e.g. 128 bits or something). Is there some other property of this combined secret that you're wanting? $\endgroup$
    – Reid
    Oct 15 '13 at 4:08
  • 2
    $\begingroup$ I don't quite understand your question here, what properties do you expect from this "reversed" scheme? $\endgroup$
    – orlp
    Oct 15 '13 at 7:08
  • $\begingroup$ added additional details , basically i want to pack two strings first and later i may split them into their original forms $\endgroup$
    – sashank
    Oct 15 '13 at 7:16
  • $\begingroup$ @Reid the resultant combined string length should be less than string length of combined strings concatenated plainly. $\endgroup$
    – sashank
    Oct 15 '13 at 7:17
  • 4
    $\begingroup$ @sashank: I don't think that's possible; what you're essentially wanting is compression, but good ol' Shannon proved that you can't compress truly-random data and get non-negligble (in the intuitive sense of the word, not the mathematical) space savings. $\endgroup$
    – Reid
    Oct 15 '13 at 7:28

On the information theoretic level you can not get a shorter result than the concatenation if you want to be able to recover the original inputs: If there are $k$ shares from a set with $2^{x}$ elements (represented as $x$ bit array), an injective function requires at least $(2^{x})^k = 2^{xk}$ different function values, which requires at least $xk$ bit. If the function combining the different shares has a shorter function value, it is not injective and you can not recover the original shares.

However, since the chosen string has a specific bit representation, you might be able to work with encodings to save space, e.g. Huffman codes, etc.

You might be able to choose your common secret and shares in a way, where the shares are not compressible by much but the common secret is.

  • $\begingroup$ The phrase 'compress the entropy' is really quite odd, in my opinion. If you're doing lossless compression, and you probably are, then you're really summing up the entropies of each individual secret, not 'compressing' them. $\endgroup$
    – Reid
    Oct 17 '13 at 13:13
  • $\begingroup$ I replaced the odd phrase with some more detailed thoughts. $\endgroup$
    – tylo
    Oct 17 '13 at 14:15

Yes, this paper describes how to do exactly that. But there are caveats. All secrets must be in a base smaller than that of the shares, and each additional secret must be smaller than the previous one.

The specific example in the paper hides 4 binary secrets (of lengths 27, 9, 3, and 1) inside ternary shares of length 27.


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.