group: Implements Shamir and Feldman secret sharing. #348

armfazh · 2022-07-12T06:51:16Z

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

chris-wood

The ergonomics of the API seem good, but I think we can do better with the naming. I'm curious to hear what @cjpatton has to say about the names.

group/secretsharing/ss.go

group/secretsharing/ss_test.go

group/secretsharing/poly.go

group/secretsharing/ss.go

bwesterb · 2022-07-29T10:31:16Z

group/secretsharing/ss.go

+	vecComm := make(SharesCommitment, v.s.T+1)
+	for i, ki := range poly.coeff {
+		vecComm[i] = v.s.G.NewElement()
+		vecComm[i].MulGen(ki)


We need to add a big fat warning. If our secret is a small scalar, it can easily be recovered from the commitment. E.g., it's easy to see if our secret was 2 from vecComm[0].

secretsharing/ss.go

cjpatton

First pass focuses on API, I will look at the math next :)

High level questions about math/polynomial:

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?
If "yes" to (1.), why not define this package around a generic finite field?

It's a bit odd that constructing a new impl of SecretSharing requires a Group. Shamir's (and Feldman's I imagine, but I haven't checked) is well-defined for any finite field, hence this API is more restrictive than necessary.

If this API is only intended for use with cryptographic protocols built from an implementation of Group, then I would make this very clear in the documentation.

math/polynomial/polynomial.go

secretsharing/ss.go

armfazh · 2022-08-26T23:10:24Z

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?

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.

secretsharing/ss.go

armfazh · 2022-10-10T17:54:48Z

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

chris-wood

Functionally, this seems correct, but I think we can still improve the API to make it easier to build things like STAR on top of this.

chris-wood · 2022-10-17T18:49:41Z

math/polynomial/polynomial.go

@@ -53,6 +56,15 @@ func (p Polynomial) Evaluate(x group.Scalar) group.Scalar {
 	return px
 }

