PROCESSING A NEW BLIND SIGNATURE BASED ON ELGAMAL

DAMERI A.¹*, BOOSTANI R.^2
1IT Masters, Electronic Collage, Shiraz University, Shiraz- 71454, Iran.
²Science & Computer Department, Shiraz University, Shiraz- 71454, Iran.
* Corresponding Author : amirdameri@yahoo.com

Received : 18-09-2012     Accepted : 12-12-2012     Published : 27-12-2012
Volume : 2     Issue : 2       Pages : 66 - 68
Bioinfo Secur Inform 2.2 (2012):66-68

One of the main challenges of blind signature algorithms is their high computational complexity. In order to overcome this problem, a novel scheme is proposed which is a modified version of Elgamal digital signature. Moreover, this algorithm guarantees a high security during the signing process.

Blind signature is a kind of digital signature that should have some properties such as enforceability, unlikability and untracibility [13] . The enforceability provides the signer to be the only one who produces a valid sign. The unlikability property forms the sign such that only the requester can make a relation between the protocol and sign. Also, blind signature should have the untracibility property which assures the requester not being tracked by the signer. Blind signature algorithms are used in many applications such as E-voting [5,11] , E-payment [6,7] and the data base security [2] . In this paper a new blind signature is offered to reduce the complexity of signing process. The proposed scheme is also provide a high security during the process. The first blind signature was presented by Chaum, et al. [1] And was based on Rivest, Shamir, Adleman (RSA) digital signature which suffered from chosen plain text attack. From another side, Elgamal [3] proposed a digital signature which is still a state of art algorithm for cryptography. Then, Alseyyed, et al. [8] offered a new blind signature based on Elgamal digital signature which has been attacked and lost its security. Ibrahim, et al. [10] Presented an E-voting system based on blind signature. In their system, voter's privacy is guaranteed by using both blind and digital signatures to increase the authentication and confidentiality. Xenakis, et al. [9] Explore the security related procedures that are required for the successful development and deployment of electronic voting in legally-binding government elections. In view of the increased complexity of the e-voting processes which can involve multi-channel e-voting options and the increase in the number of agents involved in the administration of E-elections. They relate procedural security to the need for transparent allocation of responsibilities among the different agents and used a blind signature to gain that. Jena, et al. [12] Presented a novel Blind Signature Scheme (BSS) based on Nyberg-Rueppel Signature Scheme (NRSS) using Elliptic Curve Discrete Logarithm Problem (ECDLP). This algorithm is employed in off line digital cash payments [12] which can be easily extended to E-voting application. Cetinkaya, et al. [13] formal definitions of security requirements for cryptographic voting protocols (privacy, eligibility, uniqueness, fairness, receipt-freeness, accuracy, and individual verifiability) were provided, and elaborate checklists for each requirement were presented. The Voting problem is clearly defined in terms of security requirements. The voting problem arises from the trade-off between receipt-freeness and individual verifiability. His research suggests the Predefined Fake Vote scheme as an applicable solution to overcome the voting problem [13] .
Furthermore, Junjie, et al. [14] Illustrated a new identity-based proxy blind signature scheme which satisfies unforgeability, non-repudiation, blindness, unlinkability and other security requirements of proxy blind signatures and produced less traffic [14] a new algorithm is designed based on Elgamal method to improve the security and complexity of blind signature. As follow in the second part Elgemal digital signature and Elsayed Blind signature will be explained; in the Third part a modified new digital signature based on Elgemal Digital signature will be represented and using that a new blind signature shall be offered and would be analyzed.

In this part Elgamal Digital Signature [3] will be described and base on that the Elsayed Blind Signature will be represented which is covered by Elgamal digital signature.

Elgemal digital signature was presented in 1985 for the first time. This scheme is a non-deterministic model which means a data can have many different signs. In this way, first a prime number P and a generator value are chosen. The other parameter Pof the Elgamal algorithm is which are the public keys and α is a primary key.

For signing a data like x, first is randomly chosen and the signing process is preformed as which are defined as follows:





Where are signer’s private keys and are the signs of the data.

To confirm a verifier, the following process should be carried out. If the equation works properly, then the verifier approves the sign unless it is not a valid sign.

Elsayed,, et al. [8] proposed a blind signature schemes which are based on Elgamal signature. There are three phases in their schemes explained as follows:

The requester chooses two random numbers k and h such as that and where p is a large prime number. Next, the requester computes and where g is a primitive element of p. Finally, the requester sends m' to the sign-er to be signed.

After receiving the blind data the (m'), signer generates a blind signature s' from m' such that:
s' = k^-1 (m'-xr)mod(p-1) (3)

