I.

Design of Threshold Blind Signature Scheme

Duc-Liem Vo and Kwangjo Kim

International Research center for Information Security (IRIS)

Information and Communications University (ICU), Korea

Abstract

Threshold signature and blind signature are playing important roles in cryptography as well as practical applications such as e-cash and e-voting systems. In this paper, we present a new threshold blind digital signature based on pairings without a trusted third party. Our scheme operates on Gap Diffie-Hellman group, where Computational Diffie-Hellman problems are hard but Decision Diffie--Hellman problems are easy. For example, we use pairings that could be built from Weil pairing or Tate pairing. To the best of our knowledge, we claim that our scheme is the first  threshold blind signature using pairings with provable security in the random oracle model.

Introduction

Digital signature is an essential comp-onent in cryptography. Depending on its purpose, the digital signatures can provide the various setting.

A threshold signature scheme dist-ri-butes the signing abilities to a group of signers such that a digital signature on a message cannot be produced by a predetermined number of signers. With this property, misbehavior caused by a single dishonest signer will be eli-minated in many applications. A blind signature scheme, on the other hand, gives users ability to get a digital signature from a signer without revealing message content. This pro-perty is very important for imple-menting e-voting, e-com-merce, and e----payment systems, etc.

A threshold blind signature combines a threshold signature and a blind one to exhibit both properties. Therefore, a threshold blind sig-nature while giving user ability to get sig-nature on a message without revealing its con-tent, still maintains the shared secret key to be distributed among signers.

In this paper, we propose a new threshold blind signa-ture scheme based on pairings. Working on an elliptic curve over a finite field, our proposed signature scheme has achieved efficiency in terms of the signature size compared to the previous schemes [14] and [15]. We also prove the security of our signature scheme in a formal way.

Organization: Some background on bilinear pairings and relevant tools are stated in Section II. In Section III, we describe our proposed thres-hold blind signature scheme. Section IV analyzes the security aspects of the proposed scheme. In Section V, we will evaluate performance of our scheme. Section VI is concluding remark.

II.  Preliminaries

1. Concepts of bilinear pairings

We summarize some concepts of bilinear pairings using similar notations used by Zhang and Kim [23] which was used to design ID-based blind signature and ring signature based on pairings.

Let G1 and G2 be additive and multip-licative groups of the same prime order q, respectively. Let P is a generator of G1. Assume that the discrete logarithm problems in both G1 and G2 are hard. Let e:G1×G1→G2 be a pairing which satisfies the following properties:

1. Bilinear: e(aP,bP') = e(P,P')ab for all P, P'∈G1 and all a,b∈ℤ.

