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.

When performed in binary Galois fields $GF_{2^n}$, Shamir's threshold secret sharing scheme produces shares that are each the same bit-size as the secret. Though the scheme is "perfectly secure" in that less than the requisite number of shares provide no information about the secret, in practice it does leak information about the secret, namely its size (when performed in binary fields).

Would padding the binary representation of the secret (say to a bit-length that is a multiple of 1024, or something) increase the security of the scheme?

If padding improves security, would padding with random bits be better than zero-padding?

If random padding is better, when reconstructing the secret, what is the best way to know how many random bits were added? Should I have the first few bytes be a number that stores this info? Obviously, zero-padding does away with this problem, because any leading zeros can be dropped on reconstructing the secret.

I should add: I'm operating in $GF_{2^8}$, and computing each byte of the shares from a byte of the secret, with different random coefficients for each polynomial, as discussed in this question.

share|improve this question

1 Answer 1

up vote 6 down vote accepted

As you note, Shamir's threshold secret sharing is perfectly secure (or information theoretically secure), yet does leak some information about the size of the secret (same thing with one-time pad).

If you are worried about leaking some information about the size of the secret, then padding could be used to lower the information leakage (instead of knowing that say the secret is 32 bits, the attacker would now know that the secret is no larger than say 1024 bits, something along those lines). If leaking the size of the secret is a problem, then this indeed increases the security of the scheme.

Padding with random bits vs zero-padding would make no difference in security. The secret is already perfectly secure (except for the size of it). Zero-padding hides the length just as well as random padding.

So, what if the secret starts with a zero bit? One thing to do (and this works with random padding too) would be to prepend the length of the padding to the secret. Other techniques would work too.

share|improve this answer

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.