Explaining Shamir’s Secret Sharing: The Building Block of Arcana’s DKG

Before we dive into what secret sharing and Shamir’s Secret Sharing mechanism is, let us walk through a simple example.

Consider a bank with a vault that needs to be accessed every day. To reduce the possibilities of fraud or theft, the bank adopts an approach where four senior personnel in the bank are provided with parts of a secret key that opens the vault. The vault can only be opened when at least three personnel are present with their parts to the secret key. This is a real-world example of how secret sharing mechanisms work. No individual member can open the vault on their own, and at least three personnel have to be present for the vault to be opened. Three becomes the threshold number of people required to open the vault.

Through secret sharing schemes, we are essentially distributing a secret key over a group of individuals in such a way that no single individual can access the shared secret by themselves. Secret sharing schemes were independently invented by George Blakley and Adi Shamir in 1979.

Among the various secret sharing schemes, Shamir’s Secret Sharing (SSS) is one of the most popular and basic schemes. It also forms the basis of Distributed Key Generation (DKGs) which is used extensively due to its simplicity and easy application. In this post, we attempt to break down SSS, give you a quick overview of how it works, and then highlight some of the most prominent drawbacks of the secret-sharing mechanism.

This blog post is a part of “Engineering at Arcana” series where we share all things blockchain, technology, and engineering. Read on.

Shamir’s Secret Sharing

Below, we deconstruct Shamir’s Secret Sharing (SSS) from a mathematical perspective. The fundamental idea behind SSS is that in order to reconstruct a polynomial of degree n, you would require n+1 points that lie on that curve. So, for example, in order to reconstruct a line, we require at least 2 points that lie on that line.

Consider the X & Y axis, along with a line that intercepts the Y-axis at a point ‘D’. Let’s take three points on the line, say A, B, and C. Here, the three points translate to the three people who have shares to access the secret ‘D.’

Now imagine that the line that intercepts the Y-axis is erased. To find out the secret, which is point D, you would have to know at least two points out of the three points, A, B, and C. This particular case is called 2-out-of-3 Shamir Secret Sharing.

While the above-mentioned example is discussing a linear curve, the same mechanism also holds true for higher powers of x. A quadratic curve, for instance, will require at least three points, whereas a cubic curve will require four points.

Lagrange’s Interpolation

Once you have the points that lie on the curve, how do you reconstruct the polynomial? Without going into too much detail, this is done using Lagrange Interpolation. The formula to reconstruct a polynomial P(x) given n points (x1, y1), (x2, y2) .. (xn, yn) that lie on it is:

Where each Pj is:

Or, if you were to expand it out:

With the reconstructed polynomial, you can then find the y-intercept and subsequently the secret being shared.

Note: The above mathematical expressions form the basis of Shamir’s Secret Sharing. Lagrange’s Interpolation is extensively used in secret sharing schemes, including Distributed Key Generation (DKG) systems as well.

Drawbacks of Shamir’s Secret Sharing

While SSS is widely used across the blockchain ecosystem, the mechanism does come with a number of drawbacks. As a result, other models such as Asynchronous Verifiable Secret Sharing (AVSS) have been adopted. We will dive into AVSS and other such mechanisms in future posts in our “Engineering at Arcana” blog series.

Coming back to the drawbacks with Shamir’s Secret Sharing schemes below, let’s go over two of the most prominent ones:

• Inability to verify share integrity
  With SSS, it is not possible to verify if the data of a split secret is corrupted. The same is the case when it comes to verifying if the retrieved shares of a secret are correct or not. This downside primarily led to the development of verifiable secret sharing, through which it is possible to check if the shareholders of the secret are submitting authentic shares or fakes.
• Single Point of Failure
  SSS, in essence, works by splitting a secret key into multiple keys on a single device; and when someone wants to access the shared secret, they will then have to reconstruct the entire secret using the shared keys on some other device. In such a case, a security compromise on either of the devices (the device which held the key during splitting or the device which held the key during recombination) can effectively compromise the secret — leading to a single point of failure.

There are also other, not-so-major drawbacks worth mentioning: complexity in implementation, share revocation, lack of strong implementation standards, social recovery issues, side-channel attacks, and poor auditability.

What we have above is a simple guide to help you understand the general concept and the mathematics behind SSS, along with a few downsides which led to the evolution and adoption of other secret sharing mechanisms.

In later blog posts, we will expand on other schemes, and what we at Arcana are doing to overcome the drawbacks mentioned, among other insightful topics. Follow us on our socials or medium to stay up to date with all the informational content we post in the time to come.

About Arcana Network

Built for Ethereum and EVM-based chains, Arcana is the web3 infrastructure to easily onboard dApp users and enable user data privacy and ownership. Web3 developers use Arcana’s SDKs for a seamless, familiar user onboarding experience via social authentication and passwordless login. All user data is encrypted, secured with data access fully controlled by the users, and powered by blockchain.

Arcana has raised 2.7Mn USD from some of the leading investors and founders in the ecosystem such as Balaji Srinivasan, Founders of Polygon, Woodstock, Republic Crypto, and Digital Currency Group.

Watch out for Arcana’s upcoming Testnet and Mainnet in 2022.

Official Links: Website | Telegram | TG Announcement | Twitter | Medium| GitHub | Discord|