A Hierarchical Threshold Signature

ChihYun Chuang
Nov 5, 2019 · 7 min read

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. No information can be revealed about s with the knowledge of any t′ pieces t′<t.
  1. Minimal: The size of each piece does not exceed the size of the original data.
  2. Ideal: The cardinality of the secret set is equal to the cardinality of the share set.
  3. Extensible: When t is fixed, shares can be be dynamically added or deleted without affecting the other pieces.
  4. Dynamic: Security can be easily enhanced without changing the secret.
  5. 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.
  1. 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.

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.


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. 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.
  2. 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.
  1. 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.

Hierarchical Threshold Signature Scheme:

  1. Private shares in HTSS can be refreshed and also permits add shares or delete shares dynamically without changing public key(i.e. address).
  2. 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

getamis

Using breakthrough blockchain technology, Amis has created a standardized platform to let business create information exchange systems and make transaction data open and shareable to improve the quality of life for everyone.

ChihYun Chuang

Written by

getamis

getamis

Using breakthrough blockchain technology, Amis has created a standardized platform to let business create information exchange systems and make transaction data open and shareable to improve the quality of life for everyone.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade