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

Now, Alice supports two parts:

Audited Part :

ECDSA :

1. HTSS(A variant of GG18 and CCLST).
2. HTSS(A variant of CGGMP).

EdDSA :

1. HTSS(A variant of FROST).

Preparation :

1. 2-party Bip32.

Security issues update:

1. verichanis, tssshock:
   They mentioned three security issues.

   a. Weaknesses in using ambiguous encoding scheme (alpha shuffle):
   Our implementation of GG18 and CGGMP adapts the Google protobuf, so our implementation is essentially immune to this attack.

   b. c-split:
   The version of our GG18 is secure according to Theorem 2 in the GG18. We follow the suggestion of GG18 to substitute sMTA for mta and mta with check. So, we do not implement
   this proof in our GG18.

c. c-guess:
We do not implement dlnproof in GG18 as described in the case b.
Our iteration of the zkproof in CGGMP is at least 80. ref [here](https://github.com/getamis/alice/blob/cf43552c510499e5e797bc06e855a8f2086408b0/crypto/homo/paillier/paillier.go#L43). If necessary, this value can be adjusted to 128. However, in practical terms, using 80 or above is considered reasonable. 

1. GG18 and GG20 Paillier Key Vulnerability [CVE-2023-33241]: Technical Report:
   In GG18 case, we have added a check: For any Paillier public key, it must not be divisible by the first three thousand prime numbers.
   For the CGGMP case, we have implemented a zero-knowledge proof named “Nosmallfactoezkproof” for Paillier that corresponds to this issue.

Audit Report:

Alice has been audited by Kudelski Security.

1. (GG18 And CCLST) The details can be found in here.

   Algorithm: The algorithms can be downloaded in here.

2. (FROST And CGGMP) The details can be found in here.

   Algorithm: The algorithms can be downloaded in here.

Warning:

Although the fist part of Alice has been audited, you should still be careful to use it.

1. Using end-to-end encryption to transfer messages between two parties is necessary.
2. If any error messages occur during execution Alice, you should stop and restart it. Never restart in the middle flow.
3. Now, the version of our GG18 is secure according to Theorem 2 in the GG18. We follow the suggestion of GG18 to substitute sMTA for mta and mta with check.

If you have more questions, you can connect us directly without any hesitation.

Our product

Wallet: Qubic

The Explanation of Packages

1. binaryfield: support some basic operation of binary fields.
2. binaryquadratic: support operations ideal class groups of quadratic imaginary fields over the rational number Q (ref.here).
3. bip32: support two-party computation of BIP32.
4. birkhoffinterpolation: support the birkhoff interpolation (i.e. a generization of Lagrange interpolation).
5. circuit: support the loading of bristol fashion and garbling circuit (ref. Two Halves Make a Whole: Reducing Data Transfer in Garbled Circuits using Half Gates).
6. commitment: support Section 2.4: hash commitment, Section 2.6:Feldman’s VSS parotocol, and Pedersen Commitment.
7. dbnssystem: write a positive integer to be The Double-Base Number expression.
8. ecpointgrouplaw: an interface of group operations of elliptic curve groups.
9. elliptic: support groups of of elliptic curve groups.
10. homo: support additive homomorphic encryptions: Castagnos and Laguillaumie homomorphic Scheme and Paillier homomorphic cryptosystem.
11. matrix: support some operations of matrices over finite fields.
12. mta: the special package used in the sign algorithm of ECDSA.
13. oprf: support a hash function mapping to the points of secp256k1. (ref. Shallue-van de Woestijne Method: Hashing to Elliptic Curves)
14. ot: support an Oblivious transfer protocol (ref. our implementation: Blazing Fast OT for Three-round UC OT Extension).
15. polynomial: support some operations of polynomials over finite fields.
16. tss: support ECDSA: GG18, CCLST, and CGGMP. And EdDSA: FROST.
17. utils: support some commonly used functions.
18. zkrpoof: support some zero knowledge proofs e.x. Schnorr’s proof, factorization proof and so on.

Acknowledgments:

Thanks to

1. Filipe Casal from Trail of Bits for indicating the potential issues of integer factorization proof.
2. Coinbase Developer grant