In honour of opening sourced HTSS-Lib https://github.com/getamis/alice worked by AMIS, we revise this topic: Hierarchical Threshold Signature.

Digital Signature:

Digital signature is a digital analogue of a pen-and-ink signature on a physical document. The purpose of digital signature is to solve the following scenario. Alice has a digital document and wants to attach some “proof” that can be used to prove that she had approved this document. Therefore, digital signature can be recognized as an analogue to her handwritten signature on an ordinary document.

---

Therefore, it is very critical to clarify and confirm that who had signed the contract. In order to prevent forged digital signature, we have to apply public-key cryptography. Public-key cryptography, is a cryptographic system that uses pairs of keys: public keys, which may be disseminated widely, and private keys are known only to the owner. Using this cryptography primitives, the basic idea of digital signature is that the person who signs a message by his private key, and anyone can use the associated public key to verify the signed message. Meanwhile, an ideal digital signature should have the following properties:

1. A signed message can unambiguously be traced back to its originator as a valid signature is only generated by the unique signer’s private key. Only the signer has the ability to generate a signature on his behalf.
2. Anyone can use the public key to convince himself/herself that the signer has actually approved this message.
3. It is very difficult to get the private key even though you have the knowledge of a public key.

---

There are three popular public-key families, namely integer factorization, discrete logarithm of finite fields or elliptic curves. Each of these allows us to construct ideal digital signatures: RSA, DSA, and ECDSA. Among these digital signature, RSA is the most widely used method in practice. However, in order to attain the same security-level as other signatures, the bit-length of public key of RSA should be the longest, which implies that it needs more space to save necessary data. Therefore, Bitcoin and Ethereum both adopt ECDSA which signature is the shortest one compared with other signature types.

---

Key management:

In the architecture of digital signature, anyone can sign transactions by using a private key. Therefore, key management plays a significant role in blockchain technology regarding the protection of digital assets. 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 two solutions: multi-signatures and threshold signature scheme (abrev. TSS) to reduce the risk of key management. The purposes of both are(ref. https://en.bitcoin.it/wiki/Multisignature):

1. If we can avoid a single-point failure, it will be more likely to prevent the asset to be transferred.
2. M-of-N backup where loss of a single seed doesn’t lead to loss of the asset.

---

Multi-Signature:

Multi-signature requires multiple private keys to authorize a transaction, rather than a single signature from one key. In detail, the multi-signature can be t-of-n type and it is possible to transfer the money once the transaction possesses t private keys out of total n keys. For example, a 2-of-3 multi-signature might have your private keys spread across a cold wallet, laptop, and smartphone, any two of which are required to move the money, but the compromise of any one key cannot result in theft. However, the main flaw of multi-signature is not so natural such that we have to write similar logic codes in different blockchains.

---

Threshold Signature Scheme:

To solve this problem, TSS has come in view of people. Let n be the number of participants and 1<t<n. A t-of-n threshold signature scheme means that a private key constructed by this scheme is divided into n parts called “share”, and at least t shares are required for creating a signature. In details, threshold signature includes four phases as follows:

• Key Generation：Each participant chooses his/her secret value first. All the participants run a progress together to determine their private key, the public key, and their own private shares based on these secret values.
• Sign a transaction: Each participant uses his/her 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 will occur and the private key is never appeared.
• Verification: The verification algorithm of TSS and the original case are the same. Anyone who has the knowledge of the public key and the message is able to verify the correctness of a signature.
• Refresh share: Refreshing the shares means that we change the value of shares without altering the public key. Periodically refresh can reduce the number of compromised shares to zero. Assuming that old un-compromised shares are erased, the refreshing process makes it more difficult to reach a state where the number of contemporaneous compromised shares surpasses the compromise threshold.

---

Compared to multi-signature, TSS offers 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. It seems that TSS may be a fabulous solution, but there are still some problems. For example, an important contract not only requires enough shares to sign, 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 to blame for in TSS.

---

Hierarchical Threshold Signature:

To solve this scenario, Professor Tassa introduced Hierarchical Threshold Signature Scheme by assigning different ranks of each share such that any valid signature generated includes the share of the manager (i.e. All shares in TSS have the same rank). A naive application of HTSS in cold wallets describes as follows. Assume that t =2 and n=3. In this case, we generate two high-ranked shares into different cold wallets and a low-ranked share in the cell phone or computer (ie. more risky place). After we generate all shares, one of the cold wallets can be used as a backup. Remember that if we want to sign a transaction, it should be either a high-ranked shares combined with a low-ranked shares or two high-ranked shares. As usual applications, there exists two situations to be considered:

1. Low-ranked shares lose: No matter how many low-ranked shares lose, no one can generate a correct signature due to the advantage of HTSS. Because any signature should involve at least a high-ranked share.
2. A cold wallet lose (i.e. a high-ranked share lose): User uses his/her backup cool wallet to transfer his/her property to a new address. Or another solution is to add a new share and then refresh all the shares.

Therefore, if there is an illegal signature, we can confirm that at least the high-ranked share had been involved, which is so-called “partial accountability”.

In conclusion,

1. HTSS preserves flexibility between partial accountability and privacy.
2. A rank of each share represents different power in business models.
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 generate a valid signature.

Reference:

1. Shamir’s Secret Sharing
2. An Introduction to Mathematical Cryptography
3. Understanding Cryptography
4. Hierarchical Threshold Secret Sharing
5. MultiSignature

---

本文由 AMIS ChihYun Chuang 提供

原文連結