A nested threshold system to complement Shamir's Secret Sharing (SSS) groups with an arbitrary amount of additional secrets, at no additional storage burden on the part of the shareholders.
Caution
This library is highly experimental cryptographic software, designed for a specialized use-case.
Do not use this code in production.
For usage documentation, see docs.rs.
Consider a SSS group with threshold
The dealer wishes to generate an additional secret
Example: A threshold recovery system stores an encrypted blob of data on a server, while the decryption key is distributed among the members of a SSS group. Contact information for all shareholders is encrypted on the server under a key
This is sort of like nesting one secret sharing scheme inside another, with a potentially different (smaller) threshold.
If shareholder storage and synchronization is not a problem, the simplest solution is to create a second SSS group which distributes the secret
However, there are situations where storing additional shares is not practical.
- What if we need distinct and unrelated secrets for every one of 100,000,000 distinct situations? That would necessecitate storing 100,000,000 + 1 shares with this approach.
- What if the share storage medium demands an extremely dense encoding, such as BIP39?
Instead of storing additional secrets with each shareholder, we will define some fixed constant parameters which shareholders can use in combination with their shares in order to reconstruct the secret
First, let's review our SSS group and its parameters.
Symbol | Meaning |
---|---|
SSS group security threshold. | |
SSS group size. | |
Primary secret shared through SSS. | |
SSS secret sharing polynomial. | |
The input at which |
|
Secondary secret shared using qudoku . |
The secret sharing polynomial
Since
SSS can be extended with Elliptic Curve Cryptography to add support for more complex use cases, such as Verifiable Secret Sharing (VSS). We will make use of the homomorphic properties of Elliptic Curve groups to allow a single SSS group to derive multiple distinct secrets.
For this library, we'll be using the secp256k1 curve. Noteworthy parameters of the curve:
Symbol | Meaning |
---|---|
Prime order of the elliptic curve. | |
Elliptic curve base-point. Multiplying |
Elliptic curve points can be added and subtracted, but not multiplied or divided by one-another. This means that scalar-point multiplication is a one-way operation which cannot be reversed (without a quantum computer).
The SSS protocol designer must first fix a chosen constant point
This point demands an important property: It must have an unknown discrete logarithm with respect to the curve base point
The best way to prove such a point has this property is to derive it using a nothing-up-my-sleeve approach, which demonstrates the point was selected in a way nobody could have chosen it intentionally while knowing its discrete log.
One such example is to generate a point by hashing some honest-looking input data, and then interpreting that hash as the X coordinate of an elliptic curve point. The pseudo-random and unpredictable nature of a secure hash function ensures that the X coordinate is effectively random. This prevents the generator from choosing a specific point which has a known discrete log. An observer can be given the input data, and the hash operation can be repeated to verify the point is indeed random and honestly chosen.
Not all hash outputs are valid X coordinates on the secp256k1 curve though, so you may need to increment the output a couple of times to find a valid curve point.
Once you find a valid X coordinate, you can select either the odd or even parity Y-coordinate which comes along with it - Either are equally honest and usable.
Let
Let
Then
Suppose you are given
Each secret sharing group member possesses an evaluation of
The shareholder doesn't need to store any extra information alongside their share; the fixed point
To distribute the secret
What if the group wishes to ease the minimum security threshold needed to learn
Currently the SSS group needs to send
To reduce this threshold from
These pre-shared evaluations must each use an input
The pre-shared share indexes can be chosen by, for example:
- reserving specific indexes for the pre-shared shares, e.g.
$\{q-1, q-2, ... q-t'\}$ , which the existing shareholders are guaranteed not to be using. - sampling random indexes from
$[1, q)$ . Because$q$ is very large, so collision with a shareholder is very unlikely.
If the SSS dealer is available, they can compute the pre-shares directly, because they know
If not, the shareholders may need to use multi-party computation to issue pre-shares directly to the recipient.
Following our earlier example with the encrypted recovery server, the SSS group would fix
If shareholders wish to pre-arrange a large collection of independent secrets, they can pre-arrange a set of
Technically, no two points on the secp256k1 curve can be co-prime, as common factors always exist, but as long as their common factors are not computable that's good enough for security to hold.
For each point
Warning
Why must all the
Let's assume there are two points
Assuming all