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.

I have been trying to understand how secret sharing methods like Shamir's secret sharing solve the problem of a share revealing information about the secret. I guess there are some random numbers involved, but how is it done mathematically?

share|improve this question
    
can u be more clear on , what is share revealing ? partial key exposure problem ? AFAIK , there is no random value addition –  sashank Nov 12 '13 at 4:31
    
We have a pretty nice tag wiki for the shamir-secret-sharing tag. (At least, I think so -- I wrote it.) It may explain some of the issues you're asking about. If there's still something you don't understand, you may want to edit your question to make it more specific. –  Ilmari Karonen Nov 12 '13 at 11:07
add comment

2 Answers 2

A simple partial explanation addressing your "random value added", too long for a comment. This works well for the trivial case of two shares: Given a secret $x$, split it into $r$ and $x-r$, where $r$ is a random number. Having both shares, you can get the secret by as their sum.

Having only one share, you can do nothing at all, assuming there are no bounds on the variable values. This wouldn't work with integers, so some finite field gets used, e.g. modular arithmetic with a prime modulus $p$. As an example, consider $p=101$ and $r=42$. Now each secret $x$ is equally possible, e.g., $x=10$ corresponds with the other share $x-r = 10-42 = -32 = 69$ (computed modulo 101). This is what information-theoretic security means in this trivial example.

It's easy to extend this for an arbitrary number shares where all of them are needed to reconstruct the secret. I hope it can help you to understand the general method described elsewhere.

share|improve this answer
add comment

Shamir's secret sharing is based on mathematical splitting but not string splitting (as in programming languages) . So a key share cannot be considered same as partial key . Also the security is information-theoretic but not computational meaning no amount of computational power can reveal the complete secret if less than threshold secret shares are available .

http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

play around some of the open source implementations you would get a feel of it .

share|improve this answer
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.