Abstract To solve the key escrow problem in identity%based cryptosystem, Al%Riyami et al. introduced the CertificateLess Public Key Cryptography (CL%PKC). As an important c ryptographic primitive, CertificateLess Designated Verifier Signature (CLDVS) scheme was studied widely. Following Al%Riy ami et al. work, many certificateless Designated Verifier Signature (DVS) schemes using bilinear pairings have been pro posed. But the relative computation cost of the pairing is approximately twenty times higher than that of the scalar multipl ication over elliptic curve group. In order to improve the performance we propose a certificateless DVS scheme without biline ar pairings. With the running time of the signature being saved greatly, our scheme is more practical than the previous rela ted schemes for practical application.

References

[1] Al)Riyami S. and Paterson G., Certificateless Public Key Cryptography, in Proceedings of the 9 th International Conference on the Theory and Application of Cryptology and Information Security , Taiwan, pp. 452)473, 2003.

[2] Cao X. and Kou W., A Pairing)Free Identity) Based Authenticated Key Agreement Scheme with Minimal Message Exchanges, Information Sciences , vol. 180, no. 15, pp. 2895)2903, 2010.

[3] Chen H., Song S., Zhang T., and Song G, An Efficient Certificateless Short Designated Verifier Signature Scheme, in Proceedings of the 4 th International Conference on Wireless Networking and Mobile Computing , Dalian, pp. 1)6, 2008.

[4] Chen L., Cheng Z., and Smart N., Identity) Based Key Agreement Protocols from Pairings, International Journal Information Security , vol. 6, no. 4, pp. 213)241, 2007.

[5] He D., Chen J., and Hu J., An ID)Based Proxy Signature Schemes without Bilinear Pairings, Annals of Telecommunications , vol. 66, no. 11) 12, pp. 657)662, 2011.

[6] He D., Chen J., and Hu J. A Pairing)Free Certificateless Authenticated Key Agreement Protocol, International Journal of Communication Systems , vol. 25, no. 2, pp. 221) 230, 2012.

[7] He D., Chen J., and Zhang R., An Efficient Identity)Based Blind Signature Scheme without Bilinear Pairings, Computers & Electrical Engineering , vol. 37, no. 4, pp. 444)450, 2011.

[8] Huang X., Susilo W., Yi M., and Zhang F., Certificateless Designated Verifier Signature Schemes, in Proceedings of Advanced Information Networking and Application , Vienna, pp. 15)19, 2006.

[9] Jakobsson M., Sako K., and Impagliazzo R., Designated Verifier Proofs and their Applications, in Proceedings of Advances in Cryptology: EUROCRYPT%International Conference on the Theory and Application of Cryptographic Techniques , Spain, pp. 143)154, 1996.

[10] Kang B., Boyd C., and Dawson E., A Novel Identity)Based Strong Designated Verifier Signature Scheme, The Journal of Systems and Software , vol. 82, no. 2, pp. 270)273, 2009.

[11] Kumar K., Shailaja G., and Saxena A., Identity Based Strong Designated Verifier Signature Scheme, Informatica , vol. 18, no. 2, pp. 239) 252, 2007.

[12] Lipmaa H., Wang G., and Bao F., Designated Verifier Signature Schemes: Attacks, New Security Notions and a New Construction, in Proceedings of the 32 nd International Colloquium Automata, Languages and Programming , Berlin, pp. 459)471, 2005.

[13] Ming Y., Shen X., and Wang Y., Certificateless Universal Designated Verifier Signature Schemes, Journal of China Universitles Posts and Telecommunications , vol. 14, no. 3, pp. 85) 91, 2007.

[14] Saeednia S., Kremer S., and Markowitch O., An Efficient Strong Designated Verifier Signature Scheme, in Proceedings of Information Security and Cryptology , Berlin, pp. 40)54, 2003.

[15] Shamir A., Identity)Based Cryptosystems and Signature Schemes, in Proceedings of CRYPTO on Advances in Cryptology , USA, pp. 47)53, 1985.

[16] Susilo W., Zhang F., and Mu Y., Identity)Based Strong Designated Verifier Signature Schemes, in Proceedings of Information Security and Privacy , Berlin, pp. 313)324, 2004.

[17] Tso R., Okamoto T., and Okamoto E., Practical Strong Designated Verifier Signature Schemes Based on Double Discrete Logarithms, in Proceedings of the 1 st SKLOIS Conference on Information Security and Cryptology , Berlin, pp. 113)127, 2005.

