THRESHOLD SIGNATURE SCHEME

1. Introduction

Assuming there are 20 employees in a company, and if each employee has his or her own copy of the secret key then it is hard to assure on individuals due to compromise and machine break down. In the other hand, if there is a valid signature requires all 20 employees’ signature in the company then it will be very secure but not be easy to use. Therefore we can implement a scheme which requires only sign 5 or more out of 20 employees then it will be valid and that is exactly what a (5,20) threshold signature scheme tries to achieve. In addition, if a threat agent wants to compromise the system and obtain a message, he must compromise at least 5 people in the scheme and that is a harder thing to do compared to a traditional public scheme.

2. Threshold signature scheme

Threshold signature scheme is a branch of public key cryptography and multi-party computation particularly. In a k-out-of-n threshold crypto-system (k, n) where 1 < k ≤ n, we generate and split the secret decryption exponent d into n different pieces D₁,…,D_n, which are then distributed privately to n parties. This enables:

• Knowledge of any k or more D_i pieces makes D easily computable.

• Knowledge of any k- 1 or fewer D_i pieces leaves D completely undetermined (in the sense that all its possible values are equally likely) [1]

2.1. Shared RSA Threshold Scheme

Similarly to traditional RSA, in shared RSA scheme, we have the public components are moduli N= pq and the encryption exponent e where e is co-prime to N. Additionally, both Boyd [2] and Frankel [3] independently proposed a simple and solution for distributed RSA. The decryption key d is additively shared amongst n parties where d = d₁ + d₂ + · · · + d_n, and signing is simply calculated as follows:

s = m^d= m^d₁· · · m^d_n (mod N), and each s_i = m^di (mod N) is called the partial signature or signature share.

Decryption is more complicated as there are more parties who get involved in the scheme. Assuming there are n parties and the prime factors of N remain unknown to every person. Each party Pi now only knows the tuple < p_i, q_i, d_i > and keeps it secret to any other parties, and they are also required to satisfy the four following conditions:

1. p is an unknown big prime number and

2. q is an unknown big prime number and

3. The unknown decryption exponent

4. And ed = 1 (mod φ(N )).

I am going to show a way to encrypt a message and decrypt a cipher text based on Discrete Logarithm Problem presented in [4].

• Encryption: is similar to RSA :
• Decryption: each party computes and then sends to all other parties. Each party knows all and then can recovers the original message (m) [5] as follow:

• Advantages: Simple and easy to deploy.
• Disadvantages: requires a trusted party and there is no verification process to avoid compromised party.

Proof:

Example:

Let p=47 and q=59, then N=pq=2773 and (p-1)(q-1)=2668. Assume e=17, we can calculate the value for d with 17d=1(mod 2668) or d=157. Each party Pi knows the tuple < p_i, q_i, d_i > : <13,19,61>, <11,23,53>, <23,17,43> respectively where p = 47 =13+11+23 ; q=59=19+23+17; and d=157=61+53+43. If the message is ready for the encryption is represent by m=9, then calculation of the ciphertext yields: .

Decipherment of the text requires knowledge of from all parties then it follows that:

M

=9, which is the original message.

2.2. Shamir’s Secret Sharing Scheme and Lagrange Coefficient

A trusted dealer has a secret s and chooses a large prime number p > n, the number of parties. Unless otherwise stated, all arithmetic operations are done modulo p. The dealer picks a₁, …, a_t−1 uniformly random from Z𝑝 and defines P(x) = . Party Pi gets share s_i= P(i) privately from the dealer. To reconstruct the secret s, any t parties come together. They can recover the secret by solving the system of linear equations: . We can also denote .

Proof:

Larrange interpolation over with

Example:

Shamir’s threshold (3,4) over Z₇:

Distribution: Dealer has secret s=4 and picks . Hence, polynomial . Dealer sends s₁=4 to P₁, s₂=0 to P₂, s₃=6 to P₁, s₄=1 to P₄.

Reconstruction: When P₁, P₃ and P₄ come together, we have:

s =

4

2.3. Threshold ElGamal based on Shamir’s Secret Sharing Scheme

2.3.1 Threshold ElGamal scheme

