Blind signature scheme based on discrete logarithm problem

me and is another 
important criterion for assessing the security of the scheme. 
2.1.2. Attack to reveal the origin of a signed message 
 With the RSA blind signature scheme as described above, to determine the identity of the 
person who created the signed M can be done. Because at the signing time, the signer (A) 
does not know the contents of M, while A knows the identity of the person requesting signer 
77 
 Электромагнитные волны и электронные системы №5 за 2015 г. 
(B). Assuming the identity of the B is the ID B, to determine the identity of the person 
requesting sign on the message M and the signature s respectively; each time when signing 
the A need to store values s' and the identity of the person requesting the ID B, It can determine 
the identity of the person requesting signer (ID B) from the signed message M and the 
signature s corresponding by an algorithm is as follows: 
 Algorithm 1.1 : 
 Input: (M,s), {(s i’, ID Bi )| i=1,2,N}. 
 Output: ID B. 
 [1]. m ← H (M ) , i = 0 
 [2]. select: (si’, ID Bi ) 
 −d
 [3]. k* ← si '×m mod n 
 [4]. if gcd( k*, n) ≠ 1 then 
 [4.1]. i ← i +1 
 [4.2]. goto [2] 
 [5]. s* ← s'× (k *)−1 mod n 
 [6]. if (*s ≠ s) then 
 [6.1]. i ← i +1 
 [6.2]. goto [2] 
 [7]. return ID Bi 
 Comment : From 1.1 shows that, if N is not large enough then it is not very hard to 
determine the name of who originated the message. In other words, the RSA blind signature 
scheme is not safe if the number of signed messages is not large enough. 
2.2. The DSA Blind Signature Scheme 
2.2.1. The improvement of DSA signature scheme 
 The system parameters of the improvement of DSA signature scheme [7] consits of p 
 *
prime, q is a prime divisor of (p-1) and a primitive root g ∈ Z p has odd is q. The private key 
 x
of signer is x ∈ Z q and y = g mod p is a public key respectively. In order to sign on M has a 
values m ∈ Z q ( m = H (M ) ,H(.) is a hash function), the signer chosses a random k ∈ Z q and 
calculate: 
 R = g k mod p 
 r = R mod q 
 s = (k × m + x × r) mod q 
 M’s signature is (r,s). 
 Check the validity of the signature (r,s) with m 
 m−1
 T = (g s × y −r ) mod p 
78 
 Электромагнитные волны и электронные системы №5 за 2015 г. 
 m is representative value of the message M. 
 The signature is considered valid if satisfied: 
 r = T mod q 
2.2.2. The DSA Blind Signatue Scheme 
 From the improvements of DSA signature scheme, L. Jan Camenisch, Jean-Marc 
Piveteau, Markus A. Stadler [9] proposed a new blind signature scheme with the procedures 
to establish the signature includes the following steps: 
 k
 1. a) Signer (A) chooses a random k ∈ Z q then calculates R' = g mod p 
 b) A checks if gcd( R',)q ≠ 1 then perform back to a) else, A sends R to (B). 
 α β
 2. a) The B chooses 2 values α, β ∈ Z q and calculates R = (R') × g mod p . 
 b) The B checks if gcd( R',)q = 1 then calculates: m' = α × m × R'×R −1 mod q then 
 sends m’ to the A. Else, B repeats step a). 
 3. The A calculates s'(= k × m'+x × R )' mod q then sends to the B. 
 4. The B calculates (r,s) as : r = R mod q , s = s'( ×R × (R')−1 + β × m) mod q . 
 Procedure to check the validity of the signature (r,s) is identical to the above procedure. 
2.2.3. Attack to reveal the origin of a signed message 
 In order to attack to reveal the origin of the signed message M, the signer A need to store 