+// Coefficient returns a deep-copy of the n-th polynomial's coefficient.
+// Note coefficients are sorted in ascending order with respect to the degree.
+func (p Polynomial) Coefficient(n uint) group.Scalar {


It seems strange that this function takes a uint as input but Degree() outputs an int -- should they use the same type?

The odd case is Degree() returning -1 for the special case of the zero polynomial. We might remove this special case.
@bwesterb what do you think?

secretsharing/ss.go

chris-wood · 2022-10-17T18:56:25Z

secretsharing/ss.go

+// A (t,n) secret sharing allows to split a secret into n shares, such that the
+// secret can be only recovered from any subset of t+1 shares. Returns an error
+// if 0 <= t < n does not hold.
+func NewShamirSecretSharing(g group.Group, t, n uint) (SecretSharing, error) {


I would only pass t as the input here, and let the caller determine how many shares they need in order to split a secret by invoking Shard as many times as needed (though at least t times).

still needs to work on this
~~done~~

chris-wood · 2022-10-17T18:57:40Z

secretsharing/ss.go

+}
+
+// Shard splits the secret into n shares.
+func (s SecretSharing) Shard(rnd io.Reader, secret group.Scalar) []Share {


Can we split this up into the following two functions?

Shard, which takes as input a secret and a (set of points) at which to produce (a set of) share(s).

RandomShard, which takes randomness as input along with the secret and produces a random share.

That would be more useful for the STAR application.

secretsharing/ss.go

chris-wood

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.

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.
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?

secretsharing/ss.go

chris-wood · 2022-10-19T22:27:28Z

secretsharing/ss.go

+// Share represents a share of a secret.
+type Share struct {
+	// ID uniquely identifies a share in a secret sharing instance.
+	ID group.Scalar


Can we rename this to something else? Maybe Input, and maybe rename Value to Output?

armfazh · 2022-11-24T00:17:53Z

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.

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.

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).

…605) This PR contains the following updates: | Package | Type | Update | Change | |---|---|---|---| | [github.com/cloudflare/circl](https://github.com/cloudflare/circl) | indirect | minor | `v1.3.7` -> `v1.6.1` | --- ### CIRCL-Fourq: Missing and wrong validation can lead to incorrect results [GHSA-2x5j-vhc8-9cwm](GHSA-2x5j-vhc8-9cwm) / [GO-2025-3754](https://pkg.go.dev/vuln/GO-2025-3754) <details> <summary>More information</summary> #### Details ##### Impact The CIRCL implementation of FourQ fails to validate user-supplied low-order points during Diffie-Hellman key exchange, potentially allowing attackers to force the identity point and compromise session security. Moreover, there is an incorrect point validation in ScalarMult can lead to incorrect results in the isEqual function and if a point is on the curve. ##### Patches Version 1.6.1 (https://github.com/cloudflare/circl/tree/v1.6.1) mitigates the identified issues. We acknowledge Alon Livne (Botanica Software Labs) for the reported findings. #### Severity Low #### References - [https://github.com/cloudflare/circl/security/advisories/GHSA-2x5j-vhc8-9cwm](https://github.com/cloudflare/circl/security/advisories/GHSA-2x5j-vhc8-9cwm) - [https://github.com/cloudflare/circl](https://github.com/cloudflare/circl) - [https://github.com/cloudflare/circl/tree/v1.6.1](https://github.com/cloudflare/circl/tree/v1.6.1) This data is provided by [OSV](https://osv.dev/vulnerability/GHSA-2x5j-vhc8-9cwm) and the [GitHub Advisory Database](https://github.com/github/advisory-database) ([CC-BY 4.0](https://github.com/github/advisory-database/blob/main/LICENSE.md)). </details> --- ### CIRCL-Fourq: Missing and wrong validation can lead to incorrect results in github.com/cloudflare/circl [GHSA-2x5j-vhc8-9cwm](GHSA-2x5j-vhc8-9cwm) / [GO-2025-3754](https://pkg.go.dev/vuln/GO-2025-3754) <details> <summary>More information</summary> #### Details CIRCL-Fourq: Missing and wrong validation can lead to incorrect results in github.com/cloudflare/circl #### Severity Unknown #### References - [https://github.com/cloudflare/circl/security/advisories/GHSA-2x5j-vhc8-9cwm](https://github.com/cloudflare/circl/security/advisories/GHSA-2x5j-vhc8-9cwm) - [https://github.com/cloudflare/circl/tree/v1.6.1](https://github.com/cloudflare/circl/tree/v1.6.1) This data is provided by [OSV](https://osv.dev/vulnerability/GO-2025-3754) and the [Go Vulnerability Database](https://github.com/golang/vulndb) ([CC-BY 4.0](https://github.com/golang/vulndb#license)). </details> --- ### Release Notes <details> <summary>cloudflare/circl (github.com/cloudflare/circl)</summary> ### [`v1.6.1`](https://github.com/cloudflare/circl/releases/tag/v1.6.1): CIRCL v1.6.1 [Compare Source](cloudflare/circl@v1.6.0...v1.6.1) #### CIRCL v1.6.1 - Fixes some point checks on the FourQ curve. - Hybrid KEM fails on low-order points. ##### What's Changed - kem/hybrid: ensure X25519 hybrids fails with low order points by [@Lekensteyn](https://github.com/Lekensteyn) in cloudflare/circl#541 - .github: Use native ARM64 builders instead of QEMU by [@Lekensteyn](https://github.com/Lekensteyn) in cloudflare/circl#542 - Fixes several errors on twisted Edwards curves. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#545 - Release v1.6.1 by [@armfazh](https://github.com/armfazh) in cloudflare/circl#546 **Full Changelog**: cloudflare/circl@v1.6.0...v1.6.1 ### [`v1.6.0`](https://github.com/cloudflare/circl/releases/tag/v1.6.0): CIRCL v1.6.0 [Compare Source](cloudflare/circl@v1.5.0...v1.6.0) #### CIRCL v1.6.0 ##### New! - [Prio3](https://github.com/cloudflare/circl/blob/main/vdaf/prio3) Verifiable Distributed Aggregation Function ([draft-irtf-cfrg-vdaf](https://datatracker.ietf.org/doc/draft-irtf-cfrg-vdaf/)). - [X-Wing](https://github.com/cloudflare/circl/blob/main/kem/xwing): general-purpose hybrid post-quantum KEM ([draft-connolly-cfrg-xwing-kem](https://datatracker.ietf.org/doc/draft-connolly-cfrg-xwing-kem/)) ##### What's Changed - Add OIDs to ML-DSA by [@bwesterb](https://github.com/bwesterb) in cloudflare/circl#519 - Adds Prio3 a set of verifiable distributed aggregation functions. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#522 - Run semgrep cronjob only in upstream repository. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#526 - X-Wing PQ/T hybrid by [@bwesterb](https://github.com/bwesterb) in cloudflare/circl#471 - ckem: move crypto/elliptic to crypto/ecdh by [@MingLLuo](https://github.com/MingLLuo) in cloudflare/circl#529 - hpke: Update HPKE code to use ecdh stdlib package. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#530 - prio3: Adds polynomial multiplication using NTT by [@armfazh](https://github.com/armfazh) in cloudflare/circl#532 - Add Prio3 in readme. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#527 ##### New Contributors - [@MingLLuo](https://github.com/MingLLuo) made their first contribution in cloudflare/circl#529 **Full Changelog**: cloudflare/circl@v1.5.0...v1.6.0 ### [`v1.5.0`](https://github.com/cloudflare/circl/releases/tag/v1.5.0): CIRCL v1.5.0 [Compare Source](cloudflare/circl@v1.4.0...v1.5.0) ### CIRCL v1.5.0 **New:** ML-DSA, Module-Lattice-based Digital Signature Algorithm. ##### What's Changed - kem: add X25519MLKEM768 TLS hybrid KEM by [@bwesterb](https://github.com/bwesterb) in cloudflare/circl#510 - Create semgrep.yml by [@hrushikeshdeshpande](https://github.com/hrushikeshdeshpande) in cloudflare/circl#514 - repo: Some fixes reported by CodeQL by [@armfazh](https://github.com/armfazh) in cloudflare/circl#515 - Add ML-DSA (FIPS204) by [@bwesterb](https://github.com/bwesterb) in cloudflare/circl#480 - sign/mldsa: Add test for ML-DSA signature verification. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#517 - Release v1.5.0 by [@armfazh](https://github.com/armfazh) in cloudflare/circl#518 ##### New Contributors - [@hrushikeshdeshpande](https://github.com/hrushikeshdeshpande) made their first contribution in cloudflare/circl#514 **Full Changelog**: cloudflare/circl@v1.4.0...v1.5.0 ### [`v1.4.0`](https://github.com/cloudflare/circl/releases/tag/v1.4.0): CIRCL v1.4.0 [Compare Source](cloudflare/circl@v1.3.9...v1.4.0) ### CIRCL v1.4.0 ##### Changes New: ML-KEM compatible with FIPS-203. ##### Commit History - eddilithium3: fix typos by [@bwesterb](https://github.com/bwesterb) in cloudflare/circl#503 - Add ML-KEM (FIPS 203). by [@bwesterb](https://github.com/bwesterb) in cloudflare/circl#470 - Add ML-KEM decapsulation key check. by [@bwesterb](https://github.com/bwesterb) in cloudflare/circl#507 - Preparing for release v1.4.0 by [@armfazh](https://github.com/armfazh) in cloudflare/circl#508 **Full Changelog**: cloudflare/circl@v1.3.9...v1.4.0 ### [`v1.3.9`](https://github.com/cloudflare/circl/releases/tag/v1.3.9): CIRCL v1.3.9 [Compare Source](cloudflare/circl@v1.3.8...v1.3.9) #### CIRCL v1.3.9 ##### Changes: - Fix bug on BLS12381 decoding elements. ##### Commit History - dilithium: fix typo by [@bwesterb](https://github.com/bwesterb) in cloudflare/circl#498 - bls12381: Detects invalid prefix in G1 and G2 serialized elements by [@armfazh](https://github.com/armfazh) in cloudflare/circl#500 - Preparing CIRCL release v1.3.9 by [@armfazh](https://github.com/armfazh) in cloudflare/circl#501 **Full Changelog**: cloudflare/circl@v1.3.8...v1.3.9 ### [`v1.3.8`](https://github.com/cloudflare/circl/releases/tag/v1.3.8): CIRCL v1.3.8 [Compare Source](cloudflare/circl@v1.3.7...v1.3.8) ### CIRCL v1.3.8 #### New - BLS Signatures on top of BLS12-381. - Adopt faster squaring in pairings. - BlindRSA compliant with RFC9474. - (Verifiable) Secret Sharing compatible with the Group interface (elliptic curves). #### Notice - Update on cpabe/tkn20 ciphertexts, read more at https://github.com/cloudflare/circl/wiki/tkn20-Ciphertext-Format-(v1.3.8) ##### What's Changed - Implement Granger-Scott faster squaring in the cyclotomic subgroup. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#449 - Updates avo and CIRCL's own dependency. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#474 - Updating documentation for OPRF package. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#475 - group: removes order method from group interface by [@armfazh](https://github.com/armfazh) in cloudflare/circl#356 - zk/dleq: Adding DLEQ proofs for Qn, the subgroup of squares in (Z/nZ)\* by [@armfazh](https://github.com/armfazh) in cloudflare/circl#451 - Reduce x/crypto and x/sys versions to match Go 1.21 by [@Lekensteyn](https://github.com/Lekensteyn) in cloudflare/circl#476 - Bump GitHub Actions versions and use Go 1.22 and 1.21 by [@Lekensteyn](https://github.com/Lekensteyn) in cloudflare/circl#477 - Adding rule for constant values by [@armfazh](https://github.com/armfazh) in cloudflare/circl#478 - Add BLS signatures over BLS12-381 by [@armfazh](https://github.com/armfazh) in cloudflare/circl#446 - group: Implements Shamir and Feldman secret sharing. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#348 - blindrsa: add support for all variants of RFC9474 by [@armfazh](https://github.com/armfazh) in cloudflare/circl#479 - Explicitly installs Go with version before CodeQL analysis. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#481 - Bumps golangci-lint action by [@armfazh](https://github.com/armfazh) in cloudflare/circl#485 - ecc/bls12381: Ensures pairing operations don't overwrite their input by [@armfazh](https://github.com/armfazh) in cloudflare/circl#494 - Align to the `purego` build tag, removing `noasm` build tag by [@mattyclarkson](https://github.com/mattyclarkson) in cloudflare/circl#492 - cpabe: Serializing ciphertext with 32-bit prefixes. by [@armfazh](https://github.com/armfazh) in cloudflare/circl#490 ##### New Contributors - [@mattyclarkson](https://github.com/mattyclarkson) made their first contribution in cloudflare/circl#492 **Full Changelog**: cloudflare/circl@v1.3.7...v1.3.8 </details> --- ### Configuration 📅 **Schedule**: Branch creation - "" (UTC), Automerge - Between 12:00 AM and 03:59 AM ( * 0-3 * * * ) (UTC). 🚦 **Automerge**: Disabled by config. Please merge this manually once you are satisfied. ♻ **Rebasing**: Whenever PR becomes conflicted, or you tick the rebase/retry checkbox. 🔕 **Ignore**: Close this PR and you won't be reminded about this update again. --- - [ ] If you want to rebase/retry this PR, check this box --- This PR has been generated by [Renovate Bot](https://github.com/renovatebot/renovate).  Reviewed-on: https://code.forgejo.org/forgejo/runner/pulls/605 Reviewed-by: earl-warren <earl-warren@noreply.code.forgejo.org> Co-authored-by: Renovate Bot <bot@kriese.eu> Co-committed-by: Renovate Bot <bot@kriese.eu>

armfazh added the new feature New functionality or module label Jul 12, 2022

armfazh requested review from bwesterb, chris-wood and cjpatton July 12, 2022 06:51

armfazh self-assigned this Jul 12, 2022

chris-wood suggested changes Jul 22, 2022

View reviewed changes

armfazh force-pushed the secretSharing branch from 44925f7 to 50afb71 Compare July 25, 2022 21:33

armfazh requested a review from chris-wood July 25, 2022 21:41

bwesterb requested changes Jul 29, 2022

View reviewed changes

armfazh force-pushed the secretSharing branch from 50afb71 to 175788f Compare July 30, 2022 03:18

armfazh changed the base branch from main to polynomial July 30, 2022 03:18

bwesterb approved these changes Aug 1, 2022

View reviewed changes

secretsharing/ss.go Outdated Show resolved Hide resolved

bwesterb self-requested a review August 1, 2022 08:30

armfazh force-pushed the polynomial branch from 2901247 to dc30325 Compare August 1, 2022 19:51

armfazh force-pushed the secretSharing branch from 175788f to 99716d8 Compare August 1, 2022 20:05

Base automatically changed from polynomial to main August 9, 2022 20:56

armfazh force-pushed the secretSharing branch from 99716d8 to 0122e3d Compare August 16, 2022 17:29

armfazh force-pushed the secretSharing branch 2 times, most recently from b0d84b5 to bb3e3e4 Compare August 24, 2022 22:58

cjpatton requested changes Aug 26, 2022

View reviewed changes

armfazh force-pushed the secretSharing branch from bb3e3e4 to 28db5bf Compare August 26, 2022 22:59

cjpatton reviewed Aug 30, 2022

View reviewed changes

cjpatton reviewed Aug 31, 2022

View reviewed changes

secretsharing/ss.go Outdated Show resolved Hide resolved

armfazh force-pushed the secretSharing branch from da1ac24 to 1b68fea Compare October 10, 2022 20:24

chris-wood suggested changes Oct 17, 2022

View reviewed changes

cjpatton approved these changes Oct 18, 2022

View reviewed changes

secretsharing/ss.go Outdated Show resolved Hide resolved

armfazh force-pushed the secretSharing branch from 98bfada to b0a42cb Compare October 19, 2022 08:38

armfazh requested a review from chris-wood October 19, 2022 08:39

chris-wood reviewed Oct 19, 2022

View reviewed changes

armfazh force-pushed the secretSharing branch from b0a42cb to bbaa64a Compare November 24, 2022 00:18

Implements Shamir and Feldman secret sharing.

9c3d94b

armfazh force-pushed the secretSharing branch from bbaa64a to 9c3d94b Compare November 24, 2022 00:22

armfazh requested a review from chris-wood November 24, 2022 00:24

armfazh merged commit 2a2b195 into main Feb 14, 2024

armfazh deleted the secretSharing branch February 14, 2024 19:32

group: Implements Shamir and Feldman secret sharing. #348

group: Implements Shamir and Feldman secret sharing. #348

Uh oh!

Conversation

armfazh commented Jul 12, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

chris-wood left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

bwesterb Jul 29, 2022

Choose a reason for hiding this comment

Uh oh!

Uh oh!

cjpatton left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

armfazh commented Aug 26, 2022

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

armfazh commented Oct 10, 2022

Uh oh!

chris-wood left a comment

Choose a reason for hiding this comment

Uh oh!

chris-wood Oct 17, 2022

Choose a reason for hiding this comment

Uh oh!

armfazh Oct 18, 2022

Choose a reason for hiding this comment

Uh oh!

Uh oh!

chris-wood Oct 17, 2022

Choose a reason for hiding this comment

Uh oh!

armfazh Oct 18, 2022 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

chris-wood Oct 17, 2022

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

chris-wood left a comment

Choose a reason for hiding this comment

armfazh commented Jul 12, 2022 •

edited

Loading

armfazh Oct 18, 2022 •

edited

Loading