Similarly to traditional ElGamal encryption scheme, in threshold ElGamal, we have the public components are (p,g,h) and private key in threshold environment. The dealer picks a₁, …, a_t−1 uniformly random from Z𝑝 and defines P(x) = . Party Pi gets share s_i= P(i) privately from the dealer. This scheme of both construction and reconstruction of the secret is similar to the previous scheme based on Shamir’s Lagrange.

Example: public key (23, 5, 8) and private key = 6 in a (3,5)-threshold scheme [6].

• Standard ElGamal encryption with message m and public key.

• Decryption

Trusted dealer and every party can receive cipher = (B, c). Assume 3 parties {2,4,5} meet together to compute decryption share:

Trusted dealer computes using Shamir’s Lagrange: . Then compute

However, this scheme still requires a trusted third party (dealer) which is the most disadvantage when being compromised. Broadcasting partial secret information is used to avoid this problem using distributed key generation (DKG) as follow:

• Each party acts as dealer picks a₁, …, a_t−1 uniformly random from Z𝑝 and defines P_i(x) = . Party Pi sends s_i,j= P_i(j) privately to party P_j. All parties compute their secret key share: . And secret key .
• To decrypt a given ciphertext (c₁,c₂). Let Q be any subgroup of size t, for example {P₁,…,P_t}. Each party P_j of Q broadcast then compute . Thereafter, compute .

It is easy to prove that nobody can gain information about , however there is no verification if parties deviate from this scheme. In general, verifiable secret sharing ensures that even if the dealer is malicious there is a well-defined secret that the players can later reconstruct while in standard secret sharing, the dealer is assumed to be trusted. The concept of verifiable secret sharing (VSS) was first introduced in [7]. Therefore, I am going to show you two schemes to verify secret sharing: Feldman’s VSS scheme.

2.3.2 Threshold El-Gamal based on DKG and Feldman’s Verifiable Secret Sharing

Each party P_i picks a_i,1, …, a_i,t−1 uniformly random from Z𝑝 in given group G = <g> of order p and defines P_i(x) = . Party Pi shares s_i,j= P_i(j) privately to party P_j and broadcasts and . Hence all parties P_j can check own share: , compute key share: and compute verification key of P_i :

To decrypt a given ciphertext (c₁,c₂). Let Q be any subgroup of size t, for example {P₁,…,P_t}. Each party P_j of Q broadcast similar to DKG scheme then compute . Use Zero knowledge proof to prove Thereafter, compute .[8]

• Advantages: It does not require any trusted dealer and still can generate the public/private key pair efficiently with verification process.
• Disadvantages: All parties’ identity need to be known to all other parties through every step.

4.Conclusion

Different applied schemes using threshold signature scheme is proposed in this report that includes: RSA shared secret, Shamir’s secret sharing, Elgamal threshold scheme, distributed key generation and verification as well as advantages and disadvantages of each scheme.

-cmxd

REFERENCES

[1] A. Shamir. How to share a secret. Communications of the ACM, 22, 612–613, 1979

[2] C. Boyd. Digital Multisignatures. Cryptography and Coding 1989. Institute of Mathematics and its application, IMA. 241–246, Clarendon Press, 1989

[3] Y. Frankel. A practical protocol for large group oriented networks. Advances in Cryptology – EUROCRYPT ’89, Springer-Verlag LNCS 434, 56–61, 1989.

[4] P. Paillier. Public key crypto-systems based on composite residue classes. Advances in Cryptography - EIROCRYPT ’99. Springer-Verlag LNCS 1070, pp. 72-83, 1996.

[5] H.L. Nguyen, RSA Threshold Cryptograph. University of Bristol, 2005.

[6] Björn Groneberg, Threshold Cryptography slides. University of Potsdam, 2013.

[7] Benny Chor, Shafi Goldwasser, Silvio Micali, Baruch Awerbuch. Verifiable secret sharing and achieving simultaneity in the presence of faults, SFCS '85 Proceedings of the 26th Annual Symposium on Foundations of Computer Science p. 383-395,1985.

[8] Dr. S.J.A. de Hoogh, Threshold Cryptography slides. TU/D, 2014.