MPC-LSS Linear Secret Sharing

See also: LP-14, LP-13, LP-INDEX

Abstract

This proposal introduces the Linear Secret Sharing Scheme (LSS) implementation in Lux Network's threshold cryptography suite. LSS is a foundational threshold signature protocol that enables dynamic resharing - the ability to change the participant set and threshold without changing the public key. This capability is crucial for long-lived systems where validator sets change over time.

Enhancement over Original Paper: While Vishnu's original LSS paper described a trusted dealer setup, our implementation enhances this with a fully distributed key generation (DKG) protocol, eliminating any single point of trust. This makes LSS suitable for trustless environments while maintaining all dynamic resharing capabilities.

LSS complements the CGG21 (CMP) protocol described in LP-14 by providing a simpler, more flexible approach to threshold signatures with unique dynamic properties not available in ECDSA-based schemes.

Motivation and Rationale

While CGG21/CMP provides state-of-the-art threshold ECDSA with identifiable aborts, there are scenarios where a simpler, more flexible approach is beneficial:

1. Dynamic Participant Sets: LSS uniquely supports changing the set of participants (adding/removing parties) while maintaining the same public key
2. Threshold Flexibility: The threshold can be adjusted dynamically without regenerating keys
3. Protocol Simplicity: LSS uses straightforward polynomial secret sharing without complex MPC protocols
4. Foundation for Higher Protocols: LSS serves as a building block for more complex threshold schemes

These properties make LSS ideal for:

• Validator rotation in blockchain networks
• Long-lived custody solutions where signers change
• Disaster recovery scenarios requiring participant replacement
• Gradual migration between signer sets

Technical Specification

Core Concepts

LSS is based on Shamir's Secret Sharing using polynomial interpolation over a finite field. The key innovation is the resharing protocol that enables dynamic reconfiguration.

Mathematical Foundation

Given a secret s and threshold t:

1. Construct a random polynomial f(x) of degree t-1 where f(0) = s
2. Each party i receives share f(i)
3. Any t parties can reconstruct s using Lagrange interpolation
4. The public key Y = s·G remains constant across resharing

Key Properties

• Information Theoretic Security: No computational assumptions required for secrecy
• Perfect Secrecy: Fewer than t shares reveal nothing about the secret
• Homomorphic: Operations on shares correspond to operations on secrets
• Verifiable: Using Feldman VSS, shares can be verified without revealing the secret

Protocol Phases

1. Distributed Key Generation (DKG)

LSS implements fully distributed key generation without any trusted dealer:

Input: Parties P = {p₁, ..., pₙ}, threshold t
Output: Share sᵢ for each party, public key Y

Round 1 - Polynomial Generation & Commitment:
Each party pᵢ:
1. Generate random secret sᵢ and polynomial fᵢ(x) of degree t-1 where fᵢ(0) = sᵢ
2. Compute commitments Cᵢⱼ = fᵢ(j)·G for each party j
3. Generate chain key for session binding
4. Broadcast commitments to all parties

Round 2 - Share Distribution:
Each party pᵢ:
1. Verify received commitments from all parties
2. Compute shares sᵢⱼ = fᵢ(j) for each party j
3. Send encrypted share sᵢⱼ to party pⱼ

Round 3 - Share Aggregation & Verification:
Each party pᵢ:
1. Verify received shares: sⱼᵢ·G ?= Cⱼᵢ
2. Compute final share: xᵢ = Σⱼ sⱼᵢ
3. Compute public key: Y = Σⱼ Cⱼ₀
4. Store configuration with share xᵢ and public key Y

Output: Distributed key with no single party knowing the secret

This DKG protocol ensures:

• No Trusted Dealer: Secret is generated collectively
• Verifiability: All shares can be verified using commitments
• Robustness: Protocol completes despite t-1 malicious parties

2. Signing

Input: Message m, signers S ⊆ P with |S| ≥ t
Output: Schnorr signature (R, z)

1. Nonce Generation:
   Each signer i ∈ S:
   a. Generate random kᵢ
   b. Compute Rᵢ = kᵢ·G
   c. Broadcast Rᵢ

2. Aggregation:
   a. R = Σᵢ∈S λᵢ·Rᵢ (λᵢ are Lagrange coefficients)
   b. c = H(R, Y, m)

3. Response:
   Each signer i:
   a. Compute zᵢ = kᵢ + c·λᵢ·sᵢ
   b. Broadcast zᵢ

4. Combine:
   z = Σᵢ∈S zᵢ

