Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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.

share|improve this question
    
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? –  Reid Oct 15 '13 at 4:08
2  
I don't quite understand your question here, what properties do you expect from this "reversed" scheme? –  nightcracker Oct 15 '13 at 7:08
    
added additional details , basically i want to pack two strings first and later i may split them into their original forms –  sashank Oct 15 '13 at 7:16
    
@Reid the resultant combined string length should be less than string length of combined strings concatenated plainly. –  sashank Oct 15 '13 at 7:17
4  
@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. –  Reid Oct 15 '13 at 7:28
show 3 more comments

1 Answer

up vote 1 down vote accepted

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.

share|improve this answer
    
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. –  Reid Oct 17 '13 at 13:13
    
I replaced the odd phrase with some more detailed thoughts. –  tylo Oct 17 '13 at 14:15
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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