Re: Bitwise File Shredding

[blokhead]

From an information theory perspective, splitting the file isn't helping as much as you think, since each chunk is only 1/8th the size of the original file. In your scheme, each chunk gives some information about the source file. In fact, it gives exactly 1/8th of the possible information of the source file.

An area of cryptography called threshold secret sharing gives methods for dividing a "secret" into chunks distributed among n players such that any (t-1) or fewer pieces together give no information about the secret (they constitute entirely random information), but any t pieces together can reassemble the secret. In order for this to happen, the t^th chunk had to contain as much information as the entire secret, so it had to be at least as large.

Secret sharing schemes are most often used for distributed signatures. A committee has a public key and shares the corresponding private key using threshold secret sharing, so that official statements can't be cryptographically signed unless more than half of the committee members agree to sign.

So in your case, encrypting the source, splitting, and then encrypting the pieces may help the case, but it's shaky ground from a theoretical standpoint.. You're probably no better off than just encrypting the source file without splitting it. If you really want to gain theoretical ground by splitting the file up, you should look into existing secret sharing schemes (wikipedia). With these, there's little need to encrypt the chunks, and (physically) separating the chunks has really helped.

[QM]

In order for this to happen, the t^th chunk had to contain as much information as the entire secret, so it had to be at least as large.

Excuse me if I'm wrong, but I thought the idea was that any t chunks could be combined to restore the original, and that all chunks were similar, i.e., same size, information content, etc.

But perhaps we are in violent agreement?

[blokhead]

Right, that's exactly the point, although I should have made it more explicit. The last chunk must contain as much information as the entire original message. But since any chunk could be the "last chunk," all chunks have to be at least as large as the original message.

But they needn't be the same size (well, depending on how you look at it). In some RSA threshold signatures, the secret key d is split into random integers within a range of {-A, ..., A} (for some A much bigger than the valid range of d) so that all the shares add up to d. Some shares may certainly be much smaller than others, and you could store them in fewer bits. But the fact that each key could be as large as A means you have no information about the secret key by knowing all but one share -- the last share could be large enough that adding it onto the current sum can yield every valid choice of d with equal probability.

However, if a participant publicly announced that his share of the secret could be stored in a very small number of bits, you may be able to get information about the secret if you have all the shares but his -- you may know that the secret d must lie in a smaller range of valid choices.

[jdklueber]

I knew that my algorithm couldn't have been as spiffy as it seemed, and I knew that if I posted it, someone would be able to point me towards what I'm missing. :) Thank you for that.

If nothing else, though, this has certainly been an interesting and educational exercise. And, I've found out the correct term to google on for this class of software: "Key Sharing". I had googled all over the place to find out if someone had already done what I was trying to do, or found an even better scheme. Just didn't know the right terminology. That blasted self-taught thing bites me sometimes. ;-)

Thanks!!