5. Output: (R, z)

3. Dynamic Resharing (Unique to LSS)

Input: Old parties P_old, new parties P_new, new threshold t_new
Output: New shares for P_new, same public key Y

1. Share Distribution:
   Each party pᵢ ∈ P_old:
   a. Create polynomial fᵢ(x) where fᵢ(0) = sᵢ_old
   b. Compute shares sᵢⱼ = fᵢ(j) for each pⱼ ∈ P_new
   c. Send sᵢⱼ to pⱼ with commitments

2. Share Aggregation:
   Each party pⱼ ∈ P_new:
   a. Collect shares from t_old parties in P_old
   b. Verify shares using commitments
   c. Compute new share sⱼ_new = Σᵢ sᵢⱼ

3. Verification:
   a. Verify public key unchanged: Y_new = Y_old
   b. Run verification protocol among P_new

4. Output: New shares {sⱼ_new} for P_new

Implementation Details

Configuration Structure

type Config struct {
    ID              party.ID
    Threshold       int
    SecretKeyShare  curve.Scalar
    VerificationKey curve.Point  // Public key Y
    PartyIDs        []party.ID
    Generation      uint32       // Incremented on reshare
}

Security Parameters

• Field: secp256k1 scalar field (256-bit prime)
• Hash Function: BLAKE3 for commitments and challenges
• Encryption: ECIES for share transmission
• Verification: Feldman VSS with Pedersen commitments

Comparison with Other Protocols

Feature	LSS	CGG21/CMP	FROST	GG18
Signature Type	Schnorr	ECDSA	Schnorr	ECDSA
Dynamic Resharing	✅ Native	❌	❌	❌
Threshold Change	✅	❌	❌	❌
Participant Change	✅	Limited	❌	❌
Rounds (Sign)	2	5-8	2	9
Identifiable Abort	✅ VSS	✅	❌	❌
Complexity	Low	High	Medium	High
Proactive Security	✅	✅	Limited	Limited

Security Model

Assumptions

1. Honest Majority: At most t-1 corrupted parties
2. Synchronous Network: Messages delivered within known time bounds
3. Secure Channels: Authenticated encryption between parties
4. Random Oracle: Hash functions modeled as random oracles

Security Properties

1. Unforgeability: Adversary cannot forge signatures without t shares
2. Robustness: Protocol completes despite t-1 malicious parties
3. Privacy: Share distribution reveals nothing about the secret
4. Forward Security: Past signatures remain secure after resharing

Threat Mitigation

• Share Leakage: Regular resharing invalidates old shares
• Adaptive Corruption: Proactive refresh limits corruption window
• Network Attacks: Authenticated channels prevent MITM
• Replay Attacks: Generation counter prevents share reuse

Integration with Lux Network

Use Cases

1. Validator Rotation: Seamless rotation of consensus validators
2. Bridge Custody: Dynamic bridge operator management
3. DAO Treasury: Evolving multisig with changing members
4. Recovery Protocols: Replace lost/compromised shares

Compatibility

LSS integrates with existing Lux infrastructure:

• Compatible with T-Chain for MPC operations
• Works alongside CGG21 for ECDSA when needed

Specification

The normative protocol is defined in Technical Specification and Protocol Phases above (DKG, Signing, Dynamic Resharing) including data types and verification steps. Implementations MUST follow those algorithms and parameter choices.

Rationale

LSS is chosen for its native dynamic resharing: validator sets and thresholds can change without rotating public keys. This simplifies long‑lived operations, reduces operational risk, and complements ECDSA‑focused protocols (CGG21) with a simpler Schnorr‑style alternative.

Backwards Compatibility

This LP introduces an additive threshold scheme. Existing components continue to operate unchanged. Systems MAY adopt LSS gradually; keys and interfaces are versioned via the Generation counter to avoid ambiguity during migrations.

Security Considerations

Follow the Security Model above. In particular: use authenticated channels, enforce generation counters to prevent replay, schedule proactive resharing to limit exposure, and verify shares via VSS commitments. Parameter choices (field, hash, encryption) MUST match those stated.

• Supports same key management infrastructure
• Uses common networking and storage layers

Migration Path

For systems currently using static threshold schemes:

1. Generate LSS shares for existing key
2. Run parallel signing during transition
3. Gradually rotate out old system
4. Enable dynamic features once stable

Test Cases

Unit Tests

