Alice: Hierarchical Threshold Signature Scheme

Hierarchical Threshold Signature Scheme

Introduction:

This is Hierarchical Threshold Signature Scheme (HTSS) worked by AMIS . Comparing to Threshold Signature Scheme (TSS), shares in this scheme are allowed to have different ranks.

The main merit of HTSS is vertical access control such that it has "partial accountability”. Although TSS achieves joint control to disperse risk among the participants, the level of all shares are equal. 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.

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 to blame for. However, in HTSS framework, through assigning different ranks of each share induces that any valid signature generated includes the share of the manager.

HTSS has been developed by Tassa and other researchers many years ago. In our implementation, we setup up this theory on TSS(i.e. just replace Lagrange Interpolation to Birkhoff Interpolation). Meanwhile, our protocol of sign (i.e. GG18 and CCLST20 ) can support two homomorphic encryptions which are Paillier and CL scheme.

This code will be audited soon.

One of references of HTSS is A Hierarchical Threshold Signature or See.

Table of Contents:

Implementations:

Like the classical TSS, HTSS also contains three protocols:

1. DKG: Distributed key generation for creating secret shares without any dealer.
2. Signer: Signing for using the secret shares to generate a signature.
3. Reshare: Refresh the secret share without changing the public key.

The algorithms can be downloaded in here .

Remark:

1. Comparing to TSS, each share in HTSS is generated by DKG having difference levels (or called rank). The level 0 is the highest.
2. If all levels of shares are zero, then HTSS reduces to the classical TSS. (i.e. In this case, Birkhoff interpolation reduces to Lagrange Interpolation).
3. After perform the progress of DKG, each participant will get (x-coordinate, share, rank). Assume that the threshold is 3. Therefore, any three shares (x-coordinate, rank): (x1, n1), (x2, n2), (x3, n3) with n1 <= n2 <= n3 can recover the secret or sign if and only if n_i <= i-1 for all 1 <= i <= 3. In general, assuming the threshold is t, any t shares (xi,ni) with ni <= nj for all i < j can recover the secret or sign if and only if n_i <= i-1 for all 1 <= i <= t.

Example:

Let threshold = 3, and participants = 4. Assume that the corresponding rank of each shareholder are 0, 1, 1, 2. Then authorized sets in this setting are

1. 0, 1, 1
2. 0, 1, 2
3. 0, 1, 1, 2

The other combinations of shares can not recover the secret (e.g. 1, 1, 2).

DKG:

We implement a modified version of DKG in Fast Multiparty Threshold ECDSA with Fast Trustless Setup . We point out the different parts:

• Replace Lagrange interpolation with Birkhoff interpolation and generate own x-coordinate respectively.
• We do not generate a private key and the corresponding public key of homomorphic encryptions (i.e. Paillier cryptosystem or CL Scheme) in the key-generation. Move it to the beginning of Signer.

Signer:

Our implementation involves two algorithms: Fast Multiparty Threshold ECDSA with Fast Trustless Setup and Bandwidth-efficient threshold EC-DSA . The main difference of two schemes is applying different homomorphic encryptions. One is Paillier cryptosystem and another is CL scheme. We point out the difference between our implementation and their versions.

GG18:

• Replace Lagrange interpolation with Birkhoff interpolation .
• In the beginning of signer, we generate a key-pair of the homomorphic encryption.

Remark:Our version is the algorithm of GG18 without doing range proofs in MtA(cf. Section 3, GG18 ).

CCLST:

• Replace Lagrange interpolation with Birkhoff interpolation .
• In the beginning of signer, we generate different parameters for each participant in the homomorphic encryption scheme. In their protocol, all participants use the same parameters but different key-pairs, which are generated in DKG.
• All zero-knowledge proofs are non-interactive version (i.e. This part will be audited soon).

Reshare:

It is the standard algorithm replacing Lagrange interpolation with Birkhoff interpolation .

Usage:

Peer:

We create an interface named `PeerManager`. It defines three methods to be implemented.

NumPeers
SelfID
MustSend

Before you try to go through a multi-party algorithm, you should create a peer manager instance first. Here is an example for DKG.

type dkgPeerManager struct {
	id       string
	numPeers uint32
	dkgs     map[string]*dkg.DKG
}

func newDKGPeerManager(id string, numPeers int, dkgs map[string]*dkg.DKG) *dkgPeerManager {
	return &dkgPeerManager{
		id:       id,
		numPeers: uint32(numPeers),
		dkgs:     dkgs,
	}
}

func (p *dkgPeerManager) NumPeers() uint32 {
	return p.numPeers
}

func (p *dkgPeerManager) SelfID() string {
	return p.id
}

