TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol. 12, No. 10, Octobe r 20 14, pp. 7343  ~ 735 2   DOI: 10.115 9 1 /telkomni ka. v 12i8.520 2    ļ®       7343     Re cei v ed  De cem ber 6, 20 13; Re vised Ju ly 18, 20 14; Acce pted Au gust 2, 201 4   Provably Secur e  and Efficient ID-based Strong  Designated Verifier Signature Scheme with Messag e  Recovery       Min Li   Sichu an Norm al Univ ersit y  of  Chin a, Che n g du, Sichu a n   Univers i t y   of Electronic Sci enc e and T e chno l o g y  of Chi n a   email: lm_t urni p@1 26.com       A b st r a ct   Many ID-bas e d  strong des ig nated ver i fier  sign at ure sche m es h a ve b e e n  prop osed i n  recent   years. How e ve r, most of the m  d i d  not  giv e   the rig o rous s e curity pro o fs a nd d i d n o t sati sfy the strong n e ss   prop erty that anyo ne exc ept  the des ig nate d  verifier ca nn ot check the  valid ity of a desig nate d  verifie r   sign ature, In  a dditi on, c onsi d erin g so me s p ecial  a p p licati o ns, these  sch emes  hav e l a r ger  data  si z e   of  communic a tio n .  T o  overc o me thos e  prob l e ms,  exp l oiti n g   mess age  r e covery  tech n i qu es w h ic h  are  regar ded  as  a  useful  metho d   to shorte n ID- base d  si gnat ur es'  si z e , w e  p u t forw ard a n   efficient ID- bas ed   strong des ig na ted verifier si gn ature sche m es  w i th messag e  recovery a nd g i ve its rigor ous  security pro o f i n   the ran d o m   or acle  mod e l b a s ed o n  th e h a rd ness ass u mp ti ons of th e co mputatio na l Bil i n ear D i ffie-He ll ma n   prob le m i n  thi s  pap er. T o  th e best  of our   know led ge,  it  i s  the first ID-b ased stro ng  d e sig nate d  verif i er   sign ature sch e m es w i th mess age rec o very a nd rig o rous s e curity proofs. D ue to its mer i ts, it can be use d  in   some s peci a l  e n viro nments w here  the  ba nd w i dth is  one   of  the  ma in c onc erns, suc h  as   PDAs, cell  p h o nes,   RFID etc.      Ke y w ords :   ide n tity-base d  publ ic key cr yptogra phy, d e sig nate d  veri fier sign ature,  mess age r e c o very,  bili ne ar pair i n g s , rando m orac le mod e l          Copy right  Ā©  2014 In stitu t e o f  Ad van ced  En g i n eerin g and  Scien ce. All  rig h t s reser ve d .       1. Introduc tion   Digital  sig nat ure  a s  o ne i m porta nt p r i m itiv e  in cry p togra phy, which   can pro v ide  data   integrity, authenticatio n an d non-rep udi ation, has m any pra c tical  appl i c ation s  in the real wo rld,  su ch a s  el ectro n ic  co mmerce, ele c troni c g o ve rnme nt etc.  Ho wever, i n  som e  sp ecial   environ ment s, signatu r e s   with spe c ial  prop ertie s   a r e always  de sirable. F o r  example, in  so me  scena rio s  su ch a s  E-votin g , call fo r ten ders an d  software licen sin g , the publi c   verification  of an   ordin a ry sign ature  i s   n o t desi r ed, sin c e  the sign er  may not wan t  to the re cip i ent of a di gi tal  signature to transfer  the conviction to a third party at will.  To  a ddress  t h is problem  above, Cha u m   an d Van   Antwerpen  in trodu ced  un d eniabl e   sign ature s  [2 , 3] whi c h  allowe d a  sig n e r to  com p le tely control h i s  signatu r e s .  In und enia b l e   sign ature s , the verifie r  (B ob)  can  not  che c k t he va lidity of the signature give n by the si g ner  (Alice )  by him s elf. Instea d, Alice pa rtici p ates in  th e scheme to  prov e the validity (or i n validity)  of  the si gnatu r e  to Bob  by  m ean s of  an  in teractive   protocol.  Neve rth e less, Ali c e  can o n ly de cid e   whe n  to prove, but not who to verify. Hence,  the co nviction ca n be tran sferre d to anyone else.   Motivated by  the a bove  p r oble m , Jako bsson  et  al.  [4] introdu ce d the  co ncep t of de sign ated  verifier si gnat ure (DVS)  scheme in Eu rocrypt 1 996.  A DVS sch eme ma ke s i t  possible for a  sign er Alice to convin ce a  desig nated  verifier  Bob t hat Alice ha s signe d a me ssage in  su ch a   way that Bob can not transfe r  the conviction to a third party  Cindy. This is called n on- transfe ra bility, and is usu a l l y achieved b y  enabling  Bob the cap a b ility of efficiently simulatin g  a   sign ature  whi c h is in distin g u ish able fro m  Alice's.   In ord e r to e nhan ce  the  signer's priva cy, Ja kob s son  et al. al so  introdu ce d a   stron g e r   versio n of DVS in the same wo rk [4]. It is us ually calle d stro ng  desig nated  verifier si gnat ure   (SDVS) sch e m e, in  whi c h  no  third  pa rt y can  eve n   check th e vali dity of a  de si gnated  verifi er   sign ature, si n c e the verification of the si gnatur e re qui res the  desi g nated verifie r ' s  private  key.  Evaluation Warning : The document was created with Spire.PDF for Python.
                 ļ®               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 10, Octobe r 2014:  734 3  ā€“ 7352   7344 Since th e n o tion of S D VS  prop osed  by  Ja kob s son  et  al. in [4], m any SDVS  scheme s   have b een  p u t forward in  the literatu r e.  In 20 03,  Sae ednia  et al. [ 5 ] firstly form alize d  the  not ion  of SDVS an d pro p o s ed  an efficient  schem e in th e sam e  pap er. In 2004,  Susilo et al.  [6 ]  prop osed the  first stron g  desi gnate d  verifier  sign ature  sch eme  in identity-ba sed p ubli c  key  crypto system  that was first  introdu ce d b y  Shamir  [1] in 1984 to  sol v e the probl e m s of certificate   manag eme n t in public  key  infrastructu re (PKI). D ue  to its advanta ge in co ntra st  to PKI, several  new I D -b ase d  SDVS (IBSDVS) have  b een p r op osed  in the ne w  setting re centl y . In 2008, Z hang  et al. [8] p r o posed  a n o vel IBSDVS schem e  by co mbining ID- b as ed public   key cr yptos y s t em  with the de sig nated verifie r  sign ature. In their  work, the y  claimed tha t  their schem e wa s a st ron g   desi gnate d  v e rifier si gnatu r e, that i s  to  say,  no thi r d  p a rty can  ch eck the  validity  of a  de signat ed  verifier  sign ature  gene rate d by the  sign er. In 20 09,  h o weve r, Kan g  et al. [9] found that Z h a ng et   al.'s sche me can n o t satisf y the strongn ess pro per ty as they claim ed in [8]. In  the sam e  pap e r   [9], they presented a ne w IBSDVS sch eme and I D - based de sig n a ted verifier  proxy sign atu r e   s c heme  (IBDVPS) based  on the new I BSDVS s c heme.  In the meanwhile, they als o  put forward  a novel  IBSDVS scheme [10] with security proofs  i n  t he random  oracle  model based on Bilinear  Diffie-Hellma n  a s sumptio n . Unfo rtunat ely, Lee  et  al. [11] sho w ed  that Ka ng et  al.'s  n e w  scheme s  in [ 9 ] are u n iversally forgea ble  in 2010,   that is,  anyon e  ca n  gen erate a sign ature on an   arbitrarily ch o s en me ssag e  without the secret key  of e i ther the sig n e r or the d e si gnated verifie r .  To overcom e  these flaws,  they also pres ented a new IBSDVS and IBDVPS schem e and give   the formal  se curity p r oof s  in the rand o m  ora c le  mo del [14, 1 5 ] in the  same   pape r. In 20 08,  Hua ng et al. [ 7 ] also  propo sed  an effici e n t IBSD VS scheme  whi c h i s  secure ba sed on  a  stron ger  assumption, i . e. Gap Bilinear Diffie-Hel l man, the si ze of the  signature in  their scheme i s  v e ry  sho r t co mpa r ed to all the  existing sch e m es. Howeve r, the sig natu r e in thei r scheme i s  short o f   rand omi c ity beca u se the signatures o n  the same  me ssage a r e al ways ide n tica l in every time  sign ature g e n e ration p r o c e dure.    As  far as   we  k n ow, all these exis ting  sc heme s  exce pt the schem es  in [7, 11, 16]  can  not  sup port  the  strongn ess property  of the  SDVS, and   the signi ng m e ssag es  in al l  these sche mes  alway s  nee d to be tran smi tted together  with t he sig n a ture s. Thu s , these sch e m e s have a la rge  total commu nicatio n  co st, for whi c h they maybe  can n o t efficiently used i n  som e  sp e c ial   environ ment s where low- communi catio n  and lo w-co mputation co st are u s ually  requi red.   To solve th ose  above  probl em s, combinin g th e messa g e  recovery t e ch niqu es  pre s ente d  in  [12], we firstl y put forwa r d  an e ffic i ent IBSDVS s c heme with mess age rec o very   (IBSDVSMR), and prove  its se cu rity in the ran d o m  ora c le mo del ba sed  o n  Bilinear  Di ffie- Hellma n  a s su mption. In th e prosed  sch e me, t he m e ssage i s  e m b edde d in a  si gnature an d  can   be re cove re d from the  received  sig nature.  Hen c e, it results in more b and width sa ving.  Obviou sly, it  has the a d va ntage of smal l data size of comm uni cati on.   Due to its m e rits, the pro posed sch e m e  in th is pap er is not onl y quite efficient with   respe c t to  co mputation  co st, but al so  very small  with re sp ect to  the total l engt h of the  si gni ng   messag e an d the ap pen ded  signatu r e, i.e. co mm unication cost.  For  these advantag es, the  prop osed sch e me with me ssage recove ry is very  use f ul for the environme n ts where b and wid t h  is on e of the   main  con c e r n s . Fo r in stan ce, on  wi rele ss devices (e .g. PDAs, cel l  phon es,  RFI D   chip s and  se nso r s) wh ere battery  life  i s  the  mai n  limit ation, commu nicatin g  eve n  one  bit  of da ta   usu a lly use s   signifi cantly more  power t han exe c utin g one 3 2 -bit instru ction [1 3 ]. Redu cing t he  numbe r of co mmuni cation  bits save s po wer a nd is  im portant for in crea sing the b a ttery life.  The rest  of this pa pe r is org ani zed  as follo ws. In se ction  2,  we first giv e  so me   prelimi nari e s,  inclu d ing bili near  map s  a nd some  rela ted hard p r ob lems, the M o del of ID-ba s ed  stron g   d e si gn ated  verifie r  signature sche me wi th me ssag e recovery and  so  on,  and th en  we   put  forwa r d  an  ef ficient  con c re te schem e a nd give it s  se curity p r o o f i n  the  ran dom  ora c le  mod e l  in   Section 3 an d  sectio n 4, re spe c tively; In  Secti on 5, we  compa r e o u r sch eme s  wit h  some exi s ting  scheme s  p r e s ente d  in [8, 10, 11]; Finally, we end this paper  with a brief co ncl u si on.      2. Rese arch  Metho d   In this sectio n, we b r iefly review  so me  fundame n tal  backg rou n d s   requi re d thro ugh thi s   pape r, in cludi ng bilin ea r m aps,  hardne ss a s sumpti o n s , the  notion   of IBSDVSMR a nd it s  se curity  definitions etc.               Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046   ļ®   Provabl y Secure an d Efficient ID-ba s e d  Strong Desi g nated Verifie r  Signature ā€¦  (Min Li)  7345 2.1. Some Nota tions   For co nvenie n ce, we   list   some notation s  wi th thei r  meanin g s through out thi s   pape r i n   Table 1.       Table 1. Nota tions an d thei r Meani ng s  Notation Meanin g     || ab   a concatenation of t w o strings a a nd b  ļƒ…   X-OR comp utatio n in the binar y s y stem  2 [] x   the binar y notatio n of  x Z ļƒŽ   10 [] y   the decimal notation of  * {0 , 1 } y ļƒŽ   1 || l ļ”   the first  1 l bits of ļ” fro m  the right side  2 || l ļ”   the first  2 l bits of  ļ” fro m  the left side      2.2. Bilinear Pairings  Let  1 (, ) G ļ€« be a cyclic ad ditive grou p of prime o r de r  q  and  2 (, ) G ī€€ be a cycli c   multiplicative  group  of th e same  o r de r q ,  12 || ql l ļ€½ ļ€« . We assu me that the  discrete lo ga rithm   probl em s in b o th  1 (, ) G ļ€«  and 2 (, ) G ī€€  are intracta ble. Le t  11 2 : eG G G ļ‚“ļ‚® be a bilinear map with the  following properties :  (1) Bilinear:  (, ) ( , ) , ab ea Pb Q e PQ ļ€½ for all  1 , PQ G ļƒŽ , and  * , q ab Z ļƒŽ .  (2)  Non - de ge nerate: Th ere  exists  1 PG ļƒŽ su ch t hat   (, ) 1 eP P ļ‚¹ .  (3)  Comp utab le: There exi s ts an efficient  algorithm to  comp uter  (, ) eP Q for any  1 , PQ G ļƒŽ .  A bilinea r ma p satisfying t he p r op ertie s  above i s   na med a n  a d mi ssi ble bili nea r ma p. It  can  be o b tai ned fro m  the  modified  Weil and T a te  pairin g s. F o llowe d by are the ha rdn e ss   assumptio n s  use d  in the secu rity proof s:  Defini tion 1.  Bilinea r  Diffie-Hell man   Problem:  Th e BDH  pro b l em i s  to  compute r   (, ) abc eP P whe n  given  (, , , ) Pa P b P c P for so me un kn own  * ,, q abc Z ļƒŽ .  Defini tion 2.  Bilinea r  Diffie-Hellma n  a s sumptio n : Su ppo se th at G  is  a B D H pa ramete r  gene rato r,  Adv G (B ) is the  advantage t hat an algo ri thm  B has in solving the  BDH proble m .  Adv G (B) i s  de fined to be the prob abilit y that the algorit hm B outputs  (, ) abc eP P  when the in puts to   algorith m  are  12 ,, , , , GG P a P b P c P , where  12 (, , ) GG e  is the output of G  for sufficie n tly large se cu rit y   para m eter  k ,  P  is a rando m gene rator  of  1 G , and  ,, ab c  are rando mly ch ose n  from  * q Z . The  BDH a s sump tion is that  Adv G  (B) is n egli g ible for all ef ficient algo rithms B.    2.3. Definition of IBSDVS MR  An IBSDVS schem e with  messag e recovery is  a tu p l e of five polynomial time  a l gorithm s  as  follows :   Setup:  This  algorith m  takes a security param eter  k  as input an d returns the  system   para m eters  Pa r a ms  an d a se cret ma ste r  key  m a ster-key .   Key  Extrac tion:  T h is  alg o rit h m t a ke s  sy st em  pa ra met e r s   Params ,  m a ster-key  and   a   use r ' s  identity  i I D  as input, an d then retu rn s the private  key  i Sk  with res p ec t to the identity i I D .   Signature  G e nera tion:   This  algo rit h m t a ke s t h e  sy st em  pa r a met e r s   Params , a   messag e  m , a  signe r' s i dentity A I D , his  corre s p ondin g  private  ke y A Sk and the  de sign ated  verifier' s  publi c  key B I D as inp u ts, and then it outputs a vali d sign ature  ļ³ on messag e  m .  Signature Verification:  Th is alg o rit h m  t a ke s t h e  sy st em pa ram e t e rs  Params , si gnature  ļ³ , the sign er' s   identity A I D , the desig nated ve rifier's i dentity B I D  and p r ivate  key B Sk as in puts. I t   outputs  1 if the si gnatu r e  is valid, the  signi ng me ssage can be recove red su cce ssfully  in  t h is  ca se. Othe rwi s e outp u ts 0.   Evaluation Warning : The document was created with Spire.PDF for Python.
                 ļ®               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 10, Octobe r 2014:  734 3  ā€“ 7352   7346 Transc ript simulation:   The de sig n a t ed verifier  run s  this  al gorithm to  prod uce  identically distributed tra n script s whi c h a r e indi stingui shable fro m  the si gn ature g enerated by the   sign er.     2.4. Securit y  propertie s o f  IBSDVSM R  As define d  in  [10, 11], the IBSDVS sche me  with me ssag e re cove ry should  sati sfy some   main se cu rity prope rtie s, which a r e de scribed a s  follo ws:   a)  Corre ctn ess :  A prope rly prod uced IBSDVSMR mu st  be accepted  by the signature   verification al gorithm.   b)  Non-Transferabilit y :  The non-transferability means  that any designated veri fier   can n o t tran sf er the  convict i on to any third party,  that is, the de sign ated ve rifier  can not prove  to   a third pa rty that the sig nat ure  wa s pro d u ce d by  the signer  or by hi mself. This i s  accompli she d   by a tran scri pt sim u lation  algo rithm th rough  wh ich t he d e si gnate d  verifie r   can  produ ce  an   in-  disting u ishabl e sign ature from the  one g enerated by the real  sign er.  c)   Strongn ess :  Given a  sign ature, the ve rificati on p r o c edure requi re s the  se cret key  of the desig n a ted verifier, that is, any third pa rty can n o t che ck the  validity of the  sign ature.   d)  Source hidi ng:  Give n a  sign ature  on  messag e  m , it is  infeas ible to tell apart the  sign ature i s   prod uced by  the original  sign er  o r  the  desig nated  verifier on e a rth even if one  kno w s both the se cret key s .  e)  Unforgeabilit y :  It is com putationally i n feasi b le to   con s tru c t  a  valid IBSDV S MR   without the knowl edge of  the priv ate key of either the sig ner o r   the desi gnat ed verifier. T h e   formal definiti on of existential unforgeabilit y of IBSDVSMR is modeled by the following game   betwe en an a d versary A and a ch allen g e r C.   Game:  Th e game is exe c uted b e twe en a chall e n ger C a nd a n  adaptively cho s e n - messag e and  cho s en -ide ntity adversa ry A.    Setup:  Th e  challen ger C runs the Setu p alg o ri thm  to ge nerate th e sy stem p a rameters  Param s  and  the  sy stem maste r  key  ma s t e r -k ey .  Then  he  sen d s  Pa r a ms   to  adve r sa ry A  whil e   kee p s  ma s t er- k ey   se cret .   Queries :  A  a daptively issu es th e foll owi ng q u e r ies in  a  polynomi a l  bou nde d n u m ber of  times .   1)  Ke y  extra cti on qu eries:   Whe n   re ceiving p r ivate  ke y que ry on  id entity i I D , C runs   the Key Extraction alg o rith m and retu rn s the private  key i Sk .  2)  Sign queries :  On   receiving  a sign ature query on  m e ssag e  m  for a   sign er  i I D  an d a   desi gnate d  verifier j I D , C run s  the Signatu r e Gen e ratio n   algorith m  an d  returns  a vali d sig nature   ļ³ on messa g e  m .  3)  Verif y  queries:  On  re ceivi ng a verify qu ery on si gnat ure ļ³ for the si g ner i I D and the   desi gnate d  verifier j I D , C run s  the Signatu r e Verification  algorith m  an d  outputs 1 if t he si gnatu r e  is valid. In th is case, C re co vers the  m e ssag e from  the sig nature  and returns it. Otherwi se ,  outputs 0.   4)  Forgery :  Eventually, A o u tputs  a tu pl e  ** * (, , ) mh ļ³  with th e  sign er  * i I D  and  the  desi gnate d  verifier * j ID . We sa y that A wins the game if t he follow condi tions are all satisfied:   (1)   * ļ³  is a vali d si gnature on   messag es  * m  w i th  th e  s i gn er * i I D  and the  de si gnated  ver i fier * j ID .  (2) Duri ng  th e  simulation,  * i I D  a nd  * j ID have n e v er b een  su bmitted to t he  Key   extr action q u eries .  (3)   * m has  never  be en que rie d  d u ring th e  Sign queries  wi th the sign er  * i I D  and the  desi gnate d  verifier * j ID .  Definition  3. An IBSDVSMR i s  existe nt ially unforg eable  agai nst adaptively cho s e n - message and chosen-identity a ttacks  if the success probabilit y  of any polynomial bounded   adversa ry A in the above g a me is ne gligi b le.        Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046   ļ®   Provabl y Secure an d Efficient ID-ba s e d  Strong Desi g nated Verifie r  Signature ā€¦  (Min Li)  7347 3. Rese arch  Metho d   3.1.  The Efficient IBS D VSMR Schem e s   In this  part, we present the firs t effic i ent IBSDVS  scheme s  wit h  messag e recove ry,  whi c h is not  only much  efficient but also  can  sup port the stro ngne ss pro p e rty. In this  new  sign ature  sch eme,  it can  deal with me ssage s  of  so me fixed l e n g th (i e.,  1 {0 , 1 } l m ļƒŽ  for  s o me  fixed integer 1 l ), each al gorith m  of which  i s  spe c ified a s  follows:   Setup:  G i ve n a   s e c u r i ty par a m e t er   k , th e KGC ge ne rates  a  cycli c   additive g r ou p  1 (, ) G ļ€«   of prim e o r d e r q , a multipli cative group  2 (, ) G ī€€  of the  sam e  pri m e  ord e r , and  an  ad missi ble  bilinea r map   11 2 : eG G G ļ‚“ļ‚® . The KG C al so cho o se s fou r  cryptograp hic  hash fun c tio n s: * 11 :{ 0 , 1 } H G ļ‚® , 12 * 22 :{ 0 , 1 } { 0 , 1 } ll HG ļ€« ļ‚“ļ‚® , 12 1 :{ 0 , 1 } { 0 , 1 } ll F ļ‚® , 21 2 :{ 0 , 1 } { 0 , 1 } ll F ļ‚®  a rando m * q s Z ļƒŽ  and a  gene rato r   P  of  1 G , and co mp utes  Pu b Ps P ļ€½ , w h er e  / Pub s P   is the  priv ate/publi c  ke y pair of  KGC, and the n  publi s he s the syste m  pa ramete rs  Params :     12 1 2 1 2 {, , , , , , , , , } Pub GG e q P P H H FF     Ke y  Extracti on:  Given a n  identity i ID , KG C co mpute s   the co rre sp o nding p r ivate  key  1 () ii Sk s H ID ļ€½   i s Q ļ€½ , where  1 () ii Qs H I D ļ€½ , and then  send s  it to the use r   with ide n tity  i ID  via  a  se cure  cha n nel. In thi s   scena rio, the  sig ner Alice  with i dentit y  A ID  ha s the   private  key  AA Sk s Q ļ€½ , and the desi gnated verifie r  Bob ha s his  private key  B B Sk s Q ļ€½ .  Signature  G e nera tion:  T o  sig n  a  me ssag e  1 {0 , 1 } l m ļƒŽ  , the signer Alice  with private   key   A Sk  perfo rm s as follows (h ere we define   (, ) AB g eS k Q ļ€½  and it can b e  pre - comput ed):   (1)  Cho o se a ra ndom elem e n t * q rZ ļƒŽ , and com pute  12 2 (, , ) { 0 , 1 } ll r AB HI D I D g ļ” ļ€« ļ€½ļƒŽ ,  whe r e  A ID and  * {0 , 1 } B ID ļƒŽ .  (2) Comp ute  12 12 1 () | | ( ( () ) ) { 0 , 1 } ll Fm F F m m ļ¢ ļ€« ļ€½ļƒ… ļƒŽ  an d  10 [] h ļ” ļ¢ ļ€½ ļƒ… .  (3) Comp ute  () A Vr h S k ļ€½ļ€­ , a nd o u tput  (, ) B eV Q ļ³ ļ€½ .  T he sign ature  on  m e ssa ge  m  is   (, ) h ļ³ .   Signature V e rificatio n:   Given sy ste m  paramete r s  Params , identity  A ID  and  the   sign ature (, ) h ļ³ , the desig nated v e rifier Bob  with private key  B Sk  performs  as  follows :   (1) Comp ute  2 '( , , ( , ) ) . h AB A B HI D I D e Q S k ļ”ļ³ ļ€½ļƒ—   (2) Comp ute  2 '[ ] ' h ļ¢ ļ” ļ€½ļƒ… .  (3) Re cover  the  messag e  12 2 '| ' | ( | ' | ) ll mF ļ¢ ļ¢ ļ€½ ļƒ… .  (4)  Output 1  and  accept  (, ) h ļ³  as a  valid si gnatu r e of m e ssa g e   '( ) mm ļ€½ if  and only if  2 1 (' ) | ' | l Fm ļ¢ ļ€½ .  Transc ript s i mulation:  T he desi gnate d  verifier Bo b can p r odu ce the disting u ish able  sign ature Ė† ļ³  intended for hi mself by doing the followi ng steps:   (1) Ran domly   choo se * Ė† q rZ ļƒŽ , then compute Ė† U ļ€½   Ė† (, ) r BA eS k Q  and   2 Ė† Ė† (, , ) . AB HI D I D U ļ” ļ€½   (2)  Comp ute 12 1 Ė† () | | ( ( ( ) ) ) Fm F F m m ļ¢ ļ€½ļƒ… and  10 Ė† Ė† Ė† [] h ļ” ļ¢ ļ€½ļƒ… .  (3) Comp ute  Ė† Ė†Ė† (, ( ) ) B A eS k r h Q ļ³ ļ€½ļ€­ . Then  Ė† Ė† (, ) h ļ³  is also a  valid signatu r e on messa g e   m .    3.2.   Securit Analy s is    In this se ction ,  we will give se curity analy s is of ou r pro posed sch e m e .   Evaluation Warning : The document was created with Spire.PDF for Python.
                 ļ®               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 10, Octobe r 2014:  734 3  ā€“ 7352   7348 a)  Corre ctn ess :  Given a  si gnature pai r  (, ) h ļ³ , the corre c tness of the  prop osed  scheme can be  prove d   as follows:    (, ) h AB eQ S k ļ³ ļƒ—   =  (( ) , ) ( , ) h AB A B er h S k Q e Q S k ļ€­ļƒ—   =  (, ) ( , ) ( , ) rh h AB AB A B eS k Q eS k Q e Q S k ļ€­ ļƒ—ļƒ—   =   (, ) ( , ) rh h BA A B g eS k Q e Q S k ļ€­ ļƒ—ļƒ— =  r g     If  (, ) h ļ³  is a  valid sig nat ure, the n   we  have  2 (, , ) r AB HI D I D g ļ” ļ€½  and   21 [] ( ) | | hF m ļ” ļ¢ ļƒ…ļ€½ ļ€½    21 (( ( ) ) ) F Fm m ļƒ… . Thus , we obtain 12 2 || ( | | ) ll Fm ļ¢ ļ¢ ļƒ… ļ€½ .  Finally, the integrity of  m  is justified by  2 1 () | | l Fm ļ¢ ļ€½ .  b)  Non-Transferabilit y :  The non-tran sferability means t hat the design a ted veri fier  Bob can n o t prove to any  third party that the  signa ture wa s p r o duced by the signe r Alice  or  himself. In  our scheme, the non-t ransferability is  achieved throug h the  simulati on algorithm.  In  particula r, su ppo se  (' , ' ) h ļ³  is a signature whi c h is rand oml y   chose n  fro m  the set of  all valid   sign ature s  int ende d to Bob ,  then the probability P r[( , ) ( ' , ' )] 1 / ( 1 ) hh q ļ³ ļ³ ļ€½ ļ€½ļ€­ since   (' , ' ) h ļ³  is  gene rated  fro m  a rand oml y  cho s en  val ue  * q rZ ļƒŽ . Similarly, it is easy  to get that the  probability Ė† Ė† Pr [ ( , ) ( ' , ' ) ] 1 / ( 1 ) hh q ļ³ļ³ ļ€½ļ€½ ļ€­ . This  mea n s th at tran scripts si mul a ted by Bo b an d the   sign ature s  ge nerate d  by Alice hav e the i dentical distri bution, so  the y  are indistin guishable fro m   each other.   c)   Strongn ess :  Since  any i n formatio n a bout the  priv ate keys  can  not be  obtai ned   from the tran script (, ) h ļ³  in our  scheme  and  Bob's  private  key is  req u i r ed in th e ve rification   pro c ed ure, any third party  wit hout the private key  will be un abl e to che ck t he validity of the   sign ature (, ) h ļ³ . Thus, the strong ness prope rty is  achi eved i n  our p r op osed schem e.  d)  Source hidi ng:  F r om th e  sign ature ge neratio n a nd  simulatio n  al gorithm s, we  can   say that even  if the third party kno w s b o th t he sig n e r  and the  de signated ve rifier' s  private  keys,  she still  can not identify whether  the signature i s  generated  by  the original si gner or  the  desi gnate d  verifier o n  eart h . Th is is d u e  to the fact th at:    (( ) , ) ( ( ) , ) AB B A er h S k Q er h S k Q ļ³ ļ€½ļ€­ ļ€½ļ€­    Whe r e  22 (, , ( , ) ) ( , , ( , ) ) rr AB A B AB B A h H ID ID e S k Q H I D I D e S k Q ļ€½ļ€½ .           Next, we wil l  prove that the prop osed   sch eme is  existentially unforg eabl e again s t  adaptively ch ose n - me ssa ge and  cho s e n -ide ntit y atta cks ba se d on  the BDH a s sumption.   Theorem 1.  If there exi s ts  an ad aptively cho s e n -m essag e  an d ide n tity adversary A wh o   can a s k at most 1 H q times 1 H queries ,  2 H q times 2 H qu eries ,  E q times   Ke y  extracti on queries ,  S q times   Sign q u eries ,  V q times   Verif y  queries , re spe c tively, and bre a k  the p r opo se d schem e  in polynomi a l  time  t  with success  probability 2 10( 1 ) ( ) / SH S qq q q ļ„ ļ‚³ļ€« ļ€« , then there exi s ts a n   algorith m  C that can u s e A  to solve the BDH p r oble m  with prob abili ty  () BD H c A dv k  in time s pan   tā€™ , whe r e  11 1 1 1 2 22 2 () ( 1 ) ( 1 ) (1 ) EV S qq q BD H c HH H H H Ad v k qq q q q ļ„ ļ€« ļ‚³ļ€­ ļ€­ ļ€­ļ€­  , 2 ' 1 2 068 6 / 10 ( 1 ) HS tq q t q ļ‚³ļ€« 21 * () ( 3 ) ( 2 ) , H SH E S V S V P qq q q q q t q q t ļÆ ļÆ ļ€«ļ€« ļ€« ļ€« ļ€« ļ€« ļ€« * t  is  the time  to   comp ute a scala r  multipli cation in  1 G , and  P t  is the tim e  to com pute  a pairin g  op eration  on   12 (, ) GG .  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046   ļ®   Provabl y Secure an d Efficient ID-ba s e d  Strong Desi g nated Verifie r  Signature ā€¦  (Min Li)  7349 Proof.  Let C be a BDH attacker. He re ceives a ran d om instan ce (, , , ) Pa P b P c P o f  t he  BDH  pro b lem ,  his g oal i s  t o  compute   (, ) ab c eP P  after interactin g with A i n  th e above   Ga me . In  our setting,  1 H  and  2 H  are both  regarded a s  random o r a c le s.    Setup:   Firs t, C sets Pu b Pc P ļ€½  , and ge nerates the sy stem  paramete r s  Params  =  12 {, , , , , , Pub GG e q P P   12 1 2 ,, , } HH F F  runni ng the  Setup  al gorit hm, then he  send s  Params   to the  adversa ry A.  Queries :  A  adaptively i s sue s  th e q u e rie s  to  the  followin g  o r a c le s in  a  pol ynomial  boun ded nu mber of time s. The s e ora c le s are a ll  simulate d by C. To avoid colli sion s and   con s i s tently respon d  to the qu eries, C  maintains two li sts  1 {, , } , Hi i i LI D Q r ļ€½   2 {, , , } Hi j LI D I D U ļ” ļ€½  which are init ially empty.  (1)   1 H   queries :  Re ceiving  an  1 H  query on i ID , C firs t sc ans  the lis t 1 H L , then retu rns   the same a n s wer in  1 H L  if the req u e s t has bee n asked before. Otherwi se, C  sele ct s a  ran dom * iq rZ ļƒŽ , and answers the qu eries a s  follows:       ,      i f   , ,      i f   , ,          ot he r w i s e . ii A ii i B i ra P I D I D Q r b P ID ID rP ļ€½ ļƒ¬ ļƒÆ ļ€½ļ€½ ļƒ­ ļƒÆ ļƒ®     Then C a d d s   (, , ) ii i ID Q r to 1 H L . In all c a s e s ,  C returns   i Q a s  the an swer.   (2)   2 H   queries :  Wh en re ceivin g  an  2 H  query o n   (, , ) ij ID ID U , C firs t  s c ans 2 H L list ,  if the reque st  has b een a s ked b e fore, the sa me an swer i n  the list  will be retu rned.  Other wis e , C s e le cts 12 {0 , 1 } ll l ļ€« ļƒŽ at rand om, a nd sets  l ļ” ļ€½ , then a d d s (, , , ) ij ID I D U ļ” to  2 H  list  2 H L and  ret u rn s the an swer ļ” .  (3)   Ke y  extrac t i on querie s :   Whe n  A issu es a  key extractio n  q uery  on i ID , C firs t   make s a n   1 H  qu ery on i ID , rec o v e rs  the tuple (, , ) ii i ID Q r , and an swers  the que ry  as  follows :     ,    i f       ,    ,           oth e rw i s e. iP u b i A B i r P ID ID o r ID Sk ļ‚¹ ļƒ¬ ļ€½ ļƒ­ ļž ļƒ®     Then  C returns the  co rre s po ndin g  an swer  i Sk  (when iA ID ID ļ€½ or B ID , C abo rts  and  outputs ļž ).   (4)   Sign queries :  O n  receivin g a  sig nature  que ry on  me ssage   m  for  a si gne r i ID  and   the desi gnate d  verifier j ID , C does the follo wing step s:   (a)  If    iA B ID ID o r I D ļ‚¹ , then  C re covers  (, , ) ii i ID Q r from the  list 1 H L , com putes th e   sign er' s  priva t e key ii P u b i Sk r P r c P ļ€½ļ€½ , and randomly cho o se s  * q tZ ļƒŽ  to generate   the sign ature  as follo ws:   (, ) t ij Ue r c P Q ļ€½     21 2 1 1 0 [ ( , , ) ( () | | ( ( () ) ) ) ] ij h H ID ID U F m F F m m ļ€½ļƒ… ļƒ… (( ) , ) ij et h r c P Q ļ³ ļ€½ ļ€­     Evaluation Warning : The document was created with Spire.PDF for Python.
                 ļ®               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 10, Octobe r 2014:  734 3  ā€“ 7352   7350 (b)  If    j AB ID ID or ID ļ‚¹ , C re cov e rs (, , ) j jj ID Q r  from the 1 H list and  com putes the   sign er' s  priva t e key jj Sk r c P ļ€½ . Then  C sel e ct s  * q tZ ļƒŽ at random a nd p r odu ce s  the  sign ature a s  follows:   (, ) t j i Ue r c P Q ļ€½     21 2 1 1 0 [ ( , , ) ( () | | ( ( () ) ) ) ] ij h H ID ID U F m F F m m ļ€½ļƒ… ļƒ… (( ) , ) j i et h r c P Q ļ³ ļ€½ ļ€­     (c)  Otherwise, quits the proto c ol.   Eventually, C retu rn s (, ) h ļ³ as th e si gnatu r e  o n  me ssage  m  with th e  sign er' s  id entity i ID  and the de si gnated verifie r 's id entity j ID .   (5)   Verif y  queries:   Wh en  re ce iving a ve rify  query  on  the  sign ature (, ) h ļ³ for t he  sign er i ID and th e de si gnated  verifi er j ID , C  chec ks   w eather   (, ) ( , ) ij A B I D ID ID I D ļ€½ or (, ) ( , ) ij B A ID ID ID I D ļ€½   h o ld s. If it hold s , th en  qui ts it. Ot herwise,  C  rec o vers   (, , ) j jj ID Q r from the li st  1 H L  and  com put es the  de sig nated ve rifier's p r ivate  key jj Sk r c P ļ€½ to verify the given  sig nature   (, ) h ļ³ by the alg o rithm   Signatur e   Verification .  If it is true,  C re cove rs th e  messa ge, th en return s it  and o u tputs  1; or  els e , C outputs  0.  Forgery :  Fin a lly, A outputs a tuple ** (, ) h ļ³  as the forge d  si g nature o n  me ssage  * m  for   the sig ner  * i ID and the  de sign ated verifier * j ID with n o n -  negli g ible  prob ability ļ„ . If     ** (, ) ( , ) ij A B ID ID ID ID ļ€½  or ** (, ) ( , ) ij B A ID ID ID ID ļ€½ , then  C o u tputs ** (, ) h ļ³ an d proceed s.   Otherwise, C outputs  ā€œfailā€ and ab ort s  it. Addi tionally, it is requi re d  that the sign ature ** (, ) h ļ³  is  valid, and th at in the sim u lation * i ID ,  * j ID have never b een  submitted to   the  Key  extraction  queries , m o reover,  * m has n e ver b een  q uerie d d u rin g  the Sign  q uerie s  with t he  signe r' s   identity  * i ID and the de sign ate d  verifier' s  ide n tity * j ID .  If ** (, ) h ļ³ sati sfies all the con d ition s  above, C recovers the tupl e  ** * * (, , , ) ij ID ID U ļ”   f r o m   the  2 H  list, an d  then  re plays A with  the  same  ran dom  tape  but  different  choice  of the h a sh  function   2 H  by e x ploiting the  ā€œforkin g ā€ techn i que fo rmali z ed in  [15]. On  the  same  m e ssag e * m ,  C get s an oth e r valid  sign ature  (' , ' ) h ļ³  su ch t hat   * ' hh ļ‚¹ and * ' ļ³ ļ³ ļ‚¹ . The n , the BDH  probl em  with ins t ance  (, , , ) Pa P b P c P  can be e a sily  solved by C  as follo ws:   (1)  If ** (, ) ( , ) ij A B ID ID ID ID ļ€½ , we have  * ** * * * ' (, ) ' (, ) hh ji ji e S kQ e S kQ ļ³ļ³ ļƒ—ļ€½ ļƒ—   That is,   *1 (' ) * ** * * (, )( , ) ' hh ji j i eS k Q e r b c P r a P ļ³ ļ³ ļ€­ ļ€­ ļƒ¦ļƒ¶ ļ€½ļ€½ ļƒ§ļƒ· ļƒØļƒø   Then, it is ea sy to get that ** * 1 [( ' ) ] * (, ) . ' ij rr h h abc ePP ļ³ ļ³ ļ€­ ļ€­ ļƒ¦ļƒ¶ ļ€½ ļƒ§ļƒ· ļƒØļƒø   (2)  If ** (, ) ( , ) ij B A ID ID ID ID ļ€½ , simila rly, we  obtai n   *1 (' ) * ** * * (, ) ( , ) ' hh ji j i e S k Q era c Pr b P ļ³ ļ³ ļ€­ ļ€­ ļƒ¦ļƒ¶ ļ€½ļ€½ ļƒ§ļƒ· ļƒØļƒø          thus ,  ** * 1 [( ' ) ] * (, ) . ' ij rr h h abc eP P ļ³ ļ³ ļ€­ ļ€­ ļƒ¦ļƒ¶ ļ€½ ļƒ§ļƒ· ļƒØļƒø   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046   ļ®   Provabl y Secure an d Efficient ID-ba s e d  Strong Desi g nated Verifie r  Signature ā€¦  (Min Li)  7351 Followi ng thi s , we  will co mpute the p r obability t hat  C solves th e  given in stan ce of th e   BD H  pr o b l e m . C  s u cc ee ds  if:   (1)   1 : E  Durin g  the si mulation, C d oes n o t abort  any query;   (2)   2 : E  A outputs a valid and n ontrivial forgery  ** (, ) h ļ³ on messag e  * m ;  (3)   3 : E   2 E  occu rs and  C doe s not q u it in the forgery pah se.   The  pro babili ty that C  su ccee ds to  solv e the  BDH p r oblem  is  12 3 Pr[ ] E EE ļƒ™ļƒ™ , that is ,  these eve n ts  happ en sim u l t aneou sly.  From the a b o v e game, it is easy to get:     11 1 1 1 2 22 2 () ( 1 ) ( 1 ) (1 ) EV S qq q BD H c HH H H H Ad v k qq q q q ļ„ ļ€« ļ‚³ļ€­ ļ€­ ļ€­ļ€­ .      4. Results a nd Analy s is  In this sectio n, we  comp a r e ou r  schem e with  tho s e  pre s ente d  in  [8], [10-11] from the  asp e ct s of the total comm unication cost, ie.  || | | s i gna t u r e m e s s age ļ€« , and the com putatio n co st   requi re d by t he  signatu r e  gene ration  a nd verifi cati o n  procedu re s, respe c tively. In table 2,  we  denote by  P  a  computatio n  of the pairin g  operation,  S  a scal a r multiplication in 1 G ,  E an  expone ntiatio n  in 2 G , and H an unefficie n t ā€œMaptoPointā€  hash fun c tio n . We  also  denote th e   total sig natu r e len g th a n d  the  bit len g t h of a  poi nt in  1 G  by  TS L ļ€­  an d  1 || G (assum e t hat 12 || | | GG ļ€½ ), respe c tively. For some  operatio ns  su ch a s  addi tions in 1 G , XO R in the bin a ry  system  and t he commo n h a sh fu nctio n , they are  so  efficient that th ey all ca n be  negle c ted i n  the   comp ari s o n .       Table 2. The  Comp ari s o n  of Several Existing Sch e m e s  Schemes  Sign Verif y   TS-L   Strongness  Scheme in [8]  4 S+H  3 P+H  3 |G 1 |+m  Ć—  Scheme in [10]  2 S+ 2 P+E  P+E  2 |G 1 |+m  Ć—  Scheme in [11]  2 S+ 2 P+E  2 P+S  2 |G 1 |+m   āˆš   Our scheme   S+ 2 P+E  P+E |G 1 |+|q|   āˆš       From th e co mpari s o n  ab ove, we  can   see th at, wh en si gnin g  th e sa me me ssag es, o u r  prop osed scheme is mu ch more effici ent on the  whole, and the  total commu nicatio n  co st is   much  le ss th an the  others sin c e  no me ssage  or j u st  partial  me ssage n eed s to  be tra n smitted   along  with th e sig natu r e.  What i s  mo re, our  sc he m e  sati sfies th e strong ne ss pro perty, wh ile   others excep t  [11] can n o t. As far as  we  kno w , it is the first IBSDVS schem e with me ssage   recovery i n  t he lite r ature,  whi c h  not  onl y req u ir e s  lo w  com putatio n po we r, b u t also  ha s  sm all  comm uni cat i on co st .       5. Conclusio n   In this paper,  we put forwa r d the first efficient IBSDVSMR schem e  and give its se curity  proof  in th e  random  o r a c le  mod e l b a se d on  the  BDH a s sum p tio n s. T he  prop ose d   scheme  ha s   both lo w co mputation  an d commu nication  co st, a nd  can   sup p o rt the  st ron gne ss p r op erty of  SDVS.            Evaluation Warning : The document was created with Spire.PDF for Python.
                 ļ®               ISSN: 23 02-4 046                     TELKOM NI KA  Vol. 12, No. 10, Octobe r 2014:  734 3  ā€“ 7352   7352 Referen ces   [1]    A Sham ir. Ide n tit y -b ase d  cr yptos y stems a n d  si gnat ure sc hemes. G.R.  Blake l y , D.  C haum   Edit ors .  Cr ypto 19 84, L NCS 19 6, Spri nger-v er la g, Califor nia, USA, 198 4: 7-53.   [2]    D Ch aum. Z e ro-kno w l e dge   und eni ab le si g natures.   Adv a nces i n  Cr ypt o lo g y - Eurocr ypt' 90, LNCS.   Sprin ger-Ver la g.  1990; 4 73: 4 58-4 64.   [3]    D Cha u m, H van Ant w er pe n. Und eni abl e  signat ures.   Advanc es in Cr ypt o lo g y - Cr yp to' 89, LNC S .   Springer-Ver lag . 1990; 4 35: 1 2 -21 6 .  [4]    M Jakobss on,  K Sako, R  Imp agli a zzo.  Desi gnate d   ver i fier proofs and   the i r  app lic ations. Advanc es  i n   Cr yptol o g y -Eur ocr y pt' 96,  LNC S . Springer-V e r lag.  19 96; 10 7 0 : 143-1 54.   [5]    S Saee dni a, S Kramer, O Markovitch. An effi cient stron g  de sign ated ver i fie r  signat ure sch eme.   ICISC  200 3.  Sprin ger -Verla g, Berlin .  2003: 4 0 -54.   [6]    W  Susilo, F  Z h ang, Y Mu. Identit y - b a se d st rong d e sig nate d  verifier sig n a t ure schemes.  Lecture Notes  in Co mputer S c ienc e (LNCS) .  2004; 3 108: 3 13-3 24.   [7]   X H uan g, W  Susil o , Y Mu, F  Z hang. Short i dentit y-b a s ed strong  de sign at ed ver i fi er sign ature   schemes.  Lect u re Notes i n  C o mputer Sci e n c e ( LNCS).  20 06; 390 3: 214- 225.   [8]    J Z hang, J M a o. A nov el ID-b ased  des ign a ted ver i fier si gn ature sch eme.  Information  Sci ences. 2 0 0 8 ;   178( 3): 766- 77 3.   [9]    BB Kang, C B o yd, E Da w s o n . Identit y-bas ed stro n g  des i gnate d  verifi er  signat ure sch emes: attacks   and n e w  co nstruction.  Co mput ers & Electrical  Engin eeri n g . 2 009; 35( 1): 49- 53.   [10]    BB Kan g , C B o yd, E D a w s o n . A nov el  ide n tit y -  base d  str ong  des ign a te d verifi er si gna ture schem e .   T he Journ a l of  Systems a nd S o ftw are . 2009; 82(2): 27 0 - 27 3.   [11]    J Le e, J C h a n g , D  Lee. F o rger y   attacks o n  Ka ng  et  a l .ā€™ s id entit y - bas e d  stron g  d e si g nated  verifi er   sign ature sc he me an d its  im provem ent  w i t h  secur i t y  pro o f.  Co mp uters  & Electric al  Engi neer in g,   Co mp uter& Ele c trical Eng i ne e r ing . 20 10; 36( 5): 948-9 54.   [12]    R T s o, C Gu,  T   Okamoto, et al. Efficient ID- B ased  Dig ital  Sign atures  w i t h  Messa ge R e cover y . F .  Ba o   et al.  Editors . CANS 20 07, L NCS 48 56, Spr i ng er-Verl ag. 2 007: 47- 59.   [13]    K Barr, K Asan ovic. Ener g y - a w a re l o ssless  data com p ressi on.  Jour nal A C M T r ansaction  on Co mpute r   System s  (T OC S). 2006; 24( 3) : 250-29 1.  [14]    M Bellare, P Rog a w a y.  Ra n d o m  oracl e s a r e practical: a  para d ig m for d e sig n in g efficie n t protocols .  Procee din g  CC Sā€™ 93 of 1 st  AC M conferenc e on comp uter a nd commu nicat i ons sec u rit y . 1 993: 62- 73.   [15]   D Pointch e va l, J Stern. Securi t y  pro o fs  for signatur e schem es. Eurocr ypt 1 996. LN CS, 10 70.  Sprin ger- Verlag.  199 6: 387-3 98.   [16]    E Yoo n . An  efficient  an d s e cure  id entit y-bas e d   strong  desi g n a ted   verifier s i g nat ure sc heme.   Information  T e chno logy and Contro l . 201 1; 40(4): 32 3-3 2 9 .       Evaluation Warning : The document was created with Spire.PDF for Python.