func TestDistributedKeyGeneration(t *testing.T) {
    // Test DKG with 3-of-5 threshold
    parties := []party.ID{"p1", "p2", "p3", "p4", "p5"}
    threshold := 3

    configs, err := lss.RunDKG(parties, threshold)
    require.NoError(t, err)
    require.Len(t, configs, 5)

    // Verify all parties have same public key
    pubKey := configs[0].VerificationKey
    for _, cfg := range configs {
        require.True(t, cfg.VerificationKey.Equal(pubKey))
    }
}

func TestThresholdSigning(t *testing.T) {
    // Generate keys for 3-of-5
    configs := setupTestConfigs(t, 5, 3)
    message := []byte("test message")

    // Sign with exactly threshold parties
    signers := configs[:3]
    sig, err := lss.Sign(signers, message)
    require.NoError(t, err)

    // Verify signature
    valid := lss.Verify(configs[0].VerificationKey, message, sig)
    require.True(t, valid)
}

func TestDynamicResharing(t *testing.T) {
    // Initial 3-of-5
    oldConfigs := setupTestConfigs(t, 5, 3)
    pubKey := oldConfigs[0].VerificationKey

    // Reshare to new 4-of-7
    newParties := []party.ID{"n1", "n2", "n3", "n4", "n5", "n6", "n7"}
    newConfigs, err := lss.Reshare(oldConfigs[:3], newParties, 4)
    require.NoError(t, err)

    // Verify public key unchanged
    require.True(t, newConfigs[0].VerificationKey.Equal(pubKey))

    // Verify new threshold works
    message := []byte("after reshare")
    sig, err := lss.Sign(newConfigs[:4], message)
    require.NoError(t, err)
    require.True(t, lss.Verify(pubKey, message, sig))
}

func TestShareVerification(t *testing.T) {
    // Test Feldman VSS verification
    configs := setupTestConfigs(t, 5, 3)

    for _, cfg := range configs {
        valid := lss.VerifyShare(cfg)
        require.True(t, valid, "share verification failed for %s", cfg.ID)
    }
}

func TestByzantineResilience(t *testing.T) {
    // Test with malicious parties providing invalid shares
    configs := setupTestConfigs(t, 5, 3)

    // Corrupt one party's share
    configs[0].SecretKeyShare = curve.NewScalar().Random()

    // Signing should fail with identifiable abort
    _, err := lss.Sign(configs[:3], []byte("test"))
    require.Error(t, err)
    require.Contains(t, err.Error(), "invalid share")
}

Integration Tests

1. End-to-End DKG Flow: Full distributed key generation with network simulation
2. Cross-Protocol Verification: LSS signatures verified by external Schnorr implementations
3. Resharing Migration: Complete validator set rotation with zero downtime
4. Concurrent Operations: Multiple signing sessions with same key
5. Network Partition Recovery: Handling temporary disconnections during protocol

Test Coverage Summary

Our implementation achieves:

• 100% test coverage with zero skipped tests
• 75+ test functions covering all operations
• Benchmarks showing 2-round signing < 100ms
• Stress tests up to 100 parties
• Byzantine tests with malicious parties

Key test scenarios:

• Keygen with various (n,t) parameters
• Signing with exact threshold and all parties
• Resharing with party addition/removal
• Threshold changes (increase/decrease)
• Concurrent operations
• Network failures and recovery

Future Enhancements

Planned Features

1. Asynchronous Resharing: Support for asynchronous networks
2. Weighted Shares: Different parties hold different share weights
3. Hierarchical Sharing: Multi-level threshold structures
4. Cross-Protocol Migration: Convert between LSS and other schemes

Research Directions

1. Post-Quantum LSS: Integration with lattice-based schemes
2. Non-Interactive Resharing: Reduce communication rounds
3. Adaptive Security: Full UC security proofs
4. Efficiency Optimizations: Batch verification, preprocessing

Implementation Status

The LSS protocol is fully implemented in the Lux threshold cryptography library:

• Repository: github.com/luxfi/threshold
• Package: protocols/lss
• Status: Production-ready with comprehensive testing
• Files: 64 Go files across 9 subdirectories
• Benchmarks: Available for all operations

File Inventory

