Limitations of Threshold Secret Sharing and Derived MPC Applications

Abstract. The original t-out-of-n threshold secret sharing scheme, Shamir’s scheme, is based on polynomial evaluation and interpolation.  While useful in many applications, such as key management and secure multi-party computation (MPC), the scheme comes with several, often-acceptable limitations: (1) due to interpolation, the secret must live in a group (finite field) where every element has a unique multiplicative inverse, and (2) there must be more group elements than shares.  In this presentation, we present a technique for building a t-out-of-n threshold secret sharing scheme from any n-out-of-n secret sharing scheme (particularly, even those that do not satisfy the aforementioned conditions).  Then, we examine the features and limitations of these constructed schemes to draw inferences about the flexibility and feasibility of threshold secret sharing in general.  In particular, we consider operations (inspired by real-world use cases) which can be computed without communication in some of the constructed schemes (but not in any variant of Shamir’s scheme).  We discuss how the proposed work relates directly to threshold schemes for crypto primitives, such as those considered in the NIST call for multi-party threshold schemes, considering that the added flexibility of the approach enables the use of multiple mathematical structures (with various algebraic and homomorphic properties) as a foundation for a threshold scheme.

[Video]