func (p *dkgPeerManager) MustSend(id string, message proto.Message) {
	d := p.dkgs[id]
	msg := message.(types.Message)
	d.AddMessage(msg)
}

Listener:

We create an interface named `StateChangedListener`. It defines one method to be implemented.

1. OnStateChanged : Handle state changed.

type listener struct{}

func newListener() *listener {
	return &listener{}
}

func (l *listener) OnStateChanged(oldState types.MainState, newState types.MainState) {
	// Handle state changed.
}

DKG:

Distributed key generation (DKG) is a process that multiple parties participate in the calculation of a shared public key and private key. To create a new DKG instance, there are some inputs caller must provide in our implementation.

• curve : an elliptic curve (e.g. S256)
• dkgPeerManager : a peer manager for DKG
• threshold : minimum number of participants required to sign
• rank : the rank of this participant
• listener : a function to monitor the state change

myDKG, err := dkg.NewDKG(curve, dkgPeerManager, threshold, rank, listener)
if err != nil {
    // handle error
}
myDKG.Start()
// send out peer message...
myDKG.Stop()
dkgResult, err := myDKG.GetResult()
if err != nil {
    // handle error
}

After DKG, all the participants would get the same public key and all the x-coordinates and ranks. Each participant would also get their own share.

Signer:

A (t,n)-threshold signature is a digital signature scheme that any t or more signers of a group of n signers could generate a valid signature. Here, we support two encryption algorithms for signing: Paillier, and CL. Caller must specify which encryption to be used. The security level of two homomorphic encryptions can be found in.

// 1. Paillier
homo, err := paillier.NewPaillier(2048)
if err != nil {
    // handle error
}
// 2. CL
safeParameter := 1348
distributionDistance := uint(40)
homo, err := cl.NewCL(big.NewInt(1024), 40, c.Params().N, safeParameter, distributionDistance)
if err != nil {
    // handle error
}

To start signing, you should provide some inputs for creating a new Signer instance.

• signerPeerManager : a peer manager for signer
• publicKey : the public key generated from DKG
• homo : a homomorphic encryption (Paillier of CL)
• share : the private share from DKG
• bks : the Birkhoff parameter of all participants
• msg : a message to be signed
• listener : a function to monitor the state change

Note that, threshold signers are required to participate in signing. Therefore, the length of bks must not be less than threshold .

mySigner, err = signer.NewSigner(signerPeerManager, publicKey, homo, share, bks, msg, listener)
if err != nil {
    // handle error
}
mySigner.Start()
// send out public key message...
mySigner.Stop()
signerResult, err := mySigner.GetResult()
if err != nil {
    // handle error
}

After signing, all the participants should get the same signature.

Reshare:

Refreshing share (reshare) computes new random shares for the same original secret key. Before resharing, here is also some inputs you need to prepare.

• resharePeerManager : a peer manager for reshare
• threshold : minimum number of participants required to sign
• publicKey : the public key generated from DKG
• share : the private share from DKG
• bks : Birkhoff parameters from all participants
• listener : a function to monitor the state change

Note that, reshare process requires all peers to participate.

myReshare, err = reshare.NewReshare(resharePeerManager, threshold, publicKey, share, bks, listener)
if err != nil {
    // handle error
}
myReshare.Start()
// send out commit message...
myReshare.Stop()
signerResult, err := myReshare.GetResult()
if err != nil {
    // handle error
}

After resharing, all the participants should get their new shares. For more usage, please check tss/integration/tee_test.go .

Examples:

Standard threshold signature:

There are three people co-founding a small store. Many goods come in and out every day. To increase efficiency, they agree that if any two of them confirms a transaction, the transaction should be valid. In this case, they could utilize threshold signature.

In DKG stage, all of them should create a peer manager specifying number of peers to be 2 . And all of them should have the same value of rank to be 0 . Then in signing stage, any two of them could generate a valid signature.

• Ranks: (0, 0, 0)
• Threshold: 2

DKG:

// S256 for example
curve := btcec.S256()
id := "myID"
peerNum := uint32(2)
threshold := uint32(2)
rank := uint32(0)

// each co-founder
dkgPeerManager := newDKGPeerManager(id, peerNum, dkgs)
myDKG, _ := dkg.NewDKG(curve, dkgPeerManager, threshold, rank, listener)

Signing:

msg := []byte{1, 2, 3}
peerNum := uint32(1)
homo, _ := paillier.NewPaillier(2048)

// get result from DKG
result, _ := myDKG.GetResult()

// any two of co-founders
signerPeerManager := newSignerPeerManager(id, peerNum, signers)
mySigner, _ := signer.NewSigner(signerPeerManager, result.PublicKey, homo, result.Share, result.Bks[id], peerBks, msg, listener)