protocols/lss/
├── lss.go                 # Entry points: Keygen(), Sign(), Refresh()
├── factory.go             # Protocol factory creation
├── suite.go               # Test suite utilities
├── rollback.go            # Rollback/recovery operations
├── lss_cmp.go             # CMP integration (ECDSA signatures)
├── lss_frost.go           # FROST integration (Schnorr signatures)
├── lss_*_test.go          # Test suites (integration, benchmark, threshold)
├── config/
│   ├── config.go          # Config struct with shares and verification data
│   └── marshal.go         # JSON/binary serialization
├── keygen/
│   ├── keygen.go          # Distributed key generation StartFunc
│   └── round1.go - round3.go  # 3-round DKG protocol
├── sign/
│   └── sign.go            # Threshold signing protocol
├── reshare/
│   └── reshare.go         # Dynamic resharing to new parties/threshold
├── dealer/
│   └── dealer.go          # Trusted dealer mode (optional, for testing)
├── jvss/
│   └── jvss.go            # Joint Verifiable Secret Sharing
├── coordinator/
│   └── coordinator.go     # Protocol coordination utilities
└── adapters/
    └── adapters.go        # Protocol adapter interfaces

Key Components

Component	Path	Purpose
Config	protocols/lss/config/	Configuration types and serialization
Keygen	protocols/lss/keygen/	Distributed key generation (3 rounds)
Sign	protocols/lss/sign/	Threshold Schnorr signing
Reshare	protocols/lss/reshare/	Dynamic resharing protocol
JVSS	protocols/lss/jvss/	Joint Verifiable Secret Sharing
Dealer	protocols/lss/dealer/	Optional trusted dealer (testing only)
Adapters	protocols/lss/adapters/	Cross-protocol adapters

ThresholdVM Integration

LSS is integrated into T-Chain (ThresholdVM) via:

• Executor: node/vms/thresholdvm/executor.go

  • LSSKeygenStartFunc() - Creates LSS keygen protocol runner
  • LSSSignStartFunc() - Creates LSS signing protocol runner
  • LSSReshareStartFunc() - Creates LSS reshare protocol runner
  • LSSRefreshStartFunc() - Creates LSS refresh protocol runner
  • LSSKeyShare wrapper implements KeyShare interface

• Usage in VM:

executor := NewProtocolExecutor(pool)
startFunc := executor.LSSKeygenStartFunc(selfID, participants, threshold)
handler, err := protocol.NewMultiHandler(startFunc, sessionID)

Testing

# Test keygen protocol
go test ./protocols/lss/keygen -v

# Test signing
go test ./protocols/lss/sign -v

# Test resharing
go test ./protocols/lss/reshare -v

# Test full LSS protocol (integration)
go test ./protocols/lss -v

# Performance benchmarks
go test ./protocols/lss -bench=. -benchmem

# Run all tests
go test ./protocols/lss/... -v

See LP-7330 for full ThresholdVM specification.

Related LPs

• LP-7014: CMP/CGG21 Protocol (ECDSA threshold signatures)
• LP-7104: FROST Protocol (Schnorr threshold signatures)
• LP-7330: T-Chain ThresholdVM (VM integration)
• LP-13: T-Chain Specification (uses LSS)
• LP-15: MPC Bridge Protocol

Conclusion

LSS provides unique dynamic resharing capabilities essential for long-lived threshold systems. While CGG21/CMP excels at ECDSA with accountability, LSS offers unmatched flexibility for participant and threshold changes. Together, they form a comprehensive threshold cryptography suite for the Lux Network, enabling secure, adaptable, and robust distributed key management.

References

1. Shamir, A. (1979). How to Share a Secret. Communications of the ACM.
2. Feldman, P. (1987). A Practical Scheme for Non-Interactive Verifiable Secret Sharing. FOCS 1987.
3. Pedersen, T. (1991). Non-Interactive and Information-Theoretic Secure Verifiable Secret Sharing. CRYPTO 1991.
4. Herzberg, A., et al. (1995). Proactive Secret Sharing. CRYPTO 1995.
5. Desmedt, Y., & Jajodia, S. (1997). Redistributing Secret Shares to New Access Structures. Information Processing Letters.
6. Wong, T., Wang, C., & Wing, J. (2002). Verifiable Secret Redistribution for Archive Systems. IEEE Security in Storage Workshop.
7. Schultz, D., Liskov, B., & Liskov, M. (2008). MPSS: Mobile Proactive Secret Sharing. ACM TISSEC.
8. Baron, J., et al. (2015). Communication-Optimal Proactive Secret Sharing for Dynamic Groups. ACNS 2015.
9. Benhamouda, F., et al. (2021). Can a Blockchain Keep a Secret? TCC 2021.
10. Komlo, C., & Goldberg, I. (2020). FROST: Flexible Round-Optimized Schnorr Threshold Signatures. SAC 2020.

Copyright

Copyright and related rights waived via CC0.