parameters {R’,m’,s’} and ID B in each time he/she signs. The A can identify the B by the 
following algorithm: 
 Algorithm 1.2 : 
 Input: (M,r,s), {(Ri’, mi’,s i’,ID Bi )| i=1,2,N}. 
 Output: ID B. 
 [1]. m ← H (M ) , i = 0 
 [2]. select: (Ri’, mi’, si’, ID Bi ) 
 −1
 [3]. α ← mi '×m × r ×(R') mod q 
 −1 −1
 [4]. β ← m × (s − si '×r × (R') )mod q 
 α β
 [5]. R ← (Ri ') × g mod p 
 [6]. r* ← Rmod q 
 [7]. if (*r ≠ r ) then 
 [7.1]. i ← i +1 
 [7.2]. goto [2] 
 [8]. return ID Bi 
 Comment : The algorithm 1.2 shows that, if N is not large enough then the determination of 
the identity of the B(who is author of M) is entirely possible. In other words, the DSA blind 
signature scheme is not safe if the number of signed M is not big enough. 
79 
 Электромагнитные волны и электронные системы №5 за 2015 г. 
 2.3. Attack on Nyberg-Rueppel blind signature scheme 
2.3.1. Nyberg-Rueppel signature scheme 
 The system parameters of K. Nyberg và R. A. Rueppel scheme [8] are the same as the 
improvement DSA parameters scheme. On order to sign on the message M which has 
representative value as m ∈ Z p , the signer chooses a random value k ∈ Z q and calculate: 
 r = m × g k mod p 
 s = k + x. r mod q 
 The signature on the message M is a pair (r,s). The signature is validity if the below 
equation is satisfied: 
 m = y −s × g r × r mod p 
 (m is a representative value of M). 
2.3.2. Nyberg-Rueppel blind signature scheme 
 From Nyberg-Rueppel signature scheme, Jan L. Camenisch, Jean-Marc Piveteau, Markus 
A. Stadler [9] proposed a new blind signature scheme with 4 steps as follows: 
 k
 1. The A (signer) chooses a value k ∈ Z q and calculate r' = g mod p then sends to the B 
 (who requests the A to sign). 
 *
 2. a) The B chooses two random values α ∈ Z q , β ∈ Z q and calculate 
 r = m × g α × (r')β mod p , m' = r × β −1 mod q . 
 *
 b) The B checks if m'∈ Z q then sends m’ to the A. Else B repeats step a). 
 3. The A calculates s'(= k + x × m )' mod q then sends to the B. 
 4. The B calculates s = s'( ×β + α) mod q 
 The A’s signature on the message M is (r,s). 
 Procedures for checking the validity of the scheme similar to the Nyberg-Rueppel signature 
scheme. That is: the signature (r, s) is considered valid if satisfies the equation: 
 m = y −s × g r × r mod p 
 (m is a representative value of M). 
2.3.3. Attack to reveal the origin of a signed message 
 In order to attack to reveal the origin of the signed message M, the signer A need to store 
{r’,m’,s’} and ID B for each signature. The A can determine the identity of B using the 
following algorithm: 
 Algorithm 1.3 : 
 Input: (M,r,s), {(ri’, mi’,s i’, ID Bi )| i=1,2,N}. 
 Output: ID B. 
