International Journal of Scientific & Engineering Research, Volume 5, Issue 4, April-2014 1104
ISSN 2229-5518
A Pairing Free Identity Based Proxy Signature
Scheme
Hassan Elkamchouchi1, Eman Abou El-kheir2, and Yasmine Abouelseoud3
Alexandria University1,3, Kafr El-Sheikh University2, Egypt
Abstract—Digital signature scheme is a method for signing an electronic message. As such, a signed message can be transmitted over a computer network in an authenticated manner. This paper introduces two identity based (id-based) digital signature schemes. The first one, is a signature scheme and the second its extension to a proxy signature scheme in which the original signer delegates his signing rights to a proxy signer. Both schemes don't use the bilinear pairings in the Signcryption and unsigncryption phases. Also, both schemes are based on the elliptic curve discrete logarithm problem (ECDLP). Moreover, the proposed schemes achieve the standard security requirements. the performance of the both schemes is examined. The proposed id-proxy signature scheme reduced computational complexity compared to other scheme in literature.
Index Terms— ID-Based , Digital Signature, Proxy Signature, ECDLP, W ithout Bilinear Pairings
—————————— ——————————
igital signatures offer source authentication in
cryptography. To handle the situations arising in
the digital world related to authentication, differ-
ent types of digital signatures have been developed [1].
The concept of a proxy signature was first introduced
by Mambo et al. [2] in 1996. In a proxy signature
scheme, generally, there are two entities: an original
signer and a proxy signer. The original signer can dele-
gate his signing power to a proxy signer. The proxy
signer can generate a valid signature on behalf of the
original signer. Since then, many proxy signature
schemes have been proposed [3, 4, 5, 6].
The concept of Identity based cryptography (IBC) was first introduced by Adi Shamir in 1984 [11]. Its primary innovation was its use of user identity at- tributes, such as email address, phone number, IP ad- dress instead of digital certificates for encryption and signature verification. This feature significantly re- duces the complexity of a cryptography system by eliminating the need for generating and managing user certificates[12].
Identity based signature is similar identity based encryption. It consists of the four algorithms Set-up, Extract, Signature Generation and Signature verifica- tion. In this scheme signer first obtain her private key associated with her identity and then he gener- ates a signature for message and sends it to receiv- er. After receiving the signature and message the receiver checks the signature using the signer identi- ty and PKG public key. If it is, he returns "Accept" oth- erwise he returns "Reject".
This paper proposes two id-based digital signature schemes; the first one is a id-based digital signature that satisfies unforgeability and verifiability properties,
and the second is its extension to an id-based proxy signature scheme in which the original signer delegates his signing rights to a proxy. The receiver verifies the identities of both the original signer and the proxy signer as discussed in details in the rest of paper.
In this section, we describe the generic frame work for an identity based signature scheme. The frame work of an identity based deterministic signature scheme con- sists of the algorithms described below, namely Setup, Extract, Sign and Verify. An identity based signature scheme is deterministic if the signature on a message by the same user is always the same [13].
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 5, Issue 4, April-2014 1105
ISSN 2229-5518
An id–based signature scheme consists of four phas- es; Setup, Key Generation, Signature Generation and Signature Verification phases [12].
Given security parameter k (usually 160), the PKG
chooses q a large prime number with q > 2k , (a, b) is a
pair of integers which are smaller than q and satisfy
( 4a3 + 27b2 ) mod q ≠ 0 . E is the selected elliptic curve
v2 = [( s − u ) mod q )].Ppub = ( u + H ( m ).da − u ).Ppub
= H ( m ).Qa = v1
The security of the proposed two schemes is based on the elliptic curve discrete logarithm problem (ECDLP) [15]. Up till now, the ECDLP is considered to be hard under the following definition.
Definition 1: The Elliptic Curve Discrete Logarithm Problem (ECDLP) is defined as follows. Let G and Q be two points on an elliptic curve and G is of order n
over the finite field
F : y 2 = ( x3 + ax + b ) mod q . P is the
and n is a prime. The point Q = k .G , where k < n . Giv-
base point or generator of a group of points on E, de- noted as G . Also, O is the point at infinity and n is the order of the point P, with n being a prime number,
en these two points G and Q , find the discrete loga-
rithm of Q to the base G; that is, k .
n.P = O and
n > 2k . The PKG selects a cryptographic
one way hash function
H : { 0 ,1 }*
→ Zq
. The PKG se-
Only the original signer with his/her secrete key
d a
lects a random number
mk PKG
as the master key and
can produce both ( r ,s ) because of the way they are
computes the master public key
Ppub = mk PKG .P . The
computed: r = [( w + da ) mod q ].Ppub = ( u ,v ) ,
PKG keeps mk PKG
secret and publishes the system pa-
s = ( u + H ( m ).da ) mod q . They depend on the sender
rameters params = { a ,b,k ,E ,P ,Ppub ,H }
secret key
d a . Therefore, only the original signer can
The PKG generates the secret and public key pairs for the signer. It then sends the secret keys through a se- cure channel and publishes the public key and the
generate a valid signature.
A verifier can be convinced of the agreement of the signer to the message contents by computing
identities. The PKG calculates the secret keys of the
v1 = H ( m ).Qa ,
v2 = [( s − u ) mod q )].Ppub Then, testing if
three communicating parties as follows:
v1 = v 2 , a verifier then accepts the signature .
da = ( H ( IDa ).mkPKG ) mod q
. The PKG calculates the
signer public key as follows: Qa = da .Ppub
A signer chooses a random number computes:
w ∈ [ q − 1 ]
and
This section discusses the computational cost associat- ed with the proposed ID-based signature scheme. Table
1 shows the symbol definitions that are used in the
r = [( w + da ) mod q ].Ppub = ( u ,v )
s = ( u + H ( m ).da ) mod q
The signer sends ( u ,s ,H ( m )) to the verifier.
The receiver computes:
comparative study. A comparative study of the per- formance of the proposed scheme and other schemes in literature [17,18] is provided in Table 2. Clearly, the proposed scheme is the most efficient.
v1 = H ( m ).Qa
v2 = [( s − u ) mod q )].Ppub
TABLE 1
TIME ABBREVIATIONS
If v1 = v 2 accept the signature
The correctness of the verification equation as follow:
————————————————
• Hassan Elkamchouchi : Elec. Eng. Dept, Fac. of Eng., Alexandria Universi- ty.E-mail: helkamchouchi@ieee.org
• Eman Abou El-kheir: Elec. Eng. Dept, Fac. of Eng., Kafr El-Sheikh Univer-
sity. E-mail: eman.abouelkhair@eng.kfs.edu.eg
• Yasmine Abouelseoud: Eng. Math. Dept, Fac. of Eng., Alexandria Univer-
sity. E-mail: yasmine.abouelseoud@gmail.com
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 5, Issue 4, April-2014 1106
ISSN 2229-5518
An ID-based proxy signature scheme is specified by the following polynomial-time algorithms [16].
Setup: The private key generator (PKG) provides the security parameter k as the input to this algorithm, generates the system parameters params and the mas- ter private key msk. PKG publishes params and keeps msk secret.
The designated proxy signer cannot deny a valid proxy signature generated by him.
A proxy signing key cannot be used for purpose other than generating valid proxy signatures.
An id–based proxy signature scheme consists of six phases; Setup, Key Generation, Proxy Delegation, Proxy Key Generation, Proxy Signature Generation and Proxy Signature Verification phases. The proposed id-based proxy signature scheme is an extension to the proposed id-based signature scheme that discussed in section three.
The set up phase is similar as the id-based signature scheme.
The original signer chooses a random number d and computes
other secret information and outputs a signing key for proxy signature.
• T = d .Ppub = ( α ,b )
• σ = ( d − d .H ( α ,m
)) mod q
a w
Proxy Signature: For generating a signature on a mes-
sage m, the proxy provides his identity ID, his private
• The original signer sends
( α ,σ ,mw
) to the proxy
key , params and the message m as input. This algo- rithm generates a valid proxy signature σ on message m by the proxy.
Informally, the basic security properties for proxy sig- nature schemes can be described as follows [14]:
From a proxy signature, a verifier can be convinced of the original signers agreement on the signed message.
Only the designated proxy signer can generate a valid proxy signature on behalf of the original signer.
Anyone can determine the identity of the corre- sponding proxy signer from a proxy signature.
signer, where mw is a warrant specifying the iden-
tities of both the original signer and the proxy
signer as well as the signing rights of the proxy
agent and possibly a time frame for the validity of
the warrant.
TABLE 2
A COMPARATIVE STUDY OF THE PERFORMANCE OF THE PROPOSED
ID-BASED SIGNATURE SCHEME W ITH THE SCHEMES IN [18, 17]
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 5, Issue 4, April-2014 1107
ISSN 2229-5518
?
The proxy checks if T =σ .Ppub + h( α ,mw ).Qa . If the equa-
tion holds, the proxy signer computes the secrete proxy
v2 = ( u + H ( m ).skp − u ).Ppub
v2 = H ( m ).skp.Ppub = H ( m ).( d p + σ ).Ppub
key
skp = ( d p + σ ) mod q . Then, the proxy signer gener-
v2 = H ( m ).( d p .Ppub + σ .Ppub ) = H ( m ).( σ .Ppub + Qp ) = v1 ,
ates the signature.
The proxy signer chooses a random number
then the receiver accepts the signature if the equality
holds.
w ∈ [ q − 1 ]
and computes :
The proposed proxy signature ( α ,σ ,mw ,u ,s ,H ( m )) con-
• r = [( w + skp ) mod q ].Ppub = ( u ,v )
• s = ( u + H ( m ).skp ) mod q
tains the warrant m w while the normal signature does not, so both are different in the form. Also in the
verification equation, public keys Qa and Qp , also and
• signer sends ( α ,σ ,mw ,u ,s ,H ( m )) to the verifier
warrant
mw are used. So anyone can distinguish the
The receiver computes :
• v1 = H ( m ).[ T − h( α ,mw ).Qa + Qp ]
proxy signature from a normal signature easly.
The verifier of a proxy signature can check easily that the verification equation
• v2 = [( s − u ) mod q )].Ppub
v1 = H ( m ).[ T − H ( α ,mw ).Qa + Qp ] = v2
,where
If v1 = v 2
, accept the signature .The receiver verifies
v2 = [( s − u ) mod q )].Ppub
, if
v1 = v 2
accept the signature
the identities of both the original signer as well as the
holds. In addition, this equation involves original sign-
proxy signer using the warrant.
er’s public key Qa
and warrant m w , so any one can be
The KGC calculates the secret keys for the sender and the proxy respectively as follows:
convinced of the original signer’s agreement on the
proxy signer.
da = ( H ( IDa ).mkPKG ) mod q
d p = ( H ( IDp ).mkPKG ) mod q
,and
.The KGC calculates the
In our scheme only the designated proxy signer can
create a valid proxy signature, since the proxy private
key
skp = ( d p + σ ) mod q
includes the private key d p of
public keys as follows; Qa = da .Ppub ; the sender's public
key, and Qp = d p .Ppub ; the proxy's public key.
the proxy signer and to compute d p from Q p is equiv- alent to solving the ECDLP.
This is because of the presence of the warrant mw
and
public keys
Qa and Qp
in the verification equation.
The proxy agent checks the equation
Also, the generation of a proxy signature involves both
: T = σ .Ppub + H ( α ,mw ).Qa
the original and proxy signers' private keys d a
and
= ( d − da .h( α ,mw )).Ppub + h( α ,mw ).Qa
= d .Ppub − da .H ( α ,mw ).Ppub + H ( α ,mw ).Qa = d .Ppub = T
The receiver computes:
v1 = H ( m ).[ T − H ( α , mw ).Qa + Q p ]
v1 = H ( m ).[ d .Ppub − H ( α ,mw ).da .Ppub + Qp ]
v1 = H ( m ).[ d .Ppub − H ( α ,mw ).da .Ppub + Qp ]
d p respectively. It is already proved that neither the
original signer nor the proxy signer can sign in place of any other party. So the original signer cannot deny his delegation and the proxy signer cannot deny having signed the message m on behalf of original signer to another party.
In the proposed scheme, it can be checked who is orig- inal signer and who is proxy signer from the warrant m w . Also, it clear from the verification equation
v1 = H ( m ).( σ .Ppub + Qp )
v1 = H ( m ).[ T − h( α ,mw ).Qa + Qp ] = v2
where
Also, The receiver computes: v2 = [( s − u ) mod q )].Ppub
v2 = [( s − u ) mod q )].Ppub
that the public keys
Qa and
Q p are asymmetrical in position. So anyone can distin-
IJSER © 2013 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 5, Issue 4, April-2014 1108
ISSN 2229-5518
guish the identity of the proxy signer from the proxy signature.
schemes when compared with them. Both schemes are without bilinear pairing.
The original signer generates the delegation
( α ,σ , m w )
[1] Z. Cheng, "Simple Tutorial on Elliptic Curve Cryptography",
where
T = d .G = ( α , b ) and
σ = ( d − d a .h( α , m w )) mod q
Chapter 2. ECC In Practice , December 1, 2004
using its private key and sends it to the proxy. So the delegation cannot be modified or forged. Also the war- rant mw contains the limit of delegated signing capabil-
TABLE 3
THE PROPOSED PROXY SIGNATURE SCHEME COMPARED W ITH THE
SCHEMES IN[14]
ity. So it is not possible to sign the messages that have not been authorized by original signer
The proposed proxy signature scheme is compared with the schemes in [14]. Table 3 shows the comparison in details.
From the comparison, it can be seen that the proposed proxy signature scheme requires less computational effort than the scheme with pairings [14] .
Phase | Bin Wang scheme from pairings [14] | The proposed scheme without pairings |
Proxy delegation | 2TEC-mult + 1TEC- add +1Th | 1TEC-mult + 1Th + 1Tmul |
Proxy key genera- tion | 3Tpairings + 1Th | 2TEC-mult + 1TEC- add +1Th |
Proxy Signature generation | 2TEC-mult + 3TEC- add +1Th | 1TEC-mult +1Th + 1Tmult |
Proxy Signature verification | 4Tpairings + 2TEC- add + 2Th | 3TEC-mult + 2TEC- add +2Th |
Total | 7Tpairings + 4TEC- mult +6TEC-add + 5Th | 7TEC-mult +3TEC- add +4Th +2Tmult |
This paper proposes two schemes; the first is a digital signature with its security analysis discussion, and the second is a proxy signature with its security analysis discussion. Both schemes are more efficient than other
[2] M. Mambo, K. Usuda, and E. Okamoto, "Proxy signatures: delegation of the power to sign messages," Transactions on Fundamentals of Electronic Communications and Computer Science, vol. E79-A, pp. 1338-1354, 1996.
[3] S. Kim, S. Park, and D. Won, "Proxy signatures," Proceedings of international conference on information and communications security (ICICS)'97, LNCS 1334, pp. 223-232, Springer-Verlag,
1997.
[4] B. Lee, H. Kim, and K. Kim, "Strong proxy signature and its applications," SCIS2001, vol. 2, no. 2, pp. 603-608, 2001.
[5] J. Lee, J. Cheon, and S. Kim, "An analysis of proxy signatures: Is a secure channel necessary," Cryptology-CT-RSA'03, LNCS 2612, pp. 68-79, Springer-Verlag, 2003.
[6] S. F. Tzeng, M. S. Hwang, and C. Y. Yang, "An improvement of nonrepudiable threshold proxy sig- nature scheme with known signers," Computers & Security, vol. 23, pp. 174-178, 2004.
[7] M. Tian and L. Huang,"Breaking A Proxy Signature Scheme From Lattices. International Journal of Network Security, Vol.14, No.6, PP.320-323, Nov. 2012
[8] Y. Kim and J. H. Chang, " Self Proxy Signature Scheme ", IJCSNS International Journal of Computer Science and Network Security, VOL.7 No.2, February 2007
[9] F. Zhang, R. Safavi-Naini and W. Susilo," An Efficient Signature Scheme from Bilinear Pairings and Its Applications", Springer- Verlag ,pp 277-290 PKC 2004, LNCS 2947
[10] S. Padhye, N. Tiwari," Improved Proxy Signature Scheme without Bilinear Pairings", In the Proceeding of 9th International Conference, QShine 2013, Greader Noida, India, January 11-12,
2013.
[11] A. Shamir, “Advance in Cryptology”, Proceedings of CRYPTO
84, (1984) August 19-22, California, USA.
[12] A. Kumar and H. Lee, " Performance Comparison of Identity Based Encryption and Identity Based Signature", International Journal of Security and Its Applications , Vol. 6, No. 3, July, 2012
[13] S. Sharmila Deva Selvi, S. Sree Vivek, C. Pandu Ranganm "Identity Based Deterministic Signature Scheme Without Forking- Lemma", IWSEC 2011: 79-95
[14] Bin Wang , " A new identity based proxy signature scheme ", IACR Cryptology ePrint Archive (2008)
[15] D. Johnson, A. Menezes, and S. Vanstone, " The elliptic curve digital signature algorithm (ECDSA) ",International Journal of Information Security 1 (1) (2001) 36–63.
[16] C. Gu and Y. Zhu, "An Efficient ID-based Proxy Signature
Scheme from Pairings " , Inscrypt 2007: 40-
[17] F.Hess, Efficient Identity –based signature schemes based on pairings , In Selected Areas in Cryptography- SAC 2002 , pp.310-
324, K.Nyberg and H.Heys (eds), Springer Verlag, 2003
[18] J.C.Cha and J.H.Cheon, An Identity based signature from Gap Diffie Hellman Groups, In proceeding PKC'03, LNCS,pp 18-30, Springer Verlag, 2003
IJSER © 2013 http://www.ijser.org