threshold_sharing - Threshold Secret Sharing¶

Overview¶

The threshold_sharing module implements threshold secret sharing schemes for distributed cryptographic protocols. It provides both Shamir secret sharing and verifiable secret sharing (VSS) variants including Feldman VSS and Pedersen VSS.

This module is a core component of the DKLS23 threshold ECDSA implementation, enabling secure distribution of private keys among multiple parties where any t-of-n parties can reconstruct the secret or collaboratively sign messages.

Key Features¶

Shamir Secret Sharing: Classic (t, n) threshold scheme with Lagrange interpolation
Feldman VSS: Verifiable secret sharing with public commitments for share verification
Pedersen VSS: Information-theoretically hiding VSS with blinding factors
Share Arithmetic: Add shares for distributed operations (DKG, refresh)
Proactive Security: Refresh shares without changing the underlying secret
Curve Agnostic: Works with any DDH-hard elliptic curve group

Security Properties¶

Threshold Security: Fewer than t shares reveal nothing about the secret
Verifiability (Feldman/Pedersen): Parties can verify their shares are valid
Information-Theoretic Hiding (Pedersen): Even unbounded adversaries cannot learn the secret from commitments
Computational Binding: Shares cannot be forged under the DLP assumption

Use Cases¶

DKLS23 DKG: Distribute key shares during distributed key generation
Threshold Wallets: Split cryptocurrency private keys among custodians
Key Escrow: Securely backup keys with threshold recovery
Proactive Security: Periodically refresh shares to limit exposure window

Example Usage¶

Basic Shamir Sharing:

from charm.toolbox.ecgroup import ECGroup, ZR
from charm.toolbox.eccurve import secp256k1
from charm.toolbox.threshold_sharing import ThresholdSharing

group = ECGroup(secp256k1)
ts = ThresholdSharing(group)

# Create 2-of-3 threshold shares
secret = group.random(ZR)
shares = ts.share(secret, threshold=2, num_parties=3)

# Reconstruct from any 2 shares
recovered = ts.reconstruct({1: shares[1], 3: shares[3]}, threshold=2)
assert secret == recovered

Feldman VSS (Verifiable):

from charm.toolbox.ecgroup import ECGroup, ZR, G
from charm.toolbox.eccurve import secp256k1
from charm.toolbox.threshold_sharing import ThresholdSharing

group = ECGroup(secp256k1)
ts = ThresholdSharing(group)
g = group.random(G)  # Generator

# Create shares with verification commitments
secret = group.random(ZR)
shares, commitments = ts.share_with_verification(secret, g, threshold=2, num_parties=3)

# Each party can verify their share
for party_id in [1, 2, 3]:
    valid = ts.verify_share(party_id, shares[party_id], commitments, g)
    assert valid  # Share is valid

Pedersen VSS (Information-Theoretically Hiding):

from charm.toolbox.threshold_sharing import PedersenVSS

group = ECGroup(secp256k1)
pvss = PedersenVSS(group)
g, h = group.random(G), group.random(G)

secret = group.random(ZR)
shares, blindings, commitments = pvss.share_with_blinding(secret, g, h, threshold=2, num_parties=3)

# Verify with blinding values
valid = pvss.verify_pedersen_share(1, shares[1], blindings[1], commitments, g, h)
assert valid

Share Refresh (Proactive Security):

# Refresh shares without changing the secret
refreshed_shares = ts.refresh_shares(shares, threshold=2)

# Original secret is still recoverable
recovered = ts.reconstruct({1: refreshed_shares[1], 2: refreshed_shares[2]}, threshold=2)
assert secret == recovered

Mathematical Background¶

Shamir’s Scheme: Uses polynomial interpolation where the secret is the constant term of a random polynomial f(x) of degree t-1. Each share is f(i) for party i. Lagrange interpolation recovers f(0) = secret from any t points.

Feldman VSS: Publishes commitments Cⱼ = g^{aⱼ} for polynomial coefficients. Share verification checks: g^{share_i} = ∏ Cⱼ^{i^j}

Pedersen VSS: Uses two generators g, h with unknown discrete log relation. Commitments Cⱼ = g^{aⱼ} · h^{bⱼ} hide the coefficients information-theoretically.

API Reference¶

Threshold Secret Sharing for DKLS23 and Threshold ECDSA

From: “How to Share a Secret” (Shamir Secret Sharing)
By:   Adi Shamir
Published: Communications of the ACM, 1979
URL:  https://dl.acm.org/doi/10.1145/359168.359176

Feldman VSS from:
“A Practical Scheme for Non-interactive Verifiable Secret Sharing”
By:   Paul Feldman
Published: FOCS 1987
URL:  https://ieeexplore.ieee.org/document/4568297

Pedersen Commitments from:
“Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing”
By:   Torben Pryds Pedersen
Published: CRYPTO 1991
URL:  https://link.springer.com/chapter/10.1007/3-540-46766-1_9