The requester receives the message m and its signature s which is signed by the signer as follows.
m = h^-1 m' mod ( p - 1 ) (4)
s = xrk^-1(h^-1-1)+h^-1s' mod (p-1) (5)
A verifier can validate the message m and signature (r,s) using the following equation.
g^m = y^r r^s mod p
In Elsayed schemes, the parameter k is chosen randomly and r is computed by the requester. When the requester received the blind signature s', due to the parameter r, k, s' and m' are known to the requester. The requester can derive the signer's privacy key x from s' as follows.
s' = k^-1 (m'-xr) mod (p-1) x = r^-1 (m'-s'k)mod(p-1)(7)
The requester can make a counterfeit signature with signer's private key. Therefore, Elsayed blind signature scheme is insecure.

In this part two novel algorithms are presented. The proposed schemes can be considered as a modified version of Elgamal signature.

In this algorithm, there is no need to determine the inverse of any parameters which makes the process simpler and also enlarge the search space for the attackers.

To sign the data x first is chosen randomly such as Elgamal signing process but (δ,γ) are defined differ from Elgamal's one. In the proposed algorithm the δ,γ are determined as follows:





So (a,k) are the signer's private keys and (δ,γ) are the signs for x.

If the following equation is satisfied, a verifier accepts the sign for the data

Proof:



Such that:

By using the above digital signature, in this part, a novel blind signature is proposed which not only increase the security but also decrease the complexity of calculation in blind signature. To prove the scheme mathematically, four phases should be considered; blinding, signing, unblinding, verifying.

Consider a requester blinds the data as below by choosing randomly

Where is the blind message and h is a random factor. Finally is sent to the signer.

The signer receives and chooses a random number to calculate





Then the signer sends as a blind signature to the requester.

In this step the requester generates the digital signature from the blind signature which he received from the signer as follows:

Where are the signatures for x.
Proof:

The verifying is done by the following formula:

Compare to Chaum signature scheme, the proposed blinding phase has less computational complexity and is much faster because only an adding operator is employed while RSA blind signature need a powering and a multiplying operators. The verifying phase of the proposed blind signature is slower than Chaum's blind signature consequently; run time of the proposed algorithm is slower than that of the Chaum. Nevertheless, the essential need of a blind signature is its security which Chaum blind signature suffers from the chosen plain text attack while the proposed blind signature is robust to the mentioned attack. The converted DDS [4] blind signature unblinding stage contains multiplying, exponential function and an inverted operator while the proposed algorithm just uses multiplying and adding operators. Beside the algorithm does not need to invert the factor k or any other parameters which means every number can be used for all parameters which makes it harder to be attacked. The new blind signature has just five operating stages which makes it a low computational cost algorithm compare to its rivals. In addition of low computational cost, it has a high security which has been taken form ElGamal mathematics. Therefore, this algorithm can be used as a safe algorithm in e-voting and e-payment protocols because of its simplicity and high security properties.

[1] Chaum D., Fiat A. and Naor M. (1992) Advanced in Cryptology, -CRYPT0'88, Springer-Verlag.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Chaum D. and Pedersen T.P. (2003) Advanced in Cryptrology-CRYPT0'92, 89-105.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Elgamal T. (1995) IEEE Transactions on Information Theory, IT-31(4), 469-472.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Camenisch J.L., Piveteau J.M., Stadler M.A. (2004) Advanced in Cryptology Eurocrypt, 94, Perugia, Italy, 428-432.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Fujioka A., Okamoto T. and Ohta K. (2004) A Practical Secret Voting Scheme for Large Scale.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Fan C.I. and Lei C.L. (2002) Journal of Network and Computer Applications, 25(2), 93-107.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[7] Fan C.I. (2006) Information Sciences, 176(3), 263-284.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[8] Elsayed Mohammed A.E. Emarah and Kh. El-Shennawy (2000) Information Systems for Enhanced Public Safety and Security IEEE/AFCEA, 5153.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[9] Xenakis A., Macintosh A. (2004) 37th Annual Hawaii International Conference on System Sciences.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[10] Ibrahim S., Kamat M., Salleh M., Aziz (2003) 4th National Conference on Telecommunication Technology.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[11] Jinn-Ke Jan, Yu-Yi Chen, Yi Lin (2001) 35th International Carnahan Conference on Security Technology, IEEE.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[12] Jena D., Jena S.K., Majhi B. (2007) 10th International Conference Information Technology.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[13] Cetinkaya O. (2008) Third International Conference on Availability, Reliability and Security.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[14] Junjie He, Chuanda Qi, Fang Sun (2012) International Conference Information Science and Technology.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus