Key share revocation

Following on from

This is the way I visualize the overall threshold crypto system:


The orange dot is the root key which is the main one used for doing stuff.

The blue dots are key shares, ie what you give to people. Combining enough key shares together will give the root secret.

The blue line, (ie the curve, but I’ll call it a line to avoid confusion with the existing crypto meaning), the blue line is the Key Set. This can be calculated by combining the key shares. Once the Key Set is known it can be used to a) get the root key and b) generate new key shares. This is also called the polynomial.

The x axis is the device id (not a technical term, just a convenient term I made up). You might have your phone at device id 1, your laptop at device id 2, desktop at device id 3, your friends at ids 4-9, etc.

The y axis is the key. Evaluating the polynomial at x=0 gives a certain y value (ie the root key). Evaluating the polynomial at x=2 would give a different y value (ie the key for my laptop).

When creating a k-of-n Key Set, k determines the shape of the line. k=2 is a straight line. k=3 is a parabola. k=4 is a cubic. etc. and n determines how many key shares (blue dots) to actually evaluate and display to the user for distributing.

To revoke a share:

  • calculate a different line that passes through any shares you want to keep (including the root key) but doesn’t pass through any revoked shares. The shape of the new line depends on what you want the new k to be. In some cases the desired shape may not work with the shares you want to retain, so some shares will need to be changed instead of retained. This leaves us with 3 types of shares - retained, changed, revoked.

  • if necessary, use the new line to calculate new shares and distribute them.

This is very simplified so probably created more questions than answers, but writing it up in full detail got too huge and messy. Open to any questions.


How would this not always work? A Nth order poly will always exactly fit N+1 keys.

If you wish to reduce “k” then its not a n+1 poly, its a "k’ poly

“k” is the order of the poly from what @mav said

I was speaking in general terms. k = N + 1 in the quote from @mav above.
‘N’ is not the same as ‘n’.

I don’t see why some valid shared keys would need to be changed instead of retained. Why can’t one just replace a key then and regenerate the polynomial, or fit the key to the existing polynomial (less secure?) followed by a revokation or invalidate an old key you no longer want…

Thats why I mentioned “k” and its quite possible the person removes a share and wants to only have the remaining shares available. So its reduced by one