[18] Wu S. and Zhu Y., Improved Two)Factor Authenticated Key Exchange Protocol, The International Arab Journal of Information Technolog y, vol. 8, no. 4, pp. 430)439, 2011.

[19] Xiao Z., Yang B., and Li S., Certificateless Strong Designated Verifier Signature Scheme, in Proceedings of 2 nd International Conference on e%Business and Information System Security , Wuhan, pp. 1)5, 2010.

[20] Yang B., Hu Z., and Xiao Z., Efficient Certificateless Strong Designated Verifier Signature Scheme, in Proceedings of 394 The International Arab Journal of Informa tion Technology, Vol. 10, No. 4, July 2013 International Conference on Computational Intelligence and Security, Beijing, pp.432)436, 2009.

[21] Zhang J. and Mao J., A Novel ID)Based Designated Verifier Signature Scheme, Information Science , vol. 178, no. 3, pp. 766)773, 2008. Debiao He received his PhD degree in applied mathematics from School of Mathematics and Statistics, Wuhan University in 2009. Currently, he is a lecturer in Wuhan University. His main research interests include cryptography and information security, in particular, cryptographic protocols. Jianhua Chen received his PhD degree in applied mathematics from Wuhan University, Wuhan, China, in 1994. Currently, he is a professor in Wuhan University. His current research interests include number theory, information security and network security. Appendixes Proof for Theorem 1 : Suppose F is challenged with a ECCDH instance ( P, Q 1=aP, Q2=bP) and is tasked to compute Q 3=ab P. To do so, F picks two identity ID I and IDJ at random as the challenged ID in this game, and gives { F p, E/Fp, G, P, Ppub=Q1, H1, H 2} to A1 as the public parameters. Then F answers A 1 s queries as follows. H1%Queries: F maintains a hash list 1HLof tuple ( , , , , )i i i ii ID ID ID IDID R P d has explained below. The list is initially empty. When A1 makes a hash oracle query on ID i, if the query IDj has already appeared on 1HL, then the previously defined value is returned. Otherwise, F acts as described in the partial private key extraction queries. H2%Queries: F maintains a hash list 2HLof tuple ( m j, cj, hj). When A1 makes H2 queries for identity ID i on the message mj, F chooses a random value *j nh Z , sets hj=H2(mj, cj) and adds ( mj, cj, hj) to 2HL, and sends hj to A1. Partial Private Key Extraction Queries: A 1 is allowed to query the extraction oracle for an ident ity ID i. F query H1 oracle, IDi is on 1HL, then F response with ( , , , , ).i i i ii ID ID ID IDID R P d hOtherwise, if simulates the oracle as follows. It chooses *,i i na b Z at random, sets ,iID i pub iR a P b P= + iID id =b , 1( , ) mod ,i iID i ID ih H ID R a n= response with ( , , , , ),i i i ii ID ID ID IDID R P d hand inserts ( , , , , )i i i ii ID ID ID IDID R P d hinto 1.HLNote that ( , , )i i iID ID IDR d hgenerated in this way satisfies the equation d ID P=RID+hID Ppub in the partial private key extraction algorithm. It is a valid secret key. Public Key Extraction Queries: F maintains a list L pk of tuple ( , , )i ii ID IDID s pkwhich is initially empty. When A1 queries on input ID i, F checks whether L pk contains a tuple for this input. If it does, the previously defined value is returned. Otherwise , if ID i IDJ, F picks a random value *,ID ns Z computes .i iID IDP s P= If IDi=IDJ, F sets iIDP b P= and iIDs= . F queries Partial Private Key Extraction Queries with ID i and iIDPand get response .iIDR At last F returns { , }i i iID ID IDpk P R=and adds ( , , )i ii ID IDID s pkto the Lpk. Private Key Extraction Queries: For query on input ID i, If IDi=IDI or IDi=IDJ, F stops and outputs failure . Otherwise, F performs as follows: If the 1HL and the Lpk contain the corresponding tuple ( , , , )i i ii ID ID IDID R s hand the tuple ( , , )i ii ID IDID s pk respectively, F sets { , }i i iID ID IDsk d s= and sends it to A1. Otherwise, F makes a partial private key extraction query and a public key extraction query on ID i, then simulates as the above process and sends { , }i i iID ID IDsk d s=to A 1. Public Key Replacement: When A1 queries on input ,( ),ii IDpk IDF checks whether the tuple ( , , )i ii ID IDID s pkis contained in the Lpk. If it does, F sets i iID IDpk pk= and adds the tuple ( , , )ii IDID pk to the Lpk. Signing Queries: When a message m, the signer A s identity ID A, the designated verifier s B s identity ID B is coming, F acts as follows: F first checks that whether tuple ( , , , )i i ii ID ID IDID R d hand ( , , )i ii ID IDID s pkare in 1HL and Lpk separately. If yes, it just retrieves ( , , , )A A B BID ID ID IDd s P Rfrom the tables and uses these values to sign for the messag e according to the signing algorithm described in the scheme. It outputs the signature ( r, s, t) for the message m and stores the value H 2(m, c) in 2HL for consistency. If ID A or IDB has not been queried to An Efficient Certificateless Designated Verifier Signature Scheme 395 the partial private extraction oracle and the priva te extraction oracle, F executes the simulation of the partial private extraction oracle and the private extraction oracle, then uses the corresponding secr et key to sign the message. Finally, A1 stops and outputs a signature S={ r, s, t} on the message m with the signer A s identity ID A, and A s private key AIDsk, the designated verifier s B s identity ID B public key BIDpk, which satisfies the following equation ( , , , , , )1B AA ID IDV erify params m ID sk pk S=. If IDA IDJ or ID B IDJ, F outputs failure and aborts. Otherwise, F recovers the tuple ( , , , )I I II ID ID IDID R d hand ( , , , )J J JJ ID ID IDID R d h from 1,HLthe tuple ( , , )I II ID IDID s pkand ( , , )J JJ ID IDID s pkfrom Lpk and the tuple ( m, c, h) from 2.HL Then, we have: ( )( ( ))J J I I IID ID ID ID ID pubc t d s s P r P R h P= + + + + (7) Since P IDI=sIDI P, RIDJ=b P and Ppub=a P, we could have: 2 2 2 3 ( )( ( )) ( ) J J I I I J I I I J I I IID ID ID ID ID pub ID ID ID ID ID ID ID ID pubc t d s s P r P R h P t s Q t s s P t r s Q t r d Q t r h Q t s r P R h P= + + + + = + + + + + + + Then we have 3 2 2 2 ( ) I J I I J I I IID ID ID ID ID ID ID ID pubt r h Q c t s Q t s s P t r s Q t r d Q t s r P R h P = + + (9) and 1 3 2 2 2( ) ( ( ))I J I I J I I IID ID ID ID ID ID ID ID pubQ t r h c t s Q t s s P t r s Q t r d Q t s r P R h P = + + (10) Obviously, the probability of ID A=IDI or IDB=IDJ is 1 ( 1 )s sq q . Thus, we can obtain Q3=ab P with the probability 2 ( 1 )s sq q . In other words, given ( P, Q1=aP, Q 2=bP ), F can solve the ECCDH problem with non) negligible probability 2,( 1)s sq q which is in contradiction with the ECCDH assumption. Proof for Theorem 2: Suppose that there is a type 2 Adversar A2 who can breaks our scheme with probability , when making qe extraction queries, qs signing queries and q h hashing queries respectively. Then, we will show how to use the ability of A2 to construct an algorithm F solving the ECCDH. Suppose F is challenged with a ECCDH instance ( P, Q 1=aP, Q2=bP ) and is tasked to compute Q3=ab P. To do so, F chooses a random *nx Z , computes Q=xP , picks two identity ID I and IDJ at random as the challenged ID in this game, and gives public parameters { F p, E/Fp, G, P, Ppub=Q1, H1, H2} and the master key s to A2 . Then F answers A2 s queries as follows. H1%Queries: F maintains a hash list 1HLof tuple ( , , , , )i i i ii ID ID ID IDID R P d hindexed by IDi. The list is initially empty. When A2 makes a hash oracle query on ID i, if the query IDi has already appeared on 1,HLthen the previously defined value is returned. Otherwise, F makes the partial private key extraction query with ID i, and sends iIDhto A2. H2%Queries: F maintains a hash list 2HLof tuple ( m j, cj, hj). When A2 makes H2 queries for identity ID i on the message mj, F chooses a random value *j nh Z , sets hj=H2(mj, cj) and adds ( mj, cj, hj) to 2,HLand sends hj to A2. Partial Private Key Extraction Queries: A 2 is allowed to query the extraction oracle for an ident ity ID i. F query H1 oracle, IDi is on 1HL, then F response with ( , , , , ).i i i ii ID ID ID IDID R P d h Otherwise, if simulates the oracle as follows. It chooses iIDrat random, sets ,i iID IDR r P= 1( , , )i i iID i ID IDh H ID R P= and ,i i iID ID IDd r x h= + response with ( , , , , ),i i i ii ID ID ID IDID R P d hand inserts ( , , , , )i i i ii ID ID ID IDID R P d h into 1HL. Private Key Extraction Queries: F maintains a list L sk of tuple ( , , )i ii ID IDID d swhich is initially empty. For query on input ID i, F performs as follows: 1. If the query ID i has already appeared on Lsk, then the previously defined value is returned. 2. Else if ID i=IDI, F sets iIDs= , 1iIDP Q=. 3. Else if ID i=IDJ, F sets iIDs= , 2iIDP Q=. 4. Else if ID i IDI and IDI IDJ, F generates a random number *,iID ns Z compute .i iID IDP s P= Then F looks up 1HLto get the tuple ( , , , ),i i ii ID ID IDID R d hand add the tuple (8) 396 The International Arab Journal of Informa tion Technology, Vol. 10, No. 4, July 2013 ( , , , )i i ii ID ID IDID d s Pto Lsk, and sends { , }i i iID ID IDsk d s=to A2. Public Key Extraction Queries: F maintains a list L pk of tuple ( , )ii IDID pkwhich is initially empty. When A2 queries on input ID i, F checks whether L pk contains a tuple for this input. If it does, the previously defined value is returned. Otherwise, F looks up the tables 1HLand Lsk and gets the tuple ( , , , )i i ii ID ID IDID R d hand ( , , , )i i ii ID ID IDID d s P separately. At last F returns { , }i i iID ID IDpk P R=and adds ( , )ii IDID pkto the Lpk. Signing Queries: When a message m, the signer A s identity ID A, the designated verifier s B s identity ID B is coming, F acts as follows: If IDA=IDI or ID A= IDJ, F terminates the simulation. Otherwise, F first checks that whether tuple ( , , , )i i ii ID ID IDID R d hand ( , )ii IDID pkare in 1HLand Lpk separately. If yes, it just retrieves ( , , , )A A B BID ID ID IDd s P Rfrom the tables and uses these values to sign for the message according to t he signing algorithm described in the scheme. It outputs the signature ( r, s, t) for the message m and stores the value H 2(m, c) in 2HLfor consistency. If ID A or IDB has not been queried to the partial private extraction oracle and the private extraction oracle , F executes the simulation of the partial private extraction oracle and the private extraction oracle , then uses the corresponding secret key to sign the message. Finally, A2 stops and outputs a signature S={r, s, t} on the message m with the signer A s identity ID A, and A s private key AIDsk, the designated verifier s B s identity ID B public key BIDpk, which satisfies the following equation ( , , , , , )1B AA ID IDV erify params m ID sk pk S=. If IDA IDI or ID B IDJ, F outputs failure and aborts. Otherwise, F recovers the tuple ( , , , )I I II ID ID IDID R d hand ( , , , )J J JJ ID ID IDID R d h from 1,HLthe tuple ( , , )I II ID IDID s pk and ( , , )J JJ ID IDID s pk from Lpk and the tuple ( m, c, h) from 2.HLThen, we have: ( )( ( ))J J I I IID ID ID ID ID pubc t d s s P r P R h P= + + + + (11) Since 1,IIDP Q a P= = 2JIDR Q b P= = and Ppub=x P , we could have: 3 2 2 ( )( ( )) ( )J J I I I J J I I I J I I ID ID ID ID ID pub ID ID ID ID ID pub ID ID ID c t d s s P r P R h P t s R t d r P R h P t s P t r Q t d r Q t r h x Q = + + + + = + + + + + + + (12) Then we have: 3 2 2 ( ) J J I I I J I IID ID ID ID ID pub ID ID IDt r Q c t s R t d r P R h P t s P t d r Q t r h x Q = + + (13) and 1 3 2 2 ( ) ( ( ) ) J J I I I J I IID ID ID ID ID pub ID ID IDQ t r c t s R t d r P R h P t s P t d r Q t r h x Q = + + (14) Obviously, the probability of ID A=IDI or IDB=IDJ is 1.( 1)s sq q Thus, we can obtain Q3=ab P with the probability 2.( 1)s sq q In other words, given ( P, Q1=aP, Q 2=bP ), F can solve the ECCDH problem with non) negligible probability 2,( 1)s sq q which is in contradiction with the ECCDH assumption.