Introduction:

Key management plays a significant role in blockchain technology regarding digital assets protection. Practically speaking, losing private keys leads to great losses. Improper key management and poor system implementation may increase the risk of asset being transferred maliciously. Take an extreme case that happened before as an example, a principal died suddenly and no one was able to recover keys so that the whole asset was frozen. To solve these problems, experts therefore propose threshold cryptography to reduce the risk of key management.

Threshold Cryptography

In an untrusted system, all participants may not know each other, so we should come up with a method to produce a correct result based on private information distributed across multiple parties. A possible answer may be threshold cryptography, a special application of secure multi-party computation, that splits sensitive value into multiple shares, and the computation is performed in an intrusion-tolerant distributed system. In threshold cryptography, the shares of the secret do not need to be recombined to compute a particular result. Instead, the participants independently or collaboratively calculate outcome without revealing the input shares to others. In order to realize this idea, there are many protocols and of which Shamir secret sharing is the most famous one.

Shamir’s Secret Sharing:

A (t, n)-Shamir Secret Sharing is a method which divides a secret s into n pieces by evaluating a polynomial of degree t − 1 at some points with the following two constraints:

1. s can be easily retrieved with the knowledge of t or more pieces.
2. No information can be revealed about s with the knowledge of any t′ pieces t′<t.

Properties of Shamir Secret Sharing are shown as follows:

1. Secure: Information theoretic security.
2. Minimal: The size of each piece does not exceed the size of the original data.
3. Ideal: The cardinality of the secret set is equal to the cardinality of the share set.
4. Extensible: When t is fixed, shares can be be dynamically added or deleted without affecting the other pieces.
5. Dynamic: Security can be easily enhanced without changing the secret.
6. Flexible: In organizations where hierarchy is important, we can supply each participant different number of pieces according to their importance inside the organization. For instance, the president and one secretary can unlock the safe, whereas 3 secretaries are required to unlock it.

Property 1, 2, 3,4 and 5 are desired properties. However, there are some flaws of property 6:

1. A person who possesses more shares bears more risks. This fact is against to a single point of failure.
2. Every time the president wants to recover the hiding secret, he needs to aggregate his shares in individual storage, which induces inconveniences of shares management.

Except for the flaws mentioned above, another serious problem is that any important secret can be recovered by 3 secretaries without the permission of the president. In the hierarchical system (ex. bank, government…and so on), this scenario should be solved.

Hierarchical Secret Sharing( Tassa Secret Sharing):

Tassa introduced the concept of levels in Shamir Secret Sharing to solve the above questions. In brief, no matter how many low-level shares you have, each share produced by his scheme has different level such that “low-level” shares can not recover the secret.

To be more specifically, Tassa secret sharing : a random coefficient polynomial f(x) of degree t -1 is created first. Then, the secret is the constant term of f(x). Each share is the evaluation of the polynomial f(x) at a point. Tassa used an extra operation called differentiation such that the share is computed by the derivative of f(x) and evaluated at a given point. Due to the nature of the differentiation, the constant term would vanish so we call the share coming from performing the derivative of a polynomial as low-level share. It implies that the secret, the constant term, can not be recovered by shares which consists of lower-level shares.

In Tassa secret sharing, each person only keep one share of respective level, reducing the risk of managing shares. In addition, this secret sharing also offers a solution to the question, which is an important secret recovered that the president must get involved in. In summary, Tassa secret sharing not only offers the properties of Shamir Secret Sharing from the first to the fifth but also improves the flexible.

An Application of Threshold Cryptography: Threshold Signature

Threshold Signature Scheme:

Threshold signature scheme (TSS), a special application of threshold cryptography, dramatically decreases the risk of private key management. Compared to multi-signature, TSS offers shorter signature and better privacy. Moreover, TSS provides native multi-signature capability for those blockchains that lack shorter signature and better privacy. Most importantly, TSS does not save private key on the server and provides risk control as well as separation of duties. These significant advantages make TSS suitable for implementing hot wallets without revealing private keys and provides the service in realtime. Threshold Signature includes three phases as follows:

1. Key Generation：Each participant chooses his secret value first. All the participants run a progress together to determine their private key, the public key ,and own private shares based on these secret values.
2. Sign a transaction: Each participant uses his private shares and a public message to be signed as input. All the participants in this protocol will exchange some necessary data such that each person produces a partial signature and broadcast it. Combining these partial signatures will produce a digital signature. The most important thing is that the process ensures that no leakage of secret shares occurred and the private key is never appeared.
3. Verification: The verification algorithm of TSS and the original case are the same. Everyone having the knowledge of the public key and the message is able to verify the correctness of a signature.

It seems that TSS may be a fabulous solution, but there are still some problems. The following is the potential risk of applying TSS, but will not occur with multi-signature scheme:

1. TSS does not have the property of accountability: It is impossible to distinguish which share getting involved in an unexpected signature. TSS is not like the multi-signature scheme as the signature is signed by distinct private keys in multi-signature scheme. It is because Shamir’s secret sharing only supports horizontal access control.
2. TSS is lack of vertical access control: Although TSS achieves joint control to disperse risk among the participants, the level of all shares are equal. For example, an important contract not only requires enough signatures, but also needs to be signed by a manager. Despite the fact that vertical access control can be realized on the application layer and tracked by an audit log. Once a hack happens, we will have no idea about who should be blamed for.

As summarized above, we need to design a system providing “vertical and horizontal” access controls for the accountability reasons. TSS natively possesses the horizontal access control (i.e. enough shares to generate a valid signature), but it lacks the design of vertical access controls. In order to make TSS more practical and solve the problems which it induces, we propose to a new threshold signature called hierarchical threshold signature scheme (HTSS) by combining hierarchical secret sharing and TSS.

Hierarchical Threshold Signature Scheme:

We use an example to demonstrate applications of HTSS. This scenario fits better in a financial institution with role-based access controls.

In a (2, 3)-threshold signature sharing, a dealer can generate two different levels of shares by Hierarchical secret sharing. Here we assume that there are two low level shares with one high level share. If a customer wants to transfer a transaction, it will require a banking teller to sign first and then a manager to endorse. In HTSS, if two banking tellers with low level shares co-sign the transaction, they still cannot generate a valid signature. And the manager cannot transfer the transaction without getting the approval from the banking teller. Therefore, if there is an illegal signature, we can confirm that at least the high level share had been involved, which is so-called “partial accountability”.

In conclusion,

1. HTSS preserves flexibility between partial accountability and privacy.
2. Private shares in HTSS can be refreshed and also permits add shares or delete shares dynamically without changing public key(i.e. address).
3. Compared to TSS, distributing extra new low level shares to users is less risky(i.e. This is an important merit for currency exchange) because low level shares can not recover a valid signature.

Thanks to Chang-Wu Chen and Yu-Te Lin.

Further Reading：

1. Threshold Cryptography
2. Shamir’s Secret Sharing
3. Threshold Signatures Explained
4. Birkhoff interpolation
5. Hierarchical Threshold Secret Sharing
6. Dynamic and Verifiable Hierarchical Secret Sharing