type: secret sharing
setting: Elliptic Curve group
assumption: DLP (for Feldman VSS)

This module extends Shamir secret sharing for threshold ECDSA requirements, providing Feldman VSS, Pedersen commitments, and EC group element support.

class threshold_sharing.PedersenVSS(groupObj: Any)[source]¶

Bases: ThresholdSharing

Pedersen VSS with information-theoretic hiding

Uses two generators g, h for commitments where the discrete log relationship between g and h is unknown. This provides unconditional hiding of the secret, unlike Feldman VSS.

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> pvss = PedersenVSS(group)
>>> g = group.random(G)
>>> h = group.random(G)
>>> secret = group.random(ZR)
>>> shares, blindings, comms = pvss.share_with_blinding(secret, g, h, 2, 3)
>>> pvss.verify_pedersen_share(1, shares[1], blindings[1], comms, g, h)
True
>>> pvss.verify_pedersen_share(2, shares[2], blindings[2], comms, g, h)
True
>>> pvss.verify_pedersen_share(3, shares[3], blindings[3], comms, g, h)
True
>>> recovered = pvss.reconstruct({1: shares[1], 2: shares[2]}, 2)
>>> secret == recovered
True

combine_pedersen_commitments(commitments_list: List[List[Any]]) → List[Any][source]¶

Combine multiple Pedersen commitments (for DKG)

When multiple dealers contribute shares, their commitments can be combined element-wise.

Args:: commitments_list: List of commitment lists from different dealers
Returns:: Combined commitments list

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> pvss = PedersenVSS(group)
>>> g, h = group.random(G), group.random(G)
>>> s1, s2 = group.random(ZR), group.random(ZR)
>>> _, _, comms1 = pvss.share_with_blinding(s1, g, h, 2, 3)
>>> _, _, comms2 = pvss.share_with_blinding(s2, g, h, 2, 3)
>>> combined = pvss.combine_pedersen_commitments([comms1, comms2])
>>> len(combined) == len(comms1)
True

share_with_blinding(secret: Any, g: Any, h: Any, threshold: int, num_parties: int) → Tuple[Dict[int, Any], Dict[int, Any], List[Any]][source]¶

Share with Pedersen commitments (information-theoretically hiding)

Creates two polynomials: - f(x) with f(0) = secret for the actual shares - r(x) with r(0) = random blinding for hiding

Commitments are C_j = g^{a_j} * h^{b_j} where a_j, b_j are coefficients of f and r respectively.

Args:: secret: The secret to share (ZR element) g: First generator point h: Second generator point (discrete log to g unknown) threshold: Minimum shares needed to reconstruct num_parties: Total number of parties
Returns:: Tuple of (shares_dict, blindings_dict, commitments_list) - shares_dict: {party_id: share_value} - blindings_dict: {party_id: blinding_value} - commitments_list: [C_0, C_1, …, C_{t-1}]

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> pvss = PedersenVSS(group)
>>> g, h = group.random(G), group.random(G)
>>> secret = group.random(ZR)
>>> shares, blindings, comms = pvss.share_with_blinding(secret, g, h, 2, 4)
>>> all(pvss.verify_pedersen_share(i, shares[i], blindings[i], comms, g, h)
...     for i in range(1, 5))
True

verify_pedersen_share(party_id: int, share: Any, blinding: Any, commitments: List[Any], g: Any, h: Any) → bool[source]¶

Verify a share against Pedersen commitments

Checks that g^{share} * h^{blinding} == prod_{j=0}^{t-1} C_j^{i^j}

Args:: party_id: The party’s identifier (1 to n) share: The share value (ZR element) blinding: The blinding value (ZR element) commitments: List of Pedersen commitments [C_0, …, C_{t-1}] g: First generator point h: Second generator point
Returns:: True if share is valid, False otherwise

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> pvss = PedersenVSS(group)
>>> g, h = group.random(G), group.random(G)
>>> secret = group.random(ZR)
>>> shares, blindings, comms = pvss.share_with_blinding(secret, g, h, 3, 5)
>>> pvss.verify_pedersen_share(3, shares[3], blindings[3], comms, g, h)
True

class threshold_sharing.ThresholdSharing(groupObj: Any)[source]¶

Bases: object

Enhanced secret sharing for threshold ECDSA

Supports Feldman VSS and operations on EC groups.

Curve Agnostic¶

This implementation supports any elliptic curve group that is DDH-hard. The curve is specified via the groupObj parameter.

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> ts = ThresholdSharing(group)
>>> g = group.random(G)
>>> secret = group.random(ZR)
>>> shares, commitments = ts.share_with_verification(secret, g, threshold=2, num_parties=3)
>>> ts.verify_share(1, shares[1], commitments, g)
True
>>> ts.verify_share(2, shares[2], commitments, g)
True
>>> ts.verify_share(3, shares[3], commitments, g)
True
>>> recovered = ts.reconstruct({1: shares[1], 2: shares[2]}, threshold=2)
>>> secret == recovered
True

add_shares(shares1: Dict[int, Any], shares2: Dict[int, Any]) → Dict[int, Any][source]¶

Add two sets of shares (for additive share combination)

Useful for distributed key generation and refreshing.

Args:: shares1: First dictionary of shares {party_id: share} shares2: Second dictionary of shares {party_id: share}
Returns:: Dictionary of combined shares

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> ts = ThresholdSharing(group)
>>> s1, s2 = group.random(ZR), group.random(ZR)
>>> shares1 = ts.share(s1, 2, 3)
>>> shares2 = ts.share(s2, 2, 3)
>>> combined = ts.add_shares(shares1, shares2)
>>> recovered = ts.reconstruct({1: combined[1], 2: combined[2]}, 2)
>>> recovered == s1 + s2
True

lagrange_coefficient(party_ids: List[int], i: int, x: int = 0) → Any[source]¶

Compute Lagrange coefficient for party i at point x

L_i(x) = prod_{j != i} (x - j) / (i - j)

Args:: party_ids: List of party identifiers in the reconstruction set i: The party for which to compute the coefficient x: The evaluation point (default 0 for secret recovery)
Returns:: The Lagrange coefficient as a ZR element

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> ts = ThresholdSharing(group)
>>> coeff = ts.lagrange_coefficient([1, 2, 3], 1, x=0)
>>> # L_1(0) = (0-2)(0-3) / (1-2)(1-3) = 6/2 = 3

reconstruct(shares: Dict[int, Any], threshold: int) → Any[source]¶

Reconstruct secret from threshold shares using Lagrange interpolation

Args:: shares: Dictionary {party_id: share_value} with at least threshold entries threshold: The threshold used when sharing
Returns:: The reconstructed secret
Raises:: ValueError: If fewer than threshold shares provided

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> ts = ThresholdSharing(group)
>>> secret = group.random(ZR)
>>> shares = ts.share(secret, threshold=3, num_parties=5)
>>> recovered = ts.reconstruct({1: shares[1], 2: shares[2], 4: shares[4]}, 3)
>>> secret == recovered
True

refresh_shares(shares: Dict[int, Any], threshold: int) → Dict[int, Any][source]¶

Refresh shares for proactive security

Generates new shares of zero and adds them to existing shares. The new shares reconstruct to the same secret but are unlinkable to the old shares.

Args:: shares: Dictionary of current shares {party_id: share} threshold: The threshold of the sharing
Returns:: Dictionary of refreshed shares

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> ts = ThresholdSharing(group)
>>> secret = group.random(ZR)
>>> shares = ts.share(secret, 2, 3)
>>> refreshed = ts.refresh_shares(shares, 2)
>>> recovered = ts.reconstruct({1: refreshed[1], 3: refreshed[3]}, 2)
>>> secret == recovered
True

share(secret: Any, threshold: int, num_parties: int) → Dict[int, Any][source]¶

Basic Shamir secret sharing

Args:: secret: The secret to share (ZR element) threshold: Minimum number of shares needed to reconstruct (t) num_parties: Total number of parties (n)
Returns:: Dictionary mapping party_id (1 to n) to share values

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> ts = ThresholdSharing(group)
>>> secret = group.random(ZR)
>>> shares = ts.share(secret, threshold=2, num_parties=4)
>>> len(shares) == 4
True
>>> recovered = ts.reconstruct({1: shares[1], 3: shares[3]}, threshold=2)
>>> secret == recovered
True

share_with_verification(secret: Any, generator: Any, threshold: int, num_parties: int) → Tuple[Dict[int, Any], List[Any]][source]¶

Feldman VSS - shares with public commitments for verification

Creates shares using Shamir’s scheme and publishes commitments C_j = g^{a_j} for each coefficient a_j, allowing verification without revealing the secret.

Args:: secret: The secret to share (ZR element) generator: Generator point g in the EC group (G element) threshold: Minimum shares needed to reconstruct num_parties: Total number of parties
Returns:: Tuple of (shares_dict, commitments_list) - shares_dict: {party_id: share_value} - commitments_list: [C_0, C_1, …, C_{t-1}] where C_j = g^{a_j}

>>> from charm.toolbox.eccurve import secp256k1
>>> group = ECGroup(secp256k1)
>>> ts = ThresholdSharing(group)
>>> g = group.random(G)
>>> secret = group.random(ZR)
>>> shares, comms = ts.share_with_verification(secret, g, 2, 3)
>>> all(ts.verify_share(i, shares[i], comms, g) for i in range(1, 4))
True

verify_share(party_id: int, share: Any, commitments: List[Any], generator: Any) → bool[source]¶

Verify a share against Feldman commitments

Checks that g^{share} == prod_{j=0}^{t-1} C_j^{i^j}

Args:: party_id: The party’s identifier (1 to n) share: The share value to verify (ZR element) commitments: List of Feldman commitments [C_0, …, C_{t-1}] generator: Generator point g used in commitments
Returns:: True if share is valid, False otherwise