Where can I learn about proven methods for sharing cryptographic keys?

Question

Suppose that a group wants to encrypt some information, then share the encryption key among the group members in a way that requires the consensus of the group to decrypt the information. I'm interested in a variety of scenarios where the breadth of consensus ranges from unanimity to an absolute majority. A useful technique can apply to symmetric keys, private keys, or both.

I could take a crack at rolling my own method, as I'm sure many SO members could. But for the purposes of this question, I am interested only in methods that have been widely published and have withstood scrutiny by expert cryptanalysts. Journal citations are good, but interpretation of academic sources are very useful too.

Answer 1

I have always been fascinated by this secret sharing technique. I've seen code implementing it on the internet, but have never seen actual applications. Shamir's secret sharing The wikipedia article links to some actual code, as well as the original academic article.

Answer 2

What you describe sounds a lot like "secret splitting" (Section 12.1. Introduction to Cyptography. Trappe & Washington. 2nd ed) The basic idea is you can come up with a polynomial that includes your "secret" (a key) as a point on the line. You can give out "shares" by picking other points on this polynomial. Two points define a line of the form f(x) = ax + b, three points define a polynomial of the form f(x) = ax^2 + bx + c, and four points define something of the form f(x) = ax^3 + bx^2 + cx + d, and so on. You can choose a polynomial that includes your secret as a point, and a degree for the polynomial sufficient so that any N people can reconstruct it.

This is the basic idea that is known as the "Shamir threshold scheme."

See wikipedia on Secret Splitting and Shamir's Secret Sharing The wikipedia page has some links to implementations of this idea, including GPL'd code for Windows and UNIX.

Answer 3

This is easy to implement with error-correcting codes. You could use a command-line tool such as par2 (which is not exactly appropriate for this specific purpose btw, as it generates recovery blocks of varying size). Let's say you have (n+m) voters, and want a quorum of n votes. You generate n private keys K₁∘, K₂, ... Kn, and generate m additionnal ECC blocks Pₓ of the same size. That way any n blocks suffice to reconstitute the cipher K₁∘K₂∘...∘Kn

Answer 4

Go here for a discussion of the mathematical basis to Shamir's secret sharing and brief discussion of the type of practical applications that it has. Scroll down the page to the lecture notes on Polynomials and Secret Sharing. It's probably a v. basic overview of the area, but should be quite interesting for you. Discrete Mathematics Notes