2. Non-degenerate: If e(P,P') = 1 for all P'∈G1 then P = O.

3. Computable: There is an efficient algorithm such as [1] to compute e(P,P') for any P, P'∈G1.

Group G1 is called Gap-Diffie-Hellman (GDH) group if in this group, Computational Diffie--Hellman (CDH) problems are hard but Decision Diffie-Hellman (DDH) problems are easy. Throughout this paper, G1 is GDH group of the prime order q.

2. Blind signature scheme based on GDH problem

To propose the threshold blind signature scheme, we build a blind version of the signature scheme in [4] defined as follows:

Let P be a generator of G1. Public in-for-mation is I=(q,P,H) where H:{0,1}*→G1 is an one-way hash function. A new blind GDH sig-na-ture scheme BGS=(BK,BS,BV), where BK, BS, and BV are key generation, blind signing and verification protocol, respectively, is defined as:

-BK(I): Pick randomly s∈R ℤq and compute Q=sP. Return the public key pk and the secret key sk, where pk=(q,P,H,Q), and sk=s.

-BS(I,sk,M): The user wants a message M∈{0,1}* to be signed blindly. He picks a random number r∈Rℤq and computes a blind message M' of the message M, M'=H(M). He sends M' to the signer. The signer signs on M', σ'=sM' and sends back σ' to the user. Receiving σ', the user unblinds it and gets the signature of the message M, σ= r-1σ' and outputs (M,σ).

- BV(pk,M,σ): If VDDH(P,Q,H(M),σ)=1 then return 1 else return 0, where VDDH() is an efficient algorithm which solves the DDH problem in G1.

The security of the proposed blind signature will be discussed in Section 4.

III.  Proposed Scheme

The threshold blind signature schemes TBS includes of three protocol: Key generation TBK, Signature generation TBS, and Signature verification TBV protocols.

1.  Key generationTBK

Suppose that there are n players involved in the TBK protocol to make a (t,n)-threshold scheme DKG [9], where n≥ 2t-1.

Let P and P' (i.e., P'=βP for some β∈ℤq) be ge-ne-rators of G1. Denote n players involving in TBK as {L1, L2,..., Ln}. The public key and the secret key of this group of players are Q and s, respectively. The public share of the player Li is Qi and the corresponding secret share is si, for i=1, 2,..., n.

Each player Li behaves as the following to generate a shared secret.

G1. At first, Li sends its information.

Select randomly (uniformly distributed as in [18]) ai and bi∈ℤq, keeps them secret.

Pick up randomly two polynomials fi(x) and f'i(x) over ℤq of degree at most t-1 such that fi(0)=ai0 and f'i(0)=bi0. Let fi(x)=ai0 + ai1x + ...+ ai,t-1xt-1 and f'i(x)=bi0 + bi1x +...+ bi,t-1xt-1. These polynomials are kept secret by each player.

Compute and broadcast Cik=aikP +bikP' for k = 1, 2,..., t-1; sends fi(j) and f'i(j) secretly to each player Lj for j=1, 2,..., n; j≠i.

G2. Li receives information from other players.

(a) After receiving fj(i) and f'j(i) from Lj for j=1, 2,..., n; j≠i, the player Li veri-fies fj(i) and f'j(i) by checking

(1)

If Eq.(1) is verified to be false, Li broadcasts a complaint against Lj.

(b) Each player Lj , who received a complaint from player Li, broadcasts the values fj(i) and f'j(i) satisfying Eq.(1).

(c) Each player marks as disqualified any player that either:

received more than t-1 complaints at (a), or,

answered to a complaint in (b) with values that make invalid Eq.(1).

G3. Build the set of non-disqualified players by denoting this by HP which means a set of honest players.

G4. Computes the secret share si=∑k∈HP fk(i).

G5. Each player Li∈HP broadcasts aikP for k = 0, 1,..., t-1.

Player Li verifies the value broadcast by other players in HP, for each j∈HP, verify:

(2)

If the check fails for index j, play Li sends complaint against Lj by broadca-sting values fj(i) and f'j(i) which satis-fies Eq.(1) but Eq.(2).

For player Lj, who receives at least one valid complaint as above, the other players will use Pedersen's VSS to reconstruct value of aj0, fj(x) and ajkP for k=0,1,...,t-1. Each player in HP sets public key of group as Q = ∑i∈HP ai0P. The corresponding secret key s=∑i∈HP ai0 is distributed to n players but does not appear explicitly in the protocol. Each player has the secret share si and the public share Qi = siP.

2. Signature Generation TBS

Sup-pose that a user A wants to get a signature on the message M blindly from t signers. Denote t signers as S = {Li|1≤i≤t}.

S1. A chooses randomly (unifor-mly dis-tri-buted) r∈ℤq and blinds the message M by computing M'=rH(M). A sends M' and  to every signer Li for i=1,2,...,t.

S2. Signer Li, after receiving M', computes a partial signature σi and sends it back to the user, where σi= siωiM'

S3. A, after receiving σi, verifies σi by:

e(σi,P) = e(ωiM',Qi)          (3)

If Eq.(3) does not hold, A sends M' again to get the correct σi. Otherwise, A computes the signature σ on M:

(4)

3. Verification TBV

The signature σ on a message M is accepted if and only if:

e(σ,P) = e(H(M),Q)	(5)

4. Correctness

Firstly, the correct-ness of the signature scheme must involve the correctness of verification of Eq.(3) in TBS pro-to-col. That means the partial signature σi is valid if the i-th signer is honest. We have:

e(σi,P) = e(ωiM',Qi) = e(ωiM',siP)= e(ωisiM',P)

Secondly, we verify the correctness of the threshold blind signature scheme. The scheme signature σ has a form:

We can get above result by Lagrange interpolation.

The verification using Eq.(5) gives us:

e(σ,P)=e(H(M),Q)=e(H(M),sP)= e(sH(M), P)

Hence, if σ is the valid signature on M, the verification always holds.

IV.  Security analysis

We analyze security of the proposed signature scheme in this session. First, we give definition of the security.

Definition 1. Let TBS=(TBK, TBS, TBV) be the threshold blind signature scheme. TBS is secure threshold blind signature scheme if:

1. Unforgeability. No adversary who corrupts at most t-1 signers, with non----negligible pro-bability, can do one-more forgery attack, that is an ad-----versary cannot produce more than  signature after executing TBS protocol  times.

2. Robustness. Even there exists an adver-sary who can corrupt up to t-1 signers, the TBK and TBS protocols complete success-fully.

1. Blindness

First of all, we state that our proposed sig-na-ture scheme has blind property. Since r is ch-o--s-en randomly from ℤq, therefore M' = rH(M) is also a random element in group G1. Thus signers only receive the random information from the user and there is no way to know the original message.

2. Robustness

The robustness of the proposed signa-ture scheme is shown by the following theorem:

Theorem  1. (Robustness) The threshold blind signature scheme TBS is robust for an adversary who can corrupt t-1 signers among n signers such that n≥ 2t-1 signers.

Proof. Even t-1 signers are corrupted, there always exists any subset of t signers can construct unique the secret key s uniformly distributed in ℤq. Thus TBK completes suc-ces-s-fully. Similarly, in TBS, every partial signature is verified by Eq. (3), and so is the signature σ - Eq. (5). Hence, TBS completes success-fu-l-l-y.	￭

3. Unforgeability

To prove unforgeability of TBS scheme, first we have to prove that the underlying signature scheme BGS is unforgeable and then prove that TBS scheme is simulatable.

Unforgeability

Differ from the standard signatures, the notion of unforgeablity of the blind signatures is about one-more-forgery [19]. The proof of un-for-geability of BGS based on "chosen-target CDH problem and assumption" given below:

Definition 2. (CT-CDH) Let G1 be GDH group of prime order q and P is a generator of G1. Let s be a random element of Zq and Q=sP. Let H:{0,1}*→G1 be a random hash function. The adversary B is given input (q,P,Q,H) and has access to the target oracle TG1 that returns a random point Ui in G1 and the helper oracle cdh-s(). Let qT and qH be the number of queries B made to the target oracle and the helper oracle, respectively. The advantage of the adversary attacking the chosen-target CDH problem Advct-cdhG1(B) is defined as the probability of B to output a set of  pairs ((V1,j1), (V2,j2),...,(Vl,jl)), for all i=1,2,..,l ∃ ji = 1,2,..,qT such that Vi=sUji where all Vi are distinct and qH < qT .

The chosen-target CDH assumption states that there is no polynomial-time adversary B with non-negligible Advct-cdhG1(B).

We have the following theorem:

Theorem  2. If the chosen-target CDH assumption is true in the group G1 then the blind signature scheme BGS is secure against one-more-forgery under chosen message attack.

Proof.(Sketch) If there is any polynomial-time adversary A attacking BGS against one-more forgery under chosen message attack, we always construct a polynomial-time adversary B who can solve CT-CDH problem such that AdvblindBGS(A) = Advct-cdhG1(B).	￭

Simulatable

The simulatable condition means that there exists simulators can simulate the view of an adversary on the execution of TBK and TBS protocols. Since TBK was based on DKG, we can have the same simulator as in [8]. For TBS protocol, we construct a simulator SIM which can simulate the view of an adversary A, whose view is VIEWA(TBS(s1,s2,...sn,M,Q),σ), in the running of TBS protocol. A also can corrupts up to t-1 signers.

The input to SIM is a public key Q, a message M, a signature σ on M and secret shares s1, s2,...,st-1 of corrupted signers.

1. SIM chooses r'∈ℤq randomly.

2. SIM computes partial signature:

σi = r'siωiH(M)  for 1≤ i ≤ t-1.

3. For an uncorrupted signer, SIM computes partial signature as

Denote the information produced by the above simulator SIM as SIM(M, Q, s1, s2,...,st-1). The following theorem shows the simulatable con-dition of TBS scheme:

Theorem 3. VIEWA(TBS(s1,s2,...sn,M,Q),σ) and SIM(M, Q, s1, s2,...,st-1) have the same pro---ba-bility distribution.

Proof. (Sketch) By comparing the information produced by SIM and TBS, we can easily see that it is polynomially distinguishable the view of A and the output of SIM.	￭

Theorem 4. The threshold blind signature scheme TBS is as secure as the blind signature scheme BGS against one-more-forgery under chosen message attack.

Proof. This comes immediately from Theorems 2 and 3	￭

By Theorems 1 and 4 we can state that TBS is secure and robust threshold blind signature scheme.

V. Performance

We compare the proposed signature scheme with the previous ones KKL01 [14], LJY99 [15].

Operation	KKL01	LJY99	Our scheme
Am	2t+1	2t+1	0
M	t+5	2n-t+6	1
E	6	8	0
I	0	0	1
A	N/A	N/A	t-1
S	N/A	N/A	2

Table 1: Computation at a user's side

Operation	KKL01	LJY99	Our scheme
Am	2	2(n-t+1)	0
M	5	2n-1	1
E	8	6	0
I	0	0	0
A	N/A	N/A	0
S	N/A	N/A	1

Table 2: Computation at a singer's side

In these tables, Am, M, E and I mean modu-lar addition, multiplication, exponentiation and inversion, respectively. A and S denote point addition and scalar multiplication on an elliptic curve over a finite field. N/A means Not Available.

Compare to previous schemes, our scheme is very efficient in term of the signature size, especially if the point compression technique is applied.

VI. Concluding remarks

We have proposed a secure and robust threshold blind signature scheme based on bilinear pairings. The scheme was proven as secure as the blind GDH signature scheme in the random oracle model. In addition, our scheme exhibits robustness. Even there exists an adversary who can corrupt up to t-1 signers among n≥ 2t-1 signers, the scheme still completes successfully. Moreover, our scheme achieves efficiency in a sense of the signature size.

Further more, we can add proactive property to our signature scheme using technique [11], [10]. This property makes the signature scheme more secure by coping with mobile adversary. Using DKG, we can achieve proactive property more secure, since original techniques used in-secure distribution method as pointed out in [9].

References

[1]  P.S.L.M. Barreto, H.Y. Kim, B. Lynn and M. Scott, “Efficient Algorithms for Pairing--Based Cryptosystems,” Advances in Cryp-to-logy - Crypto'2002, LNCS 2442, Springer--Verlag, pp. 354-369, 2002.

[2] M. Bellare, C. Namprempre, D. Pointcheval and M.Semanko, “The One-More--RSA-Inversion Problems and the Security of Chaum's Blind Signature Scheme,” Cryptology ePrint Archive - 2001/02.

[3] D. Boneh and M. Franklin, “ID-based Encryption from the Weil-pairing,”  Advan-ces in Cryptology - Crypto'2001, LNCS 2139, Springer-Verlag, pp. 213-229, 2001.

[4] D. Boneh, B. Lynn, and H. Shacham, “Short Signatures from the Weil-pairing,”  Advances in Cryptology - Asiacrypt'2001, LNCS 2248, Springer-Verlag, pp. 514-532, 2001.

[5] A. Boldyreva, “Threshold Signature, Multi-signature and Blind Signature Schemes Based on the Gap-Diffie-Hel-lman-group Signature Scheme,” Public Key Cryptography - PKC 2003, LNCS 2567, Springer-Verlag, pp. 31-46, 2003.

[6] D. Chaum, “Blind Signatures for Untraceable Payments,”   Proc. of Crypto'82, LNCS 1440, pp. 199-203, Springer-Verlag, 1983.

[7] Y. Desmedt and Y. Frankel, “Theshold Cryptosystems,” Advances in Cryptology - Crypto'89, LNCS 435, pp.307-315, Springer--Verlag, 1990.

[8] R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin, “Robust Threshold DDS Signatures,”  Advances in Cryptology - Eurocrypt'96, LNCS 1070, Springer-Verlag, pp. 354-371, 1996.

[9] R. Gennaro, S. Jarecki, H. Krawczyk and T. Rabin, “Secure Distributed Key Generation for Discrete-log Based Cryptosystems,”  Ad---van-ces in Cryptology - Eurocrypt'99, LNCS -1592, Springer-Verlag, pp. 295-310, 1999.

[10] A. Herzberg, M. Jakobsson, S. Jarecki, H. Krawczyk, and M. Yung, “Proactive public key and signature systems,”  ACM Con-fe-ren-ce on Computers and Communication Secu-rity - CCS'97, ACM Press, pp. 100-110, 1997.

[11] A. Herzberg, S. Jarecki, H. Krawczyk, and  M. Yung, “Proactive Secret Sharing Or: How to Cope With Perpetual Leakage,” Ad-van-ces in Cryptology - Crypto'95, LNCS 963, Springer-Verlag, pp. 339-352, 1999.

[12] F. Hess, G. Seroussi and N. Smart, “Two Topics in Hyperelliptic Cryptography,” SAC'2001, LNCS 2259, Springer-Verlag, pp. 181-189, 2001.

[13] A. Joux and K. Nguyen, “Separating Decision Diffie-Hellman from Diffie--Hel-l-man in Cryptographic Groups,”  Cryptology ePrint Archive - 2001/03.

[14] J. Kim, K. Kim and C. Lee, “An Efficient and Provably Secure Threshold Blind Signature,”  International Conference on Information Security and Cryptology - ICISC'2001, LNCS 2288, Springer-Verlag, pp. 318-327, 2002.

[15] C.L. Lei, W.S. Juang and P.L. Yu, “Provably Secure Blind Threshold Signatures Based on Discrete Logarithm,”  National Computer Symposium 1999, pp. C198-C205, 1999.

[16] M. Ohkubo, F. Miura, M Abe, A. Fujioka and T. Okamoto, “An Improvement on a Practical Secret Voting Scheme,”  Informa-tion Security Workshop - ISW'99, LNCS 1729, Springer-Verlag, pp. 225-234, 1999.

[17] T.P. Pedersen, “A Threshold Cryptosystem with-out a Trusted Party,”   Advances in Cryptology - Eurocrypt'91, LNCS 547, Springer--Verlag, pp. 522-526, 1991.

[18] T.P. Pedersen, “Non-interactive and Information-theoretic Secure Verifiable Secret Sharing,”   Advances in Cryptology - Crypto'91, LNCS 576, Springer-Verlag, pp. 129-140, 1991.

[19] D. Pointcheval and J. Stern, “Provably Secure Blind Signature Schemes,”  Advan-ces in Cryptology - Asiacrypt'96, LNCS 1163, Springer-Verlag, pp. 252-265, 1996.

[20] D. Pointcheval and J. Stern, “Security Argument for Digital Signatures and Blind Signatures,”  Journal of Cryptology,  Sprin-ger--Verlag, Vol.13 No.3, pp. 361-396, 2000.

[21] A. Shamir, “How to Share a Secret,” Commmunication of the ACM, Vol.22, No.11, pp. 612-613, Nov.1979.

[22] V. Shoup, “Practical Threshold Signatures,” Advances in Cryptology - Eurocrypt'2000, LNCS 1807, Springer-Verlag, pp. 207-220, 2000.

[23] F. Zhang and K. Kim, “ID-Based Blind Signature and Ring Signature from Pairings,”  Advances in Cryptology - Asiacrypt'2002, LNCS 2501, Sprin-ger--Verlag, pp. 533-547, 2002.