group: Implements Shamir and Feldman secret sharing.

[armfazh]

New:

• Introduces Lagrange interpolation [1].
• Shamir's secret sharing [2] on top of the group interface.
• Feldman's verifiable secret sharing [3] on top of the group interface.

References: [1] https://mathworld.wolfram.com/LagrangeInterpolatingPolynomial.html [2] https://dl.acm.org/doi/10.1145/359168.359176 [3] https://ieeexplore.ieee.org/document/4568297

[armfazh]

1. This is defined around the "scalars" of a "group". Do the operations in this package require the scalars to comprise a finite field, or more specifically, the group to have prime order?
2. If "yes" to (1.), why not define this package around a generic finite field?

It's true that secret sharing package can be defined over a finite field. In CIRCL, currently we have no such abstraction. This may require to gather all the field implementations we have in CIRCL. For the purposes of threshold cryptography, we use ecc groups and its set of scalars. At this point we are covering this use case, but we can accommodate more use cases when needed.

[armfazh]

Hi folks, to move forward with this PR, please leave your comments to the latest changes. And approve if you are ok with the current status.

cc: @bwesterb @chris-wood @cjpatton

[armfazh]

I think the interface still isn't quite right, so let me step back and identify the use cases I think are important to solve.

1. A user wants to share a secret with n other users with a recovery threshold of t. This is the classic secret sharing setting. The caller could provide "IDs," or they could be provided at random. I think it's probably easier if they're generated randomly and then the caller assigns these IDs to each user.
2. t users want to independently produce random shares of the same secret such that someone else (a collector or combiner) can recover the secret. Each user has to agree on the secret sharing polynomial independently and non-interactively, i.e., without communication, otherwise this doesn't work. This is the STAR use case.

Based on my understanding of this PR, it looks like (1) is partly addressed (though I would make the API somewhat different so as to not require a monotonically increasing selection of share input [x coordinates]), but (2) does not seem to be addressed.

It's fine if we want to address these in separate PRs, but I'd like to understand what the plan is for both. @armfazh, can you please clarify? In particular, if the plan is to do this in two separate PRs, can you please clarify how the use case in (1) is satisfied?

The code I just pushed satisfy these cases: a) both textbook Shamir and Feldman secret; and b) the case when the share is generated with a prescribed ID (case 1).

For case 2: one solution is that rand (the first param of New(rand, ...)) can be passed as a PRNG with a seed, this makes the internals of the secret sharing deterministic (and reproducible). Other solutions can be adopted later (but not in this PR).