One of references of HTSS is
- A Hierarchical Threshold Signature
- Introduction to Hierarchical Threshold Signature(revised version)
- Example.
After the project is cloned, we need to run below commands to initialize/update the sub-modules:
$ make initIf you need to rebuild protobuf, please run below command to install tools and build protobuf.
# Install tools
$ make tools
# Build protobuf
$ make protobufLike the classical TSS, HTSS also contains three protocols:
- DKG: Distributed key generation for creating secret shares without any dealer.
- Signer: Signing for using the secret shares to generate a signature.
- Reshare: Refresh the secret share without changing the public key.
Remark:
- Comparing to TSS, each share in HTSS is generated by DKG having difference levels (or called rank). The level 0 is the highest.
- 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).
- 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
- 0, 1, 1
- 0, 1, 2
- 0, 1, 1, 2
The other combinations of shares can not recover the secret (e.g. 1, 1, 2).
We implement a modified version of DKG in [Fast Multiparty Threshold ECDSA with Fast Trustless Setup](https://eprint.iacr.org/2019/114.pdf). We point out the different parts: * Replace Lagrange interpolation with [Birkhoff interpolation](https://en.wikipedia.org/wiki/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. We implement a modified version of DKG in [UC Non-Interactive, Proactive, Threshold ECDSA with Identifiable Aborts](https://eprint.iacr.org/2021/060.pdf) including echo protocol. We point out the different part: * Replace replacing the n-n threshold with [Birkhoff interpolation](https://en.wikipedia.org/wiki/Birkhoff_interpolation) and generate own x-coordinate respectively.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.
- 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 sMtA(cf. Section 5, GG18).
- 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.
- Replace Lagrange interpolation with Birkhoff interpolation.
- All zero-knowledge proofs are non-interactive version.
- Replace Lagrange interpolation with Birkhoff interpolation.
- All zero-knowledge proofs are non-interactive version.
NumPeers: Return the number of peers.SelfID: Return the self ID.MustSend: Send message to the specific peer.
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)
}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.
}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.
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 Appendix.
// 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.
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()
reshareResult, err := myReshare.GetResult()
if err != nil {
// handle error
}After resharing, all the participants should get their new shares.
Adding share creates a new share for new participant without changing the original public key. This action will have two different roles: old peer and new peer. Each role will have different parameters be filled.
For old peer:
- addShareOldPeerManager: an old peer manager for add share
- publicKey: the public key generated from DKG
- threshold: minimum number of participants required to sign
- share: the private share from DKG
- bks: Birkhoff parameters from all participants
- listener: a function to monitor the state change
- newPeerID: the new peer ID
oldPeerAddShare, err = oldpeer.NewAddShare(addSharePeerManager, publicKey, threshold, share, bks, newPeerID, listener)
if err != nil {
// handle error
}
oldPeerAddShare.Start()
// send out peer message...
oldPeerAddShare.Stop()
addShareResult, err := oldPeerAddShare.GetResult()
if err != nil {
// handle error
}For new peer:
- addShareNewPeerManager: a new peer manager for add share
- publicKey: the public key generated from DKG
- threshold: minimum number of participants required to sign
- listener: a function to monitor the state change
- newPeerRank: the new peer's rank
newPeerAddShare, err = newpeer.NewAddShare(addSharePeerManager, publicKey, threshold, newPeerRank, listener)
if err != nil {
// handle error
}
newPeerAddShare.Start()
// send out peer message...
newPeerAddShare.Stop()
addShareResult, err := newPeerAddShare.GetResult()
if err != nil {
// handle error
}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
// S256 for example
curve := elliptic.Secp256k1()
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)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)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
// S256 for example
curve := elliptic.Secp256k1()
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)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)If you want to try an executable example, please check the
/examplefolder!
Our benchmarks were in local computation and ran on an Intel qualcore-i5 CPU 2.3 GHz and 16GB of RAM.
- 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 |
+-----------------+--------------------------+------------------------------+
- 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. Appendix)
- 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 |
+-----------------+--------------------------+------------------------------+
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 |
+-----------------+--------------------------+-----------------------------------+
- Fast Multiparty Threshold ECDSA with Fast Trustless Setup
- Bandwidth-efficient threshold EC-DSA
- Hierarchical Threshold Secret Sharing
- Dynamic and Verifiable Hierarchical Secret Sharing
- Linearly Homomorphic Encryption from DDH
- Improved Efficiency of a Linearly Homomorphic Cryptosystem
- A Course in Computational Algebraic Number Theory (Graduate Texts in Mathematics)
- Maxwell Sayles: binary quadratic form