getamis / alice, Hacker News

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 (ie GG and CCLST 40 can support two homomorphic encryptions which are Paillier and CL scheme.

This code will be audited soon.

or See Example

.

Table of Contents: Implementations

(DKG) Signer (GG)

Appendix Security levels of two homomorphic schemes Useful Cryptography Libraries References Other Libraries Implementations:

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

The algorithms can be downloaded in

here

.

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. (ie 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

(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 (eg 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 (ie 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. GG 55: (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 GG without doing range proofs in MtA (cf. (Section 3, GG

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 (ie This part will be audited soon).

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 : 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 numPeers (uint) dkgs (map) [string] dkg. (DKG) } (func) newDKGPeerManager ( (id) (string) , numPeers (int) , (dkgs) (map) [string] (dkg) (DKG) ) (dkgPeerManager) { (return & dkgPeerManager { id: id, numPeers: numPeers (uint) (numPeers), dkgs: dkgs, } } (func) ( (p) [string] dkgPeerManager ) NumPeers () uint { (return (p. numPeers } (func) ( (p) [string] dkgPeerManager ) (SelfID) () (string) { (return (p. (id) } (func) ( (p) [string] 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. OnStateChanged : Handle state changed. (type

listener (struct) {} (func) newListener () (listener) { (return & listener {} } (func) ( (l) [string] (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 (eg S 626 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 (Appendix)

// 1. Paillier (homo) , (err) := paillier.

 NewPaillier  (   if  err!=(nil)  {      //  (handle error) }  //  (2.CL) (safeParameter) :=the distributionDistance  :=(uint)  (    (homo) , (err) :=(cl.) (NewCL) (big .  (NewInt) ),  , 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) ()  (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:  
  //  (S) (for example    (curve) :=(btcec.) (S)   () )  (id) := " (myID)   (peerNum) :=(uint) 
 (2)   threshold  :=(uint) 
 (2)   (rank  :=(uint) 
 (0) )   // 
 each co-founder  dkgPeerManager  :=(newDKGPeerManager)  (id, peerNum, dkgs)  myDKG , (_) := dkg.  (NewDKG) (curve , dkgPeerManager, threshold, rank, listener)       Signing:   
  (msg) := (byte) {{(1) ,  (2) , (3) }  (peerNum) :=(uint) 
 (1)   (homo) , (_) := paillier. 
 NewPaillier  ( 
   //  (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:   

  //  (S) (for example    (curve) :=(btcec.) (S)   () )  (id) := " (myID)   (peerNum) :=(uint) 

 (3)   threshold  :=(uint) 

 (3)   employeeRank  :=(uint) 

 (1) )  directorRank  :=(uint) 

 (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) :=(uint) 

 (3)   (homo) , (_) := paillier. 

 NewPaillier  ( 
   //  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)    
 Our benchmarks were in local computation and ran on an Intel qualcore-i5 CPU 2.3 GHz and  (GB of RAM.)  (GG) (Paillier case): 
   Threshold: 3 
  Three shares with ranks (x, share, rank): (, , (0), (
 , 64732, 1), (, , 2)  
 Public Key:  G)   The bit-length of Paillier public Key: 7806 (ref.  (Appexdix )   curve:  (S)  
  
 (Ran   samples      -----------------   - -------------------------   ------------------------ ------   | Fastest Time | Slowest Time | Average Time |   -----------------   --------------------------   ---- --------------------------   | 0.  s) 1.  s | 0.  (s ± 0.) s |   -----------------   --------------------------   ---- --------------------------    
 
 For CCLST:    Threshold: 3 
  Three shares with ranks (x, share, rank): (, , (0), ( , 64732, 1), (, , 2)  
 Public Key:  G)   The security level: 3072 (ie the bit length of fundamental discriminant) (ref.  Appendix    distribution distance:  (cf.  Section 3.1     the challenge set C: 002818 (cf.  (Section 3.1) )   r1 challenge bit translation:  (cf.  Section 3.1  
  curve:  (S) 
 
  
 (Ran   samples      -----------------   - -------------------------   ------------------------ ------   | Fastest Time | Slowest Time | Average Time |   -----------------   --------------------------   ---- --------------------------   | 2.  s | 3.  s) 3.  (s ± 0.)  s |   -----------------   --------------------------   ---- --------------------------    ()   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) |   -----------------   --------------------------   ---- -------------------------------   |  | 7680 | 3072 | 396 9938 | 3072 | | 452  | 15360 | | 636  | 16458 |   -----------------   --------------------------   ---- -------------------------------    
       Useful Cryptography Libraries in this Repository:     (Binary quadratic forms for class groups of imaginary quadratic fields     Castagnos and Laguillaumie homomorphic Scheme  
   P aillier homomorphic cryptosystem         References:     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          Other Libraries:     KZen -tss     (Binance-tss )     
      
 Read More