80 
 Электромагнитные волны и электронные системы №5 за 2015 г. 
 [1]. m ← H (M ) , i = 0 
 [2]. select: (ri’, mi’, si’, ID Bi ) 
 −1
 [3]. β ← r × (mi ') mod q 
 [4]. α ← (s − si '×β )mod q 
 * α β
 [5]. r = m × g × (ri ') mod p 
 [6]. if (*r ≠ r) then 
 [6.1]. i ← i +1 
 [6.2]. goto [2] 
 [7]. return ID Bi 
 Comment : Algorithm 1.3 shows that, if N is not large enough then the determination of 
the identity of the B(who is author of M) is entirely possible. In other words, the Nyberg-
Rueppel blind signature scheme is not safe if the number of signed M is not big enough. 
 3. PROPOSED NEW BLIND SIGNATURE SCHEME 
 Through the analysis of some blind signature schemes in section 2 showed "blind" a 
message with a secret parameter in the RSA blind signature scheme, or with 2 parameters as 
in the DSA and Nyberg-Rueppal still be able to find the true origin of the signed message (the 
identity of the person requesting to sign). This section presents the construction of some new 
blind signature schemes were developed from the Schnorr signature scheme [10], this new 
schemes is only 2 parameters used in the secret scheme DSA and Nyberg-Rueppal but not 
allow the signer or anybody can determine the origin of the signed message. 
3.1. Schnorr signature scheme 
 The scheme based on the hard of the discrete logarithm problem (DLP) was proposed by 
C. Schnorr in 1991, which is used as a basis for developing a new blind signature scheme. 
Schnorr signature scheme consists of algorithms to form key and parameters as follows: 
3.1.1. Form parameters and key 
 Algorithm 2.1 : 
 Input: p, q, x. 
 Output: g, y, H(.). 
 [1]. g ← h(p − 1) / q mod p , 1 < h < p 
 ∗ a
 [2]. select H :{} 0,1 Z q 
 [3]. y ← g x mod p 
 [5]. return {g,y,H(.)} 
 Comment : 
 - p, q: are prime numbers satisfied: q|(p-1). 
 - x, y: are the private and public keys of the signer. 
81 
 Электромагнитные волны и электронные системы №5 за 2015 г. 
3.1.2. Forming the signature 
 Algorithm 2.2 : 
 Input: p, q, g, x, k, M. 
 Output: (e,s). 
 [1]. r ← g k mod p 
 [2]. e ← H( r || M ) 
 [3]. s ← (k − x. e)mod q (2.1) 
 [4]. return (e,s) 
 Comment : 
 - Operator “||” is to merge 2 string of bit/character. 
3.1.2. Check the signature 
 Algorithm 2.3: 
 Input: p, q, g, y, M, (e,s). 
 Output: (e,s) = true / false . 
 [1]. u ← g s × y e mod p 
 [2]. v ← H( u || M ) 
 [3]. if ( v = e ) then {return true } 
 else {return false } 
 Comment : 
 - If the result is true then the signature (e,s) is valid, so the origin and integrity of the 
 message M should be asserted; Else, the signature is fake and/or the content of the message 
 M is no longer integrity. 
3.2. Proposed new blind signature scheme 
The new scheme, which is based on the Schnorr blind signature scheme, consists of algorithm 
to form key and parameters and also algorithm to validate the signature as follows: 
3.2.1. Form key and parameters 
 Algorithm 2.4 : 
 Input: p, q|(p-1), x. 
 Output: g, y, H(.). 
 [1]. g ← h(p − 1) / q mod p , 1< h < p 
 ∗ a
 [2]. select H :{} 0,1 Z q 
 [3]. y ← (g)−x mod p 
 [5]. return {g,y,H(.)} 
3.2.2. Form the signature 
 Algorithm 2.5: 
 Input: p, q, g, x, y, α, β, k , M. 
 Output: (e,s). 
 k
 [1]. ra ← g mod p 
82 
 Электромагнитные волны и электронные системы №5 за 2015 г. 
 α β
 [2]. rb ← (ra ) × (y × g) mod p 
 [3]. e ← H( rb || M ) 
 −1
 [4]. eb ← α ×(e − β )mod q (2.2) 
 [5]. sa ← (k + x × eb )mod q 
 [6]. s ← (α × sa + β )mod q (2.3) 
 [7]. return (e,s) 
 Comment : 
 - Steps [1] to [5] are done by the A. 
 - Steps [2], [3], [4], [6] and [7] is done by the B. 
 - The A chooses a system parameter A sitisfies: 1< k < q. 
 - Parameters α, β are chossen by the B and sitisfies: 1 < α, β < q. 
 - {x,y} is a key pairs private/public of A. 
3.2.3. The signature validity 
 Algorithm 2.6: 
 Input: p, q, g, y, M, (e,s). 
 Output: (e,s) = true / false . 
 [1]. u ← ()g s × (y)e mod p 
 [2]. v ← H( u || M ) 
 [3]. if ( v = e ) then {return true } 
 else {return false } 
3.2.4. The correctness of the proposed new scheme 
 From: 
 u = g s × y e mod p = g (.α sa +β ) × y (.α eb +β ) mod p
 = g α.( k+ x.) eb +β × g −x.(α .eb +β ) mod p
 = g k.α × g x.. eb α × g β × g −x.. eb α × g −x.β mod p 
 k α −x β β α β β
 = ()()g × g × g mod p = ()ra × y × g mod p
 α β
 = ()ra × ( y × g) mod p = rb
 We have: v = H( u || M ) = H( rb || M ) = e 
 This is to prove. 
3.2.5. The security of the proposed new scheme 
 Similar to the digital signature scheme, the security of the new scheme is also proposed to 
be assessed by the ability to: 
 - Anti-attack reveals the secret key. 
 - Anti Fake signature attack. 
 In addition, a blind digital signature scheme, its security level is also evaluated through 
resistance attack originating reveal a signed message. The requirement here is that, after the 
83 
 Электромагнитные волны и электронные системы №5 за 2015 г. 
message M was signed, the signer A as well as any other user is not knowable the message M 
are created from the B (who requires to sign). 
 a) Resistant to attack reveals the secret key and the fake signature 
 Security of the proposed new scheme is based on the safety of the Schnorr scheme [9]. In 
terms of resistance to attack reveals the secret key and resistant to fake signatures, it can be 
seen that the security of two schemes are the same. 
 b) Resistance to attack reveals the origin of the signed message 
 From algorithm 2.5 shows that, the parameters{ra,e b} and the identity of the B (ID B) are 
stored together, The signer A can determine the relationship between {M,(e,s)} and ID B, 
which means that the identify of the B can be determined from the message M and the 
corresponding signature (e,s), if from algorithm (2.2) and (2.3) the signer A may determine 
the pairs ( α,β). Indeed, if the A knows ( α,β) then he can completely identify the ID B by the 
algorithm as follows: 
 Algorithm 2.7 : 
 Input: {(rai , e bi , ID Bi )| i=1,2,N}, M, α, β. 
 Output: ID Bi . 
 [1]. m ← H (M ) , i = 0 
 [2]. select: (rai ,ebi , ID Bi ) 
 α β
 [3]. rbi * ← (rai ) × (y × g) mod p 
 [4]. ebi * ← H( rbi ||* M ) 
 [5]. if ebi *≠ ebi then 
 [5.1]. i ← i +1 
 [5.2]. goto [2] 
 [6]. return ID Bi 
 Comment : 
 Algorithm 2.7 shows that the security of the new scheme proposed in terms of the 
ability to to keep secret the origin of the message depends on the level of difficulty of finding 
the secret parameters ( α, β) by solving (2.2) or (2.3). The computation of the parameters ( α, β) 
by solving (2.2) or (2.3) is difficult as finding the secret keys (k, x) of the Schnorr scheme 
from the solving (2.1). 
 4. CONCLUSION 
 From the analysis of the weaknesses of some published blind signature schemes, the paper 
proposes a new blind signature scheme was developed from the Schnorr scheme, The new 
scheme has a higher level of security in comparison with other schemes in a field of the 
possibility of attacks against reveals the origin of the signed message. This is a very important 
factor to allow a blind signature scheme can be applied in practice. 
84 
 Электромагнитные волны и электронные системы №5 за 2015 г. 
 REFERENCE 
 D. Chaum, “Blind signature systems”, Advances in Cryptology-CRYPTO’83 , Plenum 
 [1]. 
 Press, 1984, pp. 153-156. 
 D. Chaum, A. Fiat, M. Naor, “Untraceable Electronic Cash”, Advances in 
 [2]. 
 Cryptology,Crypto’ 88, LNCS 403, Springer Verlag, pp. 319-327. 
 D. Chaum, “Privacy Protected Payment”, SMART CARD 2000 , Elsevier Science Publishers 
 [3]. 
 B.V., 1989, pp. 69-93. 
 N. Ferguson, “Single Term Off-line Coins”, Advances in Cryptology, Eurocrypt’93, LNCS 
 [4]. 
 765, Springer Verlag, pp. 318-328. 
 D. Chaum, B. den Boer, E. van Heyst, S. Mjolsnes, A. Steenbeek, “Efficient Offline 
 [5]. Electronic Checks”, Advances in Cryptology, Eurocrypt’89, LNCS 434, Springer Verlag, 
 pp. 294-301. 
 B. C. Rivest R., Shamir A., Adleman L. (1978), “A Method for Obtaining Digital 
 [6]. Signatures and Public Key Cryptosystems ”, Communications of the ACM, Vol. 21, 
 No. 2, pp. 120 – 126. 
 National Institute of Standards and Technology, NIST FIPS PUB 186-3. Digital 
 [7]. 
 Signature Standard, U.S. Department of Commerce, 1994. 
 K. Nyberg, R. A. Rueppel, “A New Signature Scheme Base on the DSA Giving 
 [8]. Message Recovery”, 1st ACM conference on Computer and Communications 
 Security , November 3 – 5, Fairfax, Virginia. 
 Jan L. Camenisch, Jean-Marc Piveteau, Markus A. Stadler , “Blind Signatures Base on 
 [9]. 
 Discrete Logarithm Problem”, Swiss KWF Foundation, grant no. 2724.1. 
 C. P. Schnorr, “Efficient signature generation by smart cards”, Journal of Cryptology, 
[10]. 
 vol. 4, pp. 161 – 174, 1991. 
85