Hierarchical threshold signature:

Imagine a department in a company is consisted of three employees and one director. The company stipulate that any transaction should be approved by at least three people and one of the approval must be the director. In this case, there are four participants but their powers might be different.

In DKG stage, all of them should create a peer manager specifying number of peers to be 3 . Three employees should set the rank value to be 1 but the director should have the rank value to be 0 (smaller the value, higher the rank). In signing stage, any two of employees along with the director could generate a valid signature. If three employees without the director try to sign a message, the signing process will return an error.

• Ranks: (0, 1, 1, 1)
• Threshold: 3

DKG:

// S256 for example
curve := btcec.S256()
id := "myID"
peerNum := uint32(3)
threshold := uint32(3)
employeeRank := uint32(1)
directorRank := uint32(0)

// each employee
dkgPeerManager := newDKGPeerManager(id, peerNum, dkgs)
employeeDKG, _ := dkg.NewDKG(curve, dkgPeerManager, threshold, employeeRank, listener)

// the director
directorDKG, _ := dkg.NewDKG(curve, dkgPeerManager, threshold, directorRank, listener)

Signer:

msg := []byte{1, 2, 3}
peerNum := uint32(3)
homo, _ := paillier.NewPaillier(2048)

// get result from DKG (for employee)
result, _ := employeeDKG.GetResult()
// get result from DKG (for director)
result, _ := directorDKG.GetResult()

// two of employees and the director
signerPeerManager := newSignerPeerManager(id, peerNum, signers)
mySigner, err = signer.NewSigner(signerPeerManager, result.PublicKey, homo, result.Share, result.Bks[id], peerBks, msg, listener)

Benchmarks:

Our benchmarks were in local computation and ran on an Intel qualcore-i5 CPU 2.3 GHz and 16GB of RAM.

GG18(Paillier case):

• Threshold: 3
• Three shares with ranks (x, share, rank): (108, 4517821, 0), (344, 35822, 1), (756, 46, 2)
• Public Key: 2089765*G
• The bit-length of Paillier public Key: 2048 (ref. Appexdix )
• curve: S256

(Ran 10 samples)

+-----------------+--------------------------+------------------------------+
|  Fastest Time   |            Slowest Time  |                 Average Time |
+-----------------+--------------------------+------------------------------+
|          0.719s |                   1.150s |              0.902s ± 0.125s |
+-----------------+--------------------------+------------------------------+

For CCLST:

• Threshold: 3
• Three shares with ranks (x, share, rank): (108, 4517821, 0), (344, 35822, 1), (756, 46, 2)
• Public Key: 2089765*G
• The security level: 1348(i.e. the bit length of fundamental discriminant) (ref.)
• distribution distance: 40 (cf. Section 3.1 )
• the challenge set C: 1024 (cf. Section 3.1 )
• r1 challenge bit translation: 40 (cf. Section 3.1 )
• curve: S256

(Ran 10 samples)

+-----------------+--------------------------+------------------------------+
|  Fastest Time   |            Slowest Time  |                 Average Time |
+-----------------+--------------------------+------------------------------+
|          2.452s |                   3.754s |              3.229s ± 0.396s |
+-----------------+--------------------------+------------------------------+

Appendix:

Security levels of two homomorphic schemes:

The Table below is referenced by Improved Efficiency of a Linearly Homomorphic Cryptosystem .

+-----------------+--------------------------+-----------------------------------+
| Security Level  |  RSA modulus (Paillier)  |  fundamental discriminant ΔK (CL) |
+-----------------+--------------------------+-----------------------------------+
|          112    |          2048            |                         1348      |
|          128    |          3072            |                         1828      |
|          192    |          7680            |                         3598      |
|          256    |         15360            |                         5972      |
+-----------------+--------------------------+-----------------------------------+

Useful Cryptography Libraries in this Repository:

1. Binary quadratic forms for class groups of imaginary quadratic fields
2. Castagnos and Laguillaumie homomorphic Scheme
3. Paillier homomorphic cryptosystem

References:

1. Fast Multiparty Threshold ECDSA with Fast Trustless Setup
2. Bandwidth-efficient threshold EC-DSA
3. Hierarchical Threshold Secret Sharing
4. Dynamic and Verifiable Hierarchical Secret Sharing
5. Linearly Homomorphic Encryption from DDH
6. Improved Efficiency of a Linearly Homomorphic Cryptosystem
7. A Course in Computational Algebraic Number Theory (Graduate Texts in Mathematics)
8. Maxwell Sayles: binary quadratic form

Other Libraries:

1. KZen-tss
2. Binance-tss