logoalt Hacker News

ezwoodlandyesterday at 10:52 PM1 replyview on HN

Something along the lines of reed-solomon codes could work for you:

If you want to share your password with M family members such that you only need N to agree to recover the original:

Split your password into ordered chunks.

Make a polynomial p, of power N where the p(1) = chunk1, p(2) = chunk2, ...

Evaluate the polynomial at M other points: p(N+1),p(N+2)...

Gives those M new points to your family along with their index (+1,+2,...).

If less than N family members get together, they will not be able to figure out the password much better than guessing. If N get together, they can interpolate their points to form the unique polynomial which will match p. Then evaluate p at p(1),p(2),... to get your original password.

If you put the whole password into 1 chunk, and pad the polynomial with random extra coefficients or points to make the polynomial of sufficient degree, then they get literally no information on the password without having at least N cooperate. If you make multiple chunks then they can do a little correlation between the chunks without knowing the whole thing.

This is sufficiently simple you can even work this out by hand without a computer, though it would be somewhat tedious.


Replies

octoberfranklintoday at 12:16 AM

Reed-Solomon is error correction, not encryption.