Alice: Hierarchical Threshold Signature Scheme
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 she 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.<p>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:<p>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.<p>2. Anyone can use the public key to convince himself&#x2F;herself that the signer has actually approved this message.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 to ideal digital signatures: RSA, DSA, ECDSA. Bitcoin and Ethereum both adopt ECDSA as the standard method of digital signature because ECDSA has shorter signature comparing to others such that we can save more signatures in a fixed space.<p>In the architecture of digital signature, anyone can sign transaction by using the correct private key. Therefore, 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 two solutions: multi-signatures and threshold signature scheme (TSS) to reduce the risk of key management. The purposes of both are:<p>1. Avoiding a single-point of failure, making it substantially more difficult for the asset key to be transferred.<p>2. M-of-N backup where loss of a single seed doesn&#x27;t lead to loss of the asset. 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 where any t private keys out of a possible n are required to move the money. 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. To solve this problem, TSS has come in view of people. Let n be the number of participants and 1&lt;t&lt;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:<p>•Key Generation：Each participant chooses his&#x2F;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.<p>•Sign a transaction: Each participant uses his&#x2F;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.<p>•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.<p>•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.<p>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. 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:<p>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.<p>2. A cold wallet lose (i.e. a high-rank share lose): User uses his&#x2F;her backup cool wallet to transfer his&#x2F;her property to a new address. Or another solution is to add a new share and then refresh all the shares.<p>In conclusion, we regard that HTSS is more flexible and more suitable for applying in business models.