Introduction to Hierarchical Threshold Signature(revised version)

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.

Image for post

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.
Image for post
1. Alice signs the message by her private key to produce a signature. 2. Anyone can verify her signature by her public key. (ref. Wiki: https://en.wikipedia.org/wiki/Digital_signature)

There are three popular public-key families, namely integer factorizationdiscrete logarithm of finite fields or elliptic curves. Each of these allows us to construct ideal digital signatures: RSADSA, 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.

Image for post
https://nvlpubs.nist.gov/nistpubs/SpecialPublications/NIST.SP.800-57pt1r4.pdf

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.

Image for post
Multi-Signature have three different private keys.

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.
Image for post
TSS: A private Key is divided into three shares. t shares can produce a correct signature.

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”.

Image for post
HTSS: Each share has the own rank.

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 提供

原文連結

分享在 facebook
Facebook
分享在 google
Google+
分享在 twitter
Twitter
分享在 linkedin
LinkedIn
分享在 pinterest
Pinterest

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

這個網站採用 Akismet 服務減少垃圾留言。進一步瞭解 Akismet 如何處理網站訪客的留言資料

%d 位部落客按了讚: