Lagrange Coefficient
Lagrange coefficients are mathematical weights used to reconstruct a secret or combine signature shares in threshold schemes like FROST and Shamir's Secret Sharing.
Key Takeaways
- A Lagrange coefficient is a mathematical weight assigned to each participant in a threshold signature or secret sharing scheme, ensuring that any qualifying subset of shares can reconstruct the original secret or produce a valid signature.
- In FROST signing, each signer multiplies their signing share by their Lagrange coefficient so that any t-of-n subset of signers produces the same aggregate signature.
- Lagrange coefficients change every signing session because they depend on which specific signers participate: a different subset means different weights for each member.
What Is a Lagrange Coefficient?
A Lagrange coefficient (also called a Lagrange basis weight) is a scalar value derived from Lagrange polynomial interpolation. It determines how much each data point (or participant) contributes when reconstructing a polynomial from a subset of its evaluations. In the context of cryptography, Lagrange coefficients are the mechanism that makes threshold schemes work: they ensure that combining the right number of shares always recovers the same secret or produces the same signature, regardless of which specific participants are involved.
The concept originates from a result in classical mathematics published by Joseph-Louis Lagrange in 1795. Given t points on a polynomial of degree t-1, Lagrange interpolation provides a formula to reconstruct the full polynomial. Each point receives a unique weight (its Lagrange coefficient) that determines its contribution to the result. Adi Shamir applied this property in 1979 to create Shamir's Secret Sharing, and it remains central to modern threshold cryptography protocols like FROST.
How It Works
To understand Lagrange coefficients, start with a simple analogy. Imagine you have a secret number hidden as the y-intercept of a straight line (a polynomial of degree 1). If you know any two points on that line, you can draw the full line and read off where it crosses the y-axis. With a curved polynomial of degree 2, you need three points. In general, for a polynomial of degree t-1, you need exactly t points.
Lagrange coefficients are the weights that make this reconstruction work mathematically. Each point gets a coefficient that answers: "How much should this point's value count toward the final answer?"
The Formula
For a set S of t participants, each identified by a unique index x_i, the Lagrange coefficient for participant i evaluated at zero (the secret's position) is:
λ_i = ∏ (x_j / (x_j - x_i)) for all j in S, j ≠ iThis is the product of x_j divided by (x_j minus x_i) for every other participant j in the current signing set. The formula has two important properties:
- It depends on the full set S of participants, not just participant i. Changing which signers participate changes every coefficient.
- When you multiply each participant's share by their coefficient and sum the results, you always recover the same value: the polynomial's constant term (the secret).
A Worked Example
Suppose a 2-of-3 threshold scheme uses participants with indices 1, 2, and 3. If participants 1 and 3 form the signing set S = {1, 3}:
λ_1 = 3 / (3 - 1) = 3/2
λ_3 = 1 / (1 - 3) = -1/2
Secret = λ_1 * share_1 + λ_3 * share_3If instead participants 2 and 3 form the set S = {2, 3}, the coefficients change entirely:
λ_2 = 3 / (3 - 2) = 3
λ_3 = 2 / (2 - 3) = -2
Secret = λ_2 * share_2 + λ_3 * share_3Both computations recover the same secret, but participant 3's coefficient changed from -1/2 to -2 because the surrounding set changed. This is why Lagrange coefficients must be recomputed for every signing session: the weights depend on who shows up.
Application in FROST
In the FROST threshold signature protocol, Lagrange coefficients serve a specific role during the signing round. Each signer computes their signing share as:
z_i = d_i + e_i * ρ_i + λ_i * s_i * c
Where:
d_i, e_i = nonce values from the commitment round
ρ_i = binding factor (derived from all commitments)
λ_i = Lagrange coefficient for signer i
s_i = signer i's secret key share
c = challenge hash (from the group nonce and message)The Lagrange coefficient λ_i scales signer i's key share contribution so that summing all signing shares produces a valid Schnorr signature under the group public key. Without the correct Lagrange coefficients, the shares from different subsets would not combine to the same aggregate value, and the signature would be invalid.
Why It Matters
Lagrange coefficients are what make threshold cryptography flexible. Without them, you would need every participant to sign (n-of-n), which creates a single point of failure if any participant goes offline. With Lagrange coefficients enabling t-of-n schemes, any qualifying subset of signers can produce a valid signature without revealing the underlying secret key.
This flexibility is critical for real-world deployments. In distributed key generation ceremonies, participants may be spread across different jurisdictions and time zones. In multisig wallet setups, some signers may be temporarily unavailable. Lagrange coefficients ensure the system remains functional as long as the threshold is met, regardless of which specific participants are present.
Protocols like Spark use FROST signing with Lagrange coefficients to enable fast, non-interactive threshold signatures. This allows multiple operators to jointly control funds without any single party holding the complete private key, improving both security and availability.
Use Cases
Threshold Wallets and Custody
Institutional custody solutions use threshold signatures where multiple parties (such as a hardware device, a server, and a recovery key) each hold a key share. Lagrange coefficients enable any 2-of-3 combination to sign transactions. If one device is lost or compromised, the remaining two can still authorize transfers while the compromised share is rotated out.
Secret Recovery
In Shamir's Secret Sharing, Lagrange coefficients reconstruct the original secret from a threshold number of shares. This is used for seed phrase backup splitting, where a user distributes shares to trusted parties or locations. Any sufficient subset of shares reconstructs the seed, but fewer shares reveal nothing about it.
Distributed Signing Protocols
Beyond FROST, Lagrange coefficients appear in many multi-party computation protocols. Any scheme built on polynomial secret sharing uses Lagrange interpolation to combine partial results. This includes protocols for threshold encryption, distributed randomness generation, and collaborative key management.
Proactive Secret Sharing
In long-lived systems, key shares can be periodically refreshed without changing the underlying secret. Each participant generates new shares that interpolate to the same polynomial, using Lagrange coefficients to verify consistency. This limits the window of vulnerability if a share is compromised.
Risks and Considerations
Finite Field Arithmetic
Lagrange coefficients in cryptographic protocols must be computed over a finite field, not ordinary integers. Using integer arithmetic leaks information about the secret: an attacker with fewer than t shares could narrow down the possible secret values. All operations (multiplication, division, addition) must use modular arithmetic over the field defined by the curve order.
Participant Index Management
The formula requires each participant to have a unique, non-zero index. If two participants share an index, the denominator (x_j - x_i) becomes zero, causing division by zero. Protocol implementations must enforce unique participant identifiers and reject zero as an index value.
Session-Dependent Recomputation
Because coefficients change with each signing set, they must be recomputed for every signing session. Caching or reusing coefficients from a previous session with a different participant set would produce an invalid signature. Implementations must derive the coefficient fresh from the current set of active signers before each signing operation.
Side-Channel Leakage
Computing Lagrange coefficients involves modular inversions and multiplications over secret indices. Implementations should use constant-time arithmetic to prevent side-channel attacks that could reveal participant indices or key share information through timing differences.
This glossary entry is for informational purposes only and does not constitute financial or investment advice. Always do your own research before using any protocol or technology.