# Introduction to Threshold signature scheme

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 D1,…,Dn, which are then distributed privately to n parties. This enables:

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

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

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  and Frankel  independently proposed a simple and solution for distributed RSA. The decryption key d is additively shared amongst n parties where d = d1 + d2 + · · · + dn, and signing is simply calculated as follows:

s = md= md1· · · mdn (mod N), and each si = mdi (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 < pi, qi, di > 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 .

• 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)  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 < pi, qi, di > : <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 a1, …, at−1 uniformly random from Z𝑝 and defines P(x) = . Party Pi gets share si= 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 Z7:

Distribution: Dealer has secret s=4 and picks . Hence, polynomial . Dealer sends s1=4 to P1, s2=0 to P2, s3=6 to P1, s4=1 to P4.

Reconstruction: When P1, P3 and P4 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 a1, …, at−1 uniformly random from Z𝑝 and defines P(x) = . Party Pi gets share si= 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 .

• 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 a1, …, at−1 uniformly random from Z𝑝 and defines Pi(x) = . Party Pi sends si,j= Pi(j) privately to party Pj. All parties compute their secret key share: . And secret key .
• To decrypt a given ciphertext (c1,c2). Let Q be any subgroup of size t, for example {P1,…,Pt}. Each party Pj 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 . 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 Pi picks ai,1, …, ai,t−1 uniformly random from Z𝑝 in given group G = <g> of order p and defines Pi(x) = . Party Pi shares si,j= Pi(j) privately to party Pj and broadcasts and . Hence all parties Pj can check own share: , compute key share: and compute verification key of Pi : To decrypt a given ciphertext (c1,c2). Let Q be any subgroup of size t, for example {P1,…,Pt}. Each party Pj of Q broadcast similar to DKG scheme then compute . Use Zero knowledge proof to prove Thereafter, compute .

• 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

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

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

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

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

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

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

 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.

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