Allowing zero leading coefficients in our open-source SSS library
Andrew MacPherson
|Jan 10, 2025
We're making an update to our open-source Shamir Secret Sharing (SSS) library to align the implementation for wider open-source community usage. This update is consistent with the formal security properties of SSS while maintaining its strong practical security guarantees.
This library is built to be a public good: a robust implementation of SSS in Typescript, usable for general-purpose integrations. Accordingly, we now allow zero leading coefficients in our implementation of SSS.
Background
Privy embedded wallets use our open-source implementation of Shamir's Secret Sharing. SSS is a cryptographic algorithm that allows a secret to be split into multiple shares, requiring a threshold number of shares to reconstruct the original secret.
We maintain this library as a public good for the entire ecosystem, making it freely available and thoroughly audited for use by any project. This commitment to public infrastructure reflects our belief that robust cryptographic implementations should be available to everyone building in web3. Good security must be the default.
Details of the change
The update modifies how polynomial coefficients are generated in our SSS implementation. Previously, we enforced non-zero leading coefficients. The updated implementation allows all coefficients to be uniformly sampled from the full range [0, 255], aligning with the formal security proof of Shamir's Secret Sharing scheme.
Security impact
Privy's system implementation was never vulnerable to any practical attacks due to restriction for non-zero leading coefficients.
Privy's architecture ensures no party but the intended party ever has access to complete private keys.
The theoretical considerations only apply in specific scenarios requiring thousands of observations of the same secret being split. In practical terms, an attacker would have had to have control of the key store and the ability to split a given key thousands of times to enable this theoretical attack. This has not happened.
Understanding the technical challenge
The core technical consideration involves the polynomial coefficient generation in our Shamir Secret Sharing implementation. When generating a polynomial of degree t-1 for a (t,n)-threshold scheme, each coefficient, including the leading coefficient, should theoretically be sampled uniformly at random from GF(2^8). Our current implementation restricts the leading coefficient to be non-zero to prevent polynomial degree reduction.
The security implications of restricting the entropy’s leading coefficient are as follows:
Degree Reduction Risk (favors restriction):
When the leading coefficient is zero, the effective polynomial degree becomes t-2 rather than t-1
For a 32-byte secret split across multiple polynomials, the probability of at least one leading coefficient being zero is approximately 11% (1 - (255/256)^32)
The probability of two or more leading coefficients being zero reduces to 0.048%
For the scheme to actually reduce to a (t-1,n)-threshold scheme, all leading coefficients would need to be zero simultaneously - a probability of (1/256)^32, equivalent to approximately 2^-256
Perfect Secrecy Consideration (favors no restriction):
Restricting coefficients to be non-zero violates the uniform random sampling requirement of Shamir's scheme
This allows t-1 shares to rule out certain values as potential secrets through statistical analysis
With sufficient observations (thousands of splits of the same secret), this non-uniformity becomes detectable
While this doesn't directly compromise the secret, it leaks information about it
To help understand these probabilities and their implications, consider this analogy:
Imagine a special combination lock with 32 number wheels (analogous to our 32-byte secret), each with numbers from zero to eight. In a 2-of-2 split, two people each get half of the numbers. Currently, we're preventing any wheel from showing leading zeroes, worried that zero positions might make the lock weaker.
However the chance of getting an all zero wheel is as unlikely as flipping a coin and getting heads 128 times in a row but preventing zeroes creates a detectable pattern - someone watching the lock being created thousands of times could notice that zero never appears.
This statistical anomaly means that a malicious observer can identify a value that cannot be the secret, and repeated observers can sample increasingly many values that cannot be the secret, which reveals information about the secret itself. Preventing one theoretical risk creates another.
Key Takeaway: While the previous implementation protects against complete degree reduction, it results in non-uniformity detection if the same secret is split thousands of times. The updated implementation aligns with the perfect secrecy properties of Shamir's scheme, and continues to maintain practical security against degree reduction through the inherent probabilistic properties of random sampling.
The evolution of our implementation
At Privy, we believe that all engineering is security engineering. This is particularly true for cryptographic implementations, where the slightest detail can have significant security implications. Over the past two years, a number of security audits and cryptographic reviews have helped us refine this library's implementation. This library is open-sourced and Privy runs an active bug bounty program. Each review has provided insights, sometimes with competing security considerations (which is one of the reasons we do multiple audits from different companies!).
Here is the timeline for making this change to give you an idea of what the lifecycle of a cryptographic audit looks like:
February 2023: The Cure53 security audit identified a finding (PVY-01-002) regarding polynomial degree reduction. We implemented a fix enforcing non-zero leading coefficients, which Cure53 verified.
July 2023: We commissioned a security review from an additional firm. Zellic's comprehensive audit validated our implementation. During the audit, Zellic and Privy discussed the non-zero coefficient restriction and noted the tradeoffs for each of the two approaches. Another firm, Cypher Stack, identified a theoretical consideration and messaged us about it: enforcing non-zero coefficients could break the perfect secrecy property of Shamir's scheme, based on research by Ghodosi et al. This apparent contradiction between security recommendations led us to pursue deeper cryptographic analysis.
August 2023: Aaron Feickert's detailed analysis provided some mathematical context for Cypher Stack's concerns. In response, we collaborated with cryptographers from Cure53 to produce a formal analysis examining the security tradeoffs between preventing degree reduction and maintaining perfect secrecy properties. This led to us continuing the path of restricting leading coefficients
April 2024: Cure53, upon encountering similar implementation choices in another project, proactively contacted us with revised recommendations. Their updated cryptographic analysis indicated that maintaining uniform random sampling across all coefficients would better preserve the scheme's security properties, effectively reversing their original finding.
January 2025: Following a report from Fordefi discussing this same coefficient point, we reopened the discussion. While the previous implementation is secure for Privy's threat model, we always intended the library to be a public good and allowing zero coefficients better serves the library's role as a general-purpose implementation.
Why this matters to me
As an initiative lead at the Security Ecosystem Alliance (SEAL), improving web3 security is something I am super passionate about. I've seen how critical open collaboration is for web3 and specifically web3 security. Although this change did not impact Privy’s security model, our goals are to provide it as an open library for the overall good of the ecosystem so we have opted to make this change.
Acknowledgments
This improvement reflects the strength of the web3 security community. We thank:
The Cure53 team for their comprehensive audit and continued engagement
Zellic and Cypher Stack for their valuable insights
Aaron Feickert for raising important theoretical considerations
The Fordefi team and Dima Kogan for bringing this to our attention
Our internal security team and cryptographers for their thorough analysis
Moving forward
The updated library is available on GitHub. This update is fully compatible with existing implementations and will not cause any breaking changes.
We're always seeking talented developers and security researchers who share our passion for web3 and our commitment to building robust, secure systems. If that sounds interesting, consider reaching out through our careers page or directly to hello@privy.io
