Secret sharing
Earlier this year, the sudden death of QuadrigaCX CEO of the Canadian Codex Exchange, resulted in the loss of the private key of the exchange that only the CEO knew. Ultimately, the exchange could not restore the $150 million worth of cryptocurrency forever. At around the same time in Korea, the cryptocurrency exchange, CoinBin, lost the secret key that locked 2.5 billion won, and both exchanges eventually went bankrupt. If the exchange’s private key had been backed up or recovered, this disaster would have been prevente
In the digital information era, protecting information such as passwords and private keys is very important. Generally, to prevent the loss of the private key, it was backed up in various places. However, this method has the risk of increasing the possibility of exposing the private keys. Backing up the private key in many areas or giving the private key to a lot of people reduces the chance of losing key, but it also increases the likelihood of the private key being leaked.
To solve the above-mentioned risks, secret sharing, which satisfies the following conditions, is being studied.
- Divide one secret into several pieces and store it. (shares)
- To restore the original secret, a certain number of shares are required. (threshold)
It is possible to implement secret sharing that satisfies the above conditions by simply cutting the secret to a certain length and dispersing it to several people. As shown in the picture below, if four people possess three of the four pieces, they can recover the original secret if they get together.
However, with this method, the larger the number of people and the threshold value, the greater the number of pieces required. If 100 people have secrets and set the threshold to 50, it would require 1.009x10²⁹ secrets, and each person must have 5.04x10²⁸ pieces.
Therefore, we need a more efficient algorithm, and Shamir’s Secret Sharing and Blakey’s Secret Sharing are representative algorithms. Blakey’s Secret Sharing is based on the intersection of n-dimensional shapes. In the figure below, one point is determined through the intersection of three 2D planes.
Shamir’s Secret Sharing is an algorithm published in 1979 that takes advantage of the fact that the t-1 th degree polynomial of x is uniquely determined, passing through t points with different x-coordinate values. For example, two points determine one straight line, and three points can uniquely determine one parabola. The figure below shows that one secret is divided into 7 shares and the threshold is set to 3.
Even if only one of t points is missing, numerous t-1 order polynomials exist as candidates, and the original polynomial can not be guessed. Therefore, no matter how many less than t secret pieces gather, the original secret value can never be exposed.
Shamir’s Secret Sharing process is shown below.
- S is a secret value, which determines the t number of information that should be gathered to recover the secret value and the n number of people to share the secret. (t<=n)
- The polynomial q (x) that satisfies
is arbitrarily determined. (a_0=S)
3. The n points (1, q (1)), (2, q (2)), …, (n, q (n)) that exist on the polynomial function y = q(x) become the shared secrets.
The secret recovery process is performed as follows:
- Collect T points (shared secret) above the polynomial y = q (x) and find q (x) through the polynomial interpolation above.
- q (0) is the original secret value S.
To do this, we use polynomial interpolation. When expressed as an equation, it is as follows:
Shamir’s Secret Sharing is characterized by the fact that the secrets that all members share are unique and equal to each other. Also, if you have enough secret pieces above the threshold, you can recover the secret, so it is safe even if some secret fragments are lost. Furthermore, even if a few traitors with bad intentions gather to recover the secret, it will be impossible.
However, these features are also limitations. Since all shared secrets are equal, it is difficult to divide them according to their security level when dividing the secrets, and it is impossible to prevent secret holders from giving incorrect secret values when providing the secret pieces, and when a secret is restored, it is not possible to tell if the proper secret has been uncovered.
The disadvantages of Shamir’s secret sharing were reinforced by several studies that follow. In 1987, Feldman and Benaloh each created a verifiable secret sharing scheme in which shared secret holders could verify their shares. Stadler in 1996, Schoenmakers in 1999, and Pederson in 2004, all respectively created publicly verifiable secret sharing algorithms that could verify not only their own shares but also others’ shares.
As secret sharing is an important factor in protecting digital assets, CodeChain will provide secret sharing via codechain-keystore. And by storing all the secret keys of CodeChain in a distributed manner, it is possible to provide protection against the threat of hacking and prevent possible loss, ultimately resulting in more reliable service.
