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.

Should the secret message of Shamir's secret-sharing algorithm be interpreted and processed byte by byte? Interpreting it byte by byte makes it easier to process, but in case one of the shareholders decides to tamper with some of the bytes in his possession, this will affect the secret reconstruction. This is a serious risk, and I don't know how it could be prevented.

Would it be sensible, as an alternative, to interpret the secret message as a whole string, instead of byte by byte, transforming it into an integer? In this case, what I am worried about is the huge size of the integer...

share|improve this question
    
A shareholder can tamper with bytes, but not larger integers? I don't understand the point of your question. –  erickson Mar 5 '13 at 18:59
    
As far as I know (which is not much), in case the secret is processed byte by byte, any tampering on some bytes of a share will affect those individual bytes only, while the untampered bytes will be reconstructed correctly. By contrast, interpreting the whole secret as a whole string will not allow for partial tampering, as any tampering will result in the total failure of the secret reconstruction. So, I am wondering which of the two ways is best. Please correct any mistakes in my reasoning, as I am a newbie. –  Penn Mar 5 '13 at 19:34
    
I don't know a lot about it either, so I will offer my opinion (based on having implemented SSS myself) rather than trying to give a real answer: I think that the reason bytes are commonly used in practice is that hard-coding the exponentiation and logarithm tables that are needed is easy, fast, and compact. However, it does limit the number of shares. If you are able to use a "big integer" library to compute the necessary powers and logarithms at runtime, it seems like performance would be adequate for a lot practical applications. –  erickson Mar 5 '13 at 20:06
    
I would also note that there have been some protocols suggested for avoiding attacks by malicious shareholders, where they try to get other share-holders' keys but withhold their own, but I haven't seen any that are bullet-proof. Maybe you could digitally sign shares when they are issued? –  erickson Mar 5 '13 at 20:08
    
Could you show us mathematically what you are talking about doing? –  mikeazo Mar 6 '13 at 13:57
add comment

migrated from stackoverflow.com Mar 6 '13 at 12:15

This question came from our site for professional and enthusiast programmers.

1 Answer

Shamir's secret sharing scheme provides only confidentiality against shareholders who want to try to learn the secret. It does not prevent denial-of-service attacks (or attacks on integrity), where a malicious shareholder submits a bogus share to try to cause the reconstruction of the shares to fail.

If you want security against that sort of attack, don't use Shamir's secret-sharing scheme; there are other schemes that can accomplish that. Verifiable secret sharing schemes do exactly that: they protect against malicious shareholders who submit bogus shares. There are many constructions of verifiable secret sharing schemes in the literature. They do exactly what you want.

Depending upon your application, you may also find threshold cryptography relevant.

share|improve this answer
    
+1 for the reference to the domain of Verifiable secret sharing. I now realize the definition of security for such a protocol is complex: we'd want to be able to designate one (or several cooperating) rogue share holders; enable the share holders to verify their share would 'work' without revealing the shared secret; etc.. Also, my prepend-hash-then-SSS-byte-per-byte scheme is unsafe against an attack by the last share holder to submit her share, and able to build her submission with knowledge from the other shares. I removed my answer. –  fgrieu Mar 7 '13 at 16:47
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.