The library, Hierarchical Threshold Signature Scheme(abrev. HTSS) worked by AMIS, offers three protocols:

1. DKG: Each participant chooses his/her secret value first. All the participants run a progress together to determine their private key, the public key, and their own private shares based on these secret values.
2. Signer: Each participant uses his/her 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 will occur and the private key is never appeared.
3. Reshare: Refreshing the shares means that we change the value of shares without altering the public key.

In this article, we focus on introducing the core techniques behind the library called Alice:

1. Secure Multi-Party Computation(abrev. SMPC)
2. Secret Sharing Scheme
3. homomorphic encryption

By using the above techniques, we are able to interpret DKG and Signer as

1. DKG = SMPC + Secret Sharing Scheme
2. Signer = SMPC + Homomorphic encryption + ECDSA

Next I will introduce SMPC, Secret Sharing Scheme, and homomorphic encryption.

---

Secure Multi-Party Computation：

SMPC is a generic cryptographic primitive that enables distributed parties to jointly compute an arbitrary functionality without revealing their own private inputs and outputs. Take a concrete example to illustrate it. Assume that there are three people: Alice, Bob and Charlie with respective inputs x, y and z denoting their salaries. Now, they want to find

together but none of them learns the knowledge of the others’ salaries.

A simple solution is that there exists a fair third-party getting all salaries from them and telling them the maximal value of question. In this solution, third-party has the knowledge of all salaries such that it may become single point of failure. Therefore, the mission of SMPC is to remove this flaw and keep the own input privately.

---

Secret Sharing Scheme：

A secret sharing scheme provides a method of sharing a secret among participants. Meanwhile, the secret can be reconstructed by any authorized group of all participants. And non-authorized group can not gain any advantage in discovering the secret.

The most useful among secret sharing schemes is (t,n) threshold sharing scheme. Here n is the total number of all participants and t is the threshold of the scheme such that any t of n people can recover the secret while less than t of n people can not do. The first threshold secret sharing scheme is invented independently by Adi Shamir and George Blakley.

Shamir Secret Sharing (Lagrange Interpolation):

The core idea behind this scheme is that any polynomial of degree t can be determined by t+1 values. In this scheme, a dealer sets a_0 to be the secret and chooses random integers

and forms the polynomial

Next, the dealer chooses n distinct random values x_1,…, x_n, and computes

The dealer sends the pair

to the i-th participant.

Secret recover: Suppose that t participants want to recover the secret

Without loss of generality, we are able to assume that the data of t participants are

After collecting these data, they have the following system of linear equations:

By using Gaussian elimination, someone can solve the above equation and thus recover the secret.

Tassa Secret Sharing (Birkhoff Interpolation):

Tassa Secret Sharing is an extension of Shamir Secret Sharing, which is also a (t,n) threshold sharing scheme. However, the access structure is more complex. In this scheme, the dealer first also chooses a polynomial of degree t-1 with random coefficients and sets his/her secret as the constant term. In addition to choosing different random values x_1,…, x_n, the dealer also picks a non-negative integer n_i, which is the order of derivative and computes

Next, the dealer sends

to i-th participant.

Secret recover: Recover the secret in Tassa Secret Sharing is more subtle. We use an example to explain it.

Example: Let t = 2 and n = 3. Then a dealer chooses a polynomial to be

Here 2 is the chosen secret.

The dealer chooses

and then computes

respectively. Now, you are able to notice that two shares (n_i, x_i, y_i):

1. (1,3,3)
2. (1,4,3)

can not recover the secret 2, because the information of the secret is killed by derivative. However, the shares

1. (0,1,5)
2. (1,4,3)

or

1. (0,1,5)
2. (1,3,3)

recover the secret by Gaussian elimination. This case implies that any set in the access structure must involve the share (0,1,5). This property in general can be realized as any authorized set in Tassa Secret Sharing must include a share with rank 0. Here rank 0 means the order of derivatives is 0. This is an important property that the shares generated by Tassa secret sharing can display different power character in business models. In summary, Tassa Secret Sharing is by introducing the derivative in Shamir Secret Sharing.

---

Homomorphic Encryption:

“Homomorphism Encryption” is a compound word that can be respectively explained by each word. Encryption is the process of encoding a message that only authorized parties can access it. Homomorphism is an algebraical structure-preserving map between two algebraic structures of the same type (such as two groups corresponding to partially homomorphic encryption, or two rings corresponding to fully homomorphic encryption). Combining those two semantic meanings, homomorphic encryption can be defined as a category of encryption that allows users to perform some computations on ciphertexts such that we are able to obtain the expected plaintext after decrypting the end ciphertext. We use an example to illustrate it:

Goal：

• Bob wants to compute 3 + 4.

A Scenario：

• A straight solution is computing 3+4 performed by his personal PC.
• Now, we assume that his personal computer can not execute this complicated computation.
• An alternative is cloud-computing. However, these data (i.e. 3 and 4) may unfortunately involve sensitive information such that he can not delegate cloud-computing to achieve them directly.

A Solution：

1. Bob generates an encrypt function E and the corresponding decrypt function D.
2. Bob computes encryptions E(3) and E(4) and sends them to a cloud-server.
3. The cloud-server performs
   C:=E(3) * E(4) (i.e. this value is equivalent to E(3+4))
   and sends the result to Bob, where * is a particular algorithm for two ciphertexts.
4. Bob uses D to decrypt the ciphertext C and obtain the desired result 3+4.

The cloud server is able to do correct computations without acknowledging the corresponding plaintexts in this working flow. Therefore, a homomorphic encryption is a method to compute confidential data without leaning anything about plaintexts such that it becomes very useful.

In our applications, we focus on partially homomorphic encryption(abbrev. PHE), which is an asymptotic cryptosystem and only permits one operation on the set of ciphertexts. In addition to homomorphism, we usually ask for an extra property for PHE: Semantic security. In brief, what is so-called semantically secure in an asymptotic cryptosystem is that it must be infeasible for a computationally bound adversary to derive significant information about a plaintext when given only its ciphertext and the corresponding public encryption key. In summary, the properties of PHE are shown as follows:

1. There are a private key and the corresponding public key
   (asymmetric cryptography).
2. There exists a homomorphic map from the set of plaintext to the set of ciphertext.
3. Semantic security can protect against chosen plain-text attack.

---

Note：

Rosario Gennaro and Steven Goldfeder(abrev. GG) combine the above tools to propose the celebrated work: Fast Multiparty Threshold ECDSA with Fast Trustless Setup. Next, Guilhem Castagnos, Dario Catalano, Fabien Laguillaumie, Federico Savasta, and Ida Tucker(abrev. CCLST) use different homomorphic encryption scheme in GG’s protocols to avoid doing range proof. We implement the above two signer protocols in Alice.

GG: Paillier cryptosystemCCLST: CL homomorphic scheme

In this article, we only introduce these topics roughly. More details about DKG and Signer can be found in the following Reference 1 and 2.

Thanks to Yu-Te Lin.

Reference:

1. Fast Multiparty Threshold ECDSA with Fast Trustless Setup
2. Bandwidth-efficient threshold EC-DSA
3. Hierarchical Threshold Secret Sharing
4. An Introduction to Mathematical Cryptography
5. Linearly Homomorphic Encryption from DDH
6. https://en.wikipedia.org/wiki/Homomorphic_encryption
7. https://en.wikipedia.org/wiki/Secure_multi-party_computation

---

本文由 AMIS ChihYun Chuang 提供

原文連結