I nte rna t io na l J o urna l o f   E lect rica l a nd   Co m p ute r  E ng in ee ring   ( I J E CE )   Vo l.   7 ,   No .   5 ,  Octo b e r   2 0 1 7 ,   p p .   2 6 7 4 ~2 682   I SS N:  2 0 8 8 - 8708 ,  DOI : 1 0 . 1 1 5 9 1 / i j ec e . v7 i 5 . p p 2 6 7 4 - 2 682          2674       J o ur na l ho m ep a g e :  h ttp : //ia e s jo u r n a l.c o m/o n lin e/in d ex . p h p /I JE C E   Identity - Ba sed  Blind Sig na ture  Sch e m e  w ith  M ess a g e Rec o v ery       Sa lo m e  J a m es 1 ,  T .   G o w ri 2 ,   G . V.   Ra m es h B a bu 3 ,   P .   Va s ud ev a   Reddy 4   1, 4 De p ar t m e n t   o f   En g in e e rin g   M a th e m a ti c s,  A n d h ra   Un iv e rsity ,   V isa k h a p a tn a m ,   In d ia.   2 De p a rtme n t   o f   ECE ,   G IT ,   G I TAM   Un iv e rsity ,   V isa k h a p a tn a m ,   In d ia.   3 De p a rtme n t  o f   Co m p u ter S c ien c e ,   S .   V . Un iv e rsit y ,   T iru p a ti ,   In d ia .       Art icle  I nfo     AB ST RAC T     A r ticle  his to r y:   R ec eiv ed   Dec   10 ,   2 0 1 6   R ev i s ed   A p r   2 5 ,   2 0 1 7   A cc ep ted   J u n   11 ,   2 0 1 7       Bli n d   sig n a tu re   a ll o w s  a   u se r  to   o b tain   a   sig n a tu re   o n   a   m e s s a g e   w it h o u t   re v e a li n g   a n y th in g   a b o u t  t h e   m e s sa g e   to   th e   sig n e r.   Bli n d   sig n a tu re s  p la y   a n   im p o rtan t  ro le  i n   m a n y   re a l  wo rld   a p p li c a ti o n s  su c h   a s  e - v o ti n g ,   e - c a sh   s y ste m   w h e re   a n o n y m it y   is  o f   g re a t  c o n c e rn .   Du e   to   th e   ra p id   g ro w th   in   p o p u larity   o f  b o th   w ire les s   c o m m u n ica ti o n s  a n d   m o b il e   d e v ice s,  th e   d e sig n   o f   se c u re   sc h e m e s  w it h   lo w - b a n d w id th   c a p a b il it y   is  a n   im p o rtan t  re se a rc h   issu e .   In   th is  p a p e r,   w e   p re se n t  a   n e w   b li n d   sig n a tu re   sc h e m e   w it h   m e ss a g e   re c o v e r y   in   th e   ID - b a se d   se tt in g   u sin g   b il in e a r  p a iri n g s  o v e r  e ll ip t ic  c u rv e s.  T h e   p ro p o se d   sc h e m e   is  u n f o rg e a b le  w it h   th e   a ss u m p ti o n   th a t  t h e   Co m p u tatio n a l   Dif f ie - He ll m a n   p ro b lem   is  h a rd .   W e   c o m p a re   o u r  sc h e m e   w it h   th e   re late d   sc h e m e s  in   term s  o f   c o m p u tatio n a l  a n d   c o m m u n ica ti o n a l   p o i n t  o f   v ie w .   K ey w o r d s :   B ilin ea r   p air in g s   B lin d   s ig n at u r e   C d h   p r o b lem   Id - b ased   cr y p to g r ap h y   Me s s a g e  r ec o v er y   Co p y rig h t  ©   2 0 1 7   In stit u te o f  A d v a n c e d   E n g i n e e rin g   a n d   S c ien c e .    Al l  rig h ts  re se rv e d .   C o r r e s p o nd ing   A uth o r :   P .   Vasu d ev a  R ed d y ,   Dep ar t m en t o f   E n g i n ee r in g   M ath e m atics ,   An d h r a  U n iv er s it y ,   Vis ak h ap at n a m ,   A . P .   I n d id a.   E m ail:  v as u cr y p to @ y a h o o . co m ,   v a s u cr y p to . e n g m at h @ au v s p . ed u . in       1.   I NT RO D UCT I O N       A   d i g ital  s i g n at u r e  s c h e m e  w it h   m e s s a g e  r ec o v er y   is   a  s ig n at u r e  s c h e m e  in   w h ich   t h e  o r ig i n al   m es s ag e  o f   t h e  s i g n at u r e  is   n o t  r eq u ir ed   to   b e  tr an s m itte d   to g eth er   w it h   t h e  s ig n at u r e  s in ce   it  h a s   b ee n   ap p en d ed   to   th e  s ig n atu r e  a n d   ca n   b e  r ec o v er ed   ac co r d in g   to   th e  v er i f icatio n / m e s s a g e  r ec o v er y   p r o ce s s .   I t  is   d if f er e n t  to   a n   a u th e n tica ted   en cr y p tio n   s c h e m e   o r   s i g n cr y p tio n   s c h e m e,   s i n ce   i n   t h i s   s c h e m e,   t h e  e m b ed d ed   m es s ag e  ca n   b e  r ec o v er ed   b y   an y o n e  w it h o u t  t h e  s ec r et  i n f o r m atio n .   T h e  p u r p o s e  o f   t h is   k in d   o f   s i g n at u r es  is   to   m i n i m ize  t h e  to tal   len g t h   o f   t h e  o r ig in al   m e s s a g e  a n d   t h e  ap p en d ed   s ig n at u r e.   So ,   th e s e  ar e  u s e f u l   in   an y   o r g an izatio n   w h er e  b an d w id t h   is   o n e  o f   th e  m ai n   co n ce r n   o r   f o r   th e  ap p licatio n   in   w h ich   s m all  m es s a g e  s h o u ld   b e  s ig n ed .   B lin d   s ig n at u r e  s ch e m e  w as  i n tr o d u ce d   b y   C h a u m   [ 1 ]   in   1 9 8 2   to   p r o v id e  th e  an o n y m i t y   o f   th e  u s e r   an d   p la y s   a   ce n tr al   r o le  i n   c r y p to g r ap h ic  p r o to co ls   s u c h   as  e - v o ti n g ,   e - p a y m en t[ 2 ] ,   [ 3 ] .   Su c h   a   s i g n atu r e   allo w s   a  u s er   to   o b tain   a  s ig n atu r e  o f   a  m ess a g e  i n   a  w a y   t h at  t h e  s i g n er   lear n s   n eit h er   t h e  m e s s a g e  n o r   th e  r esu lti n g   s i g n a tu r e.   T h e  s ch e m e  ca n   en s u r e  u n tr ac ea b ilit y   an d   u n li n k ab il it y .     W ith   t h e  ad v a n tag e s   o f   I D - b a s ed   cr y p to g r ap h y ,   s ev er al  I D - b ased   s ig n at u r e  s ch e m e s   an d   an d   th eir   v ar ian t s   h a v e  b ee n   p r o p o s ed   in   t h e  liter atu r e   [ 2 ] - [ 4 ] .   T h e  f ir s t  I D - b ased   b li n d   s i g n atu r e   s c h e m e   w a s   p r o p o s ed   b y   Z h a n g   a n d   Ki m   [ 5 ]   in   Asi a cr y p t  2 0 0 2 .   L ater ,   in   2 0 0 3 ,   Z h an g   a n d   Ki m   [ 6 ]   p r o p o s ed   a  n e w   I D - b ased   b lin d   s ig n at u r e  s c h e m e  b ased   o n   b ilin ea r   p air in g s .   I n   2 0 0 5 ,   Hu a n g   et  al.   [ 7 ]   p r o p o s ed   I D - b ased   b lin d   s i g n a tu r e   s ch e m es  u s in g   b ili n ea r   p air in g s   a n d   s h o w ed   t h at  t h e  s c h e m es  ar e  n o t  s ec u r e  if   t h e  R OS  p r o b lem   i s   s o lv ab le.   I n   2 0 0 6 ,   Z h ao   et   al.   [ 8 ]   p r esen ted   a n o th er   b lin d   s i g n at u r e  s c h e m e  i s   e f f icien t  t h an   Z h a n g   an d   Ki m ' s     s ch e m es  [ 5 ] ,   [ 6 ] .   A   g en er aliz ed   I D - b ased   b lin d   s i g n at u r e  f r o m   b il in ea r   p air in g s   w as  p r o p o s ed   in   2 0 0 7   b y   Kalk a n   et   al.   [ 9 ] .   An   I D - b ase d   au t h en tica ted   b lin d   s i g n at u r e  s ch e m e   f r o m   b ili n ea r   p air in g s   w as  p r o p o s ed   b y   Z h ao   et  al.   i n   2 0 0 7   [ 1 0 ] .   I n   2 0 1 0 ,   B . U.   R ao   et  al.   [ 1 1 ]   p r o p o s ed   I D - b ased   b lin d   s ig n a tu r e  s c h e m es  f r o m   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708       I d en tity - B a s ed   B lin d   S ig n a tu r e  S ch eme   w ith   Mes s a g e  R ec o ve r y  ( S a lo me  Ja mes )   2675   b ilin ea r   p air in g s   an d   is   ef f ici en t  th a n   th e  p r ev io u s   I D - b ase d   b lin d   s ig n at u r e  s h a m e s .   I n   2 0 1 3   Xu   et  al.   [ 1 2 ]   p r o p o s ed   an d   I D - b ased   b li n d   s i g n at u r e  s ch e m e   w it h   u n lin k ab ilit y .   I n   2 0 1 4 ,   P an ce   et  al.   [ 1 3 ]   p r o p o s ed   a  co m p ar is o n   o f   I D - b ased   b lin d   s ig n at u r es  f r o m   p air in g s   f o r   e - v o tin g   p r o to co ls .   A   b li n d   s ig n at u r e  w i th   m es s a g e  r ec o v er y   is   i m p o r ta n t  in   co m m u n icatio n   w h ic h   r eq u ir es  t h e  s m aller   b an d w id t h   f o r   s i g n ed   m e s s a g e s   t h an   s i g n atu r e s   w it h o u t  m es s ag e - r ec o v er y .   I n   2 0 0 5 ,   Han   e t  al.   [ 1 4 ]   p r o p o s ed   a  p air in g - b ased   b lin d   s i g n at u r e  s ch e m e   w it h   m e s s a g e  r ec o v er y   b ased   o n   m o d i f ied   W eil /  T ate  p air in g s   o v er   ellip tic  cu r v e s .   T h i s   s ch e m e  n ee d s   s m aller   b an d w id t h   an d   i m p r o v es  t h e  co m m u n icatio n   ef f icien c y   t h an   o t h er   p r ev io u s   I D - b ased   b lin d   s ig n atu r es.  A l s o   th i s   s c h e m e  p r o v id es  h i g h   s ec u r it y   w it h   s m all er   k e y s   i n   s ize.     I n   2 0 0 9 ,   W an g   et  al.   [ 1 5 ]   p r o p o s ed   o p ti m al  b lin d   s ig n at u r e  p ad d in g   w it h   m es s ag e  r ec o v er y .   T h is   s c h e m e  u s e s   an   id ea l  cip h er   w it h   a  s m a ll er   b lo ck   s ize  to   d esig n   a  s e cu r e  t w o - m o v e  b lin d   s i g n a tu r e  w it h   an   o p ti m al   p ad d in g .   T h eir   s ch e m e  h as  t h e  m es s ag e  r ec o v er y   p r o p er ty   w it h   le s s   b a n d w id th .     Z h an g   e t  al.   [ 1 6 ]   p r o p o s ed   a   k in d   o f   m e s s a g e - r ec o v er ab le  f air n es s   b li n d   d ig i tal  s ig n at u r e  s c h e m e  i n   2 0 1 1 .     I D - b a s ed   b lin d   s ig n at u r e   s ch e m es  w it h   m e s s a g e  r ec o v er y   s c h e m es  ar e  also   p r o p o s ed   [ 1 7 ] - [ 1 9 ] .   I n   2 0 0 5 ,   Han   et  al.   [ 1 3 ]   p r o p o s ed   a   p air in g - b ased   b lin d   s ig n at u r e  w it h   m es s a g e  r ec o v er y .     I n   2 0 0 6 ,   Hass an   et  al.   [ 1 7 ]   p r o p o s ed   a  n e w   b li n d   I D - b ased   s ig n at u r e  s ch e m e  w it h   m es s ag e  r ec o v er y   w h ic h   i m p r o v es  th e  co m p u tatio n al  e f f icie n c y   i n   th e  Han   et  al.   s ch e m e  [ 1 4 ] .   I t a ch iev es b an d w id t h   s a v i n g s   an d   is   s u i tab le  f o r   s ig n i n g   s h o r t  m es s ag e s .     I n   th i s   p ap er ,   b y   co n s id er i n g   t h e  ab o v e  ad v an tag e s ,   w e  d es i g n ed   a  n e w   b li n d   s i g n atu r e  s c h e m e  w it h   m es s ag e  r ec o v er y   in   th e  id e n tit y - b ased   s etti n g .   T h e  p r o p o s ed   I B B SS MR  s ch e m e  i s   b ased   o n   th e  b ili n ea r   p air in g s   o v er   ellip tic  c u r v e s   a n d   is   d esi g n ed   f o r   th e  m e s s a g es  o f   f i x ed   le n g th .   T h e  s c h e m e  is   u s ef u l  w h er e  t h e  an o n y m i t y   o f   t h e  u s er s   an d   b an d w id th   co n s tr ain t s   ar e  o f   g r ea t  co n ce r n .   T h e  p r o p o s ed   s ch e m e  is   u n f o r g ea b le   w it h   t h e  as s u m p tio n   t h at  t h e  C o m p u tatio n al  Di f f ie - Hell m an   p r o b lem   is   h ar d .     T h e  r est  o f   th e  p ap er   is   o r g an i ze d   as  f o llo w s .   I n   s ec tio n   2 ,   m at h e m a tical  p r eli m i n ar ies  ar e  p r o v id ed .   Sectio n   3   p r esen t s   t h e   s y n ta x   a n d   s ec u r it y   m o d el  o f   t h e   p r o p o s ed   I B B SS MR  s ch e m e.   I n   Sectio n   4 ,   a n   id en tit y - b ased   b li n d   s ig n at u r e   s ch e m e  w it h   m e s s a g e  r ec o v er y   i s   p r o p o s ed .   I n   Sectio n   5 ,     th e    p r o o f     o f     co r r ec tn ess ,     s ec u r it y   a n al y s i s   an d   th e  ef f icie n c y   a n al y s i s     o f     th e    p r o p o s ed     s ch e m e  ar e  p r esen ted .     Fin all y ,   Sectio n   6   co n clu d e s   th e  p ap er .       2.   P RE L I M I NARIE S   I n   th is   s ec t io n ,   w e  w i ll  b r ief l y   d is c u s s   th e  b asic  co n c ep ts   o n   b ilin ea r   p air in g s   an d   r elate d   co m p u tatio n al  h ar d   p r o b lem s .     2 . 1 .     B ilin ea r   P a iring s   I t  is   an   i m p o r ta n t  cr y p to g r ap h ic  p r i m it iv e  a n d   is   w id el y   a d o p ted   in   m a n y   p o s it iv e  ap p l icatio n s   o f   cr y p to g r ap h y .   L et  1 , G   an d   2 ,  . G   b e  t w o   cy c lic  g r o u p s   o f   s a m e  p r i m e  o r d er   q .   L et  P   b e  a  g e n er ato r   o f   1 . G   A   b ili n ea r   p air in g   i s   a  m ap   ˆ e   d ef i n ed   b y     1 1 2 ˆ : e G G G    s atis f y in g   t h e  f o llo w i n g   p r o p er ties :   1.   B ilin ea r it y : Fo r   all  1 ,  P Q G   an d   * ,   , q a b Z   ˆˆ ( ,   ) ( ,   ) . ab e aP bQ e P Q     2.   No n - De g e n er ac y : T h er e  ex i s ts   1 PG   s u ch   t h at  ˆ ( ,   ) 1 . e P P   3.   C o m p u tab ilit y : T h er e  ex is ts   a n   ef f icie n t a l g o r ith m   to   co m p u te  ˆ ( ,   ) e P Q   f o r   all  1 ,   . P Q G   Su c h   a  p air in g   ˆ e   is   ca lled   an   ad m is s ib le  p air in g   a n d   ca n   b e  co n s tr u cted   b y   t h e  m o d if i ed   W eil  o r   T at e   p air in g s   o n   ellip tic  cu r v es d e f i n ed   o v er   a  f in ite  f ield .     2 . 2 .     B ilin ea r   P a iring s   o v er   E llip t ic  C urv es   T h e    m o d if ied     W eil    p air in g     an d     T ate    p air in g     ar e    ad m is s ib le    i n s ta n tiatio n s     o f     b ili n ea r     p air in g s .   T h e  m o d if ied   W eil  p air in g   s ett in g s   ar e  b r ief l y   d is c u s s ed .  L et    p    b e  a  s u f f icien tl y   lar g e   p r im e  s u c h   th at   2 m o d 3 p    an d 1 p l q  ,   w h er e    q   is   also   a  lar g e  p r im e.   L et    E   b e  an   ellip tic  c u r v e  d ef i n ed   b y       th e   eq u atio n     23 1 yx     o v er p F .   Def in e      ( ) p EF    to     b e     th e    g r o u p     o f     p o in ts     o n     E    o v er     p F .   L et      ( ) p P E F    b e    a    p o in t     o f     o r d er     q   an d     1 G    b e    th e     s u b g r o u p     o f     p o in ts     g e n er ated     b y     . P   L e t    2 G    b e     th e    s u b g r o u p     o f     2 * p F    o f     o r d er     q .   T h e    m o d if ied     W eil    p air in g     is     th u s     d e f i n ed     b y     1 1 2 ˆ   :   e G G G     s ati s f y in g     t h e    co n d itio n s     o f     a    b ilin ea r     p air in g .             Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E     Vo l.  7 ,   No .   5 ,  Octo b er   2 0 1 7   :   2 6 7 4   –   2 6 8 2   2676   2 . 3 .      M a p - to - P o int    H a s h   f un ct io n    C o n s id er     a    h as h     f u n ctio n     * * 11 : 0 , 1 . HG   I t    is     s u f f icie n t    to     h av e    a    h as h     f u n ctio n     * 1 : 0 , 1 HA    f o r     s o m e    s et    A    an d     an     en c o d in g     f u n ct io n     * 1 : L A G .     T h e  en co d i n g   f u n ctio n   L     is     ca lled     Ma p - to - P o in t.  Ag ai n ,   let    p   b e  a  p r im e  s ati s f y i n g 2 m od 3  a nd   1 p p l q ,   w h er e    q    is   also   pr im e.   L et  E   b e  th e  ellip tic  cu r v e  d ef in ed   b y   t h e  eq u atio n   23 1 yx    o v er p F .     L et    1 G   b e  th e  s u b g r o u p   o f   p o in ts   o n     E   o f   o r d er   q .   Su p p o s e  w e  alr ea d y   h a v e  a  h as h   f u n ct io n * 1 : 0 , 1 p HF .     A   Ma p - to - P o in t a lg o r it h m   wo r k s   as f o llo w s   o n   in p u t 0 p yF .   1.   C o m p u te 1 ( 2 1 ) / 3 22 3 0 0 0 11 p p x y y F .   2.   L et    00 , ( ) p Q x y E F     an d   s et    1 ID Q l Q G  .   3.   Ou tp u t M ap - to - P o in t   0 () ID yQ .     2 . 4 .        Co m pu t a t io na l   P ro blem s   T h is   s ec tio n   p r esen ts   s o m e    co m p u tatio n al    p r o b lem s     w h ic h     w ill    f o r m     t h e    b asis     o f     s ec u r it y     f o r     o u r     I B B SS MR sch e m e.   1.   Dis cr ete    L o g ar it h m     P r o b lem   ( DL P ) :  Giv en     t w o     g r o u p     ele m en ts         an d     PQ ,   f in d     an     in te g er     n    s u c h     th at    Q n P    w h en e v er     s u c h     a n     in te g er     ex i s ts .   2.   Dec is io n al  D if f ie - Hell m a n   P r o b lem   ( DDHP ) :  Fo r   * , ,   Rq a b c Z ,     g iv en     , , , P a P b P c P d ec id e    w h et h er     m od c ab q .   3.   C o m p u tatio n al  D if f ie - Hel l m a n   P r o b lem   ( C D HP ) :  Fo r * ,  Rq a b Z ,   g iv e n     ,, P a P b P    co m p u te abP .   T h r o u g h o u t th i s   p ap er ,   w e  ass u m e  t h at  C D HP   an d   D L P   ar e  i n tr ac tab le.         3.   SYNT A X  AND  S E CUR I T Y  O F   T H E   P RO P O SE D  I B B S SM R  SCH E M E   I n   th i s   s ec tio n   w e  p r esen t t h e  s y n ta x   a n d   s ec u r it y   m o d el  o f   t h e  p r o p o s ed   I B B SS MR sch e m e .     3 . 1 .     Sy nt a x   o f   I B B SS M R   Ou r   b lin d   s ig n at u r e  s ch e m e  w it h   m ess a g e  r ec o v er y   is   a n   ex te n s io n   o f   o r d in ar y   b lin d   s ig n a tu r e  s ch e m e.   T h is   s c h e m e   co n s is t s   o f   t h e  f o llo w i n g   f o u r   al g o r ith m s :   S y s te m   Set u p ,   Ke y   E x tr a ct,   B lin d   Si g n at u r e  Gen er atio n ,   B li n d   Si g n at u r e  Ver if icat io n   w i th   Me s s ag e   R ec o v er y .     T h e  d etailed   d escr ip tio n   o f   th e s e   alg o r ith m s   i s   d es cr ib ed .     1.   S y s te m   Set u p :  Fo r   a  g iv e n   s e cu r it y   p ar a m eter   , kZ   th e  Ke y   Ge n er atio n   C en tr e  ( KG C )   r u n   th is   alg o r ith m   an d   g e n er ates  t h e  s y s te m   p ar a m e ter s   P a r a ms  an d   th e  m a s ter   k e y   s .  P a r a ms   ar e  m ad e  p u b lic  an d   s   is   k ep t secr et.   P a r a ms  ar e  i m p licit i n p u t to   all  th e  f o llo w i n g   alg o r it h m s .   2.   Ke y   E x tr ac t:    Fo r   a  g iv e n   u s er ’ s   id e n tit y   ID ,   t h e  KG C   r u n s   t h is   al g o r it h m   to   g e n er ate  t h e  p u b lic  k e y   ID Q   an d   th e  p r iv ate  k e y   . ID d   KGC s e n d s   ID d   to   th e  co r r esp o n d in g   u s er   t h r o u g h   a  s ec u r e  ch a n n e l.   3.   B lin d   Sig n at u r e  Gen er atio n :  T h is   i s   an   i n ter ac ti v e  an d   p r o b ab ilis tic  p o l y n o m ial  t i m e  p r o to co l,  w h ich   is   o p er ated   b y   t h e   u s er   a n d   t h e  s ig n er .   T h e  u s er   f ir s t  b li n d s   th e   m es s ag e   M   an d   o b tain s   a  n e w  v er s io n   h   o f   , M   an d   th e n   s e n d s   it   to   th e  s ig n er .   T h e  s ig n er   u s e s   h i s /h er   p r iv ate  k e y   to   s ig n   o n   h   an d   o b tain s   , V   an d   t h e n   s e n d s   i t  to   th e  u s er .   T h e  u s er   u n b li n d s   it  to   o b tain   , V   w h ich   is   a  b l in d   s ig n at u r e  o n   th e  o r ig in al  . M   4.   B lin d   Sig n at u r e  Ver if icatio n   w it h   Me s s a g e  R ec o v er y :  F o r   a  s ig n er ’ s   id e n tit y   I D  an d   a  b lin d   s ig n at u r e  ,   a  v er if ier   r u n s   th i s   alg o r ith m   to   r ec o v er   th e  m es s a g e  an d   ch ec k   th e  v al id it y   o f   t h e  b lin d   s ig n at u r e  ,   m o r e  p r ec is el y ,   t h e  alg o r ith m   V eri fy   ( ,   ) ID    o u tp u ts   1   i f   ac ce p ted ,   o r   0   if   r ej e cted .     3 . 2 .      Securit y   Re qu ire m ent s   o f   t he  P ro po s ed  I B B SS M R   A   s ec u r e  b lin d   s i g n at u r e  s ch e m e  m u s t sati s f y   t h e  f o llo w i n g   r eq u ir e m en ts :   1.   C o r r ec tn ess :  I f     th e    u s er     an d     th e    s ig n er ,   b o th     c o m p l y     w it h   th e  al g o r ith m     o f     b lin d     s ig n a tu r e     g en er atio n ,   t h en     t h e     b li n d     s ig n at u r e    V   w ill     al w a y s     b e    ac ce p ted .   T h e    co r r ec tn ess     o f     t h e     Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708       I d en tity - B a s ed   B lin d   S ig n a tu r e  S ch eme   w ith   Mes s a g e  R ec o ve r y  ( S a lo me  Ja mes )   2677   s ig n at u r e    o f     a    m es s a g e    s ig n ed     th r o u g h     th e    s ig n atu r e    s ch e m e    ca n     b e    ch ec k ed     b y     an y o n e     u s i n g     th e    s i g n er ’ s     p u b lic    k e y .   2.   B lin d n es s   :  A    s i g n at u r e    is     s a id     to     b e    b l in d     i f     a     g iv e n     m ess a g e - s i g n at u r e    p air     a n d     t h e    s i g n er ’ s     v ie w     ar e    s tat is tical l y     i n d ep en d en t.  W h i le    co r r ec tl y     o p er atin g     o n e    i n s tan ce     o f     th e    b li n d     s ig n at u r e    s c h e m e,   let    th e     o u tp u t    b e    ( ,   ) MV   ( i.e ,   m es s a g e - s i g n at u r e    p air )     an d     th e    v ie w     o f   t h e     p r o to co l   . V   A t     a    later     ti m e,   th e    s i g n er     i s     n o t   ab le    to     li n k     V   to     ( ,   ). MV T h e    co n ten t   o f     th e     m es s ag e    s h o u ld     b e    b lin d     t o     th e    s ig n er ;  th e    s ig n er     o f     th e    b lin d     s ig n at u r e    d o es    n o t    s ee     th e    co n ten t   o f     t h e    m e s s a g e.   3.   Un f o r g ea b ilit y   :  I t    i s     w i th     r esp ec t    to     th e     u s er     esp ec iall y ,   i.e .   th e     u s er     is     n o t    ab le    to     f o r g e     b lin d     s i g n a tu r es    w h ich     ar e    a cc ep ted     b y     t h e    al g o r ith m     o f     v er if icatio n     o f     b li n d     s i g n at u r es.  On l y     th e    s i g n er     ca n     g i v e    a    v alid     s ig n at u r e    f o r     th e    ass o ciate d     m es s ag e.       4.   P RO P O SE D  I D - B AS E D  B L I ND  SI G N AT U RE   S CH E M E   WI T H   M E SS AG E   R E CO VE RY    I n     th is     s ec tio n ,     w e    p r esen t     o u r     I D - b ased     b lin d     s ig n a tu r e    s ch e m e    w i th     m e s s a g e    r ec o v er y   ( I B B B SS MR)  s c h e m e.   As  d i s cu s s ed   i n   Sectio n   3 . 1 ,   th e  d etailed   f u n ct io n alit ies  o f   t h ese  al g o r ith m s   ar e   p r esen ted .   1.   S y s te m   Set u p :  Fo r   a  g i v en   s ec u r it y   p ar a m eter   , kZ   th e  KGC   r u n s   t h is   al g o r it h m   as  f o llo w s .   C h o o s es   t w o   g r o u p s     12 ,  GG    o f   s am e  p r i m e   o r d e r   2 k q   w it h   a  b ilin ea r   p air in g   1 1 2 1 ˆ : ;   e G G G G     is   an   ad d itiv e  c y clic  g r o u p   w it h   1 PG   as a   g en er ato r   an d   2 G   is   a  m u lt ip licativ e  c y c lic  g r o u p .     a.   Selects  * q sZ   r an d o m l y   a n d   co m p u t es th e  s y s te m   p u b lic  k e y   . pub P s P     b.   C h o o s es   a  m ap - to - p o in t   h as h   f u n ctio n   * 11 : { 0 ,   1 } HG   an d   t h r ee   cr y p to g r ap h ic  h a s h   f u n ctio n s   12 * 22 : { 0 ,  1}   { 0 ,  1} , ll HG      1 2 2 1 12   : { 0 ,  1} { 0 ,  1} ,   : { 0 ,  1} { 0 ,  1} . l l l l FF    c.   No w   KGC   p u b lis h es   t h e  s y s t e m   p ar a m eter s   as   1 2 1 2 1 2 ˆ { ,   ,   ,   ,   ,   ,   ,   ,   ,   } pub P a r a m s G G e q P P H H F F   as p u b lic  an d   k ee p s   t h e  m aster   k e y   s    as secr et.   2.   Ke y   E x tr ac t  :  Gi v en     a n     u s e r ’ s     id en tit y     I D,   th e    KGC    co m p u tes    t h e    co r r esp o n d in g     p r iv ate    k e y     ID ID d s Q   w h er e    1 () ID Q H I D   is     th e    p u b lic    k e y     o f     th e    u s er     an d     t h en     s en d s     it    to     t h e   co r r esp o n d in g   u s er   I D    th r o u g h     a    s ec u r e    ch a n n e l.   3.   B lin d   Si g n atu r e  Gen er atio n   :   I n   o r d er     to     s ig n     a    m ess a g e     1 { 0 ,   1 } l M   b lin d l y     b y     a     s i g n er ,   w h o s e    id en tit y     i s     ID ; th e    u s er     an d     th e    s i g n er     s h o u ld     r u n     th e    b l in d     s ig n at u r e    p r o to co l.     [ B lin d   Sig n atu r e  I s s u in g   P r o to co l]     Su p p o s e  th at    M   is   th e  m es s ag e  t o   b e  s ig n ed .   T h e  b lin d   s ig n at u r e  p r o t o co l is sh o w n   i n   Fi g u r e  1 .   a.   T h e    s ig n er     r an d o m l y       c h o o s es    a    n u m b er     * , q rZ    co m p u tes    ID X r d    an d     s e n d s     X    to     th e    u s er     as   a    co m m it m en t.   b.   ( B lin d in g )   T h e  u s er   r an d o m l y   ch o o s es   * ,     q a b Z    as b lin d in g   f ac to r s .   T h e    u s er     co m p u tes     ˆ   ( ,   ) . pub U e a P b X P    2 1 2 1 ( ,   ) ,   ( )     ( ( ( ) ) ) . H I D U F M F F M M    10 [] h   .   1 m od   h b h q an d   s en d s     h    to     th e    s ig n er .   c.   ( Sig n in g )   T h e  s ig n er   s e n d s   b ac k   ID V X h d  .   d.   ( Un b lin d i n g )   T h e    u s er     co m p u tes   . pub V b V a P      T h e  u s er   o u tp u t s   ( ,   ) hV    as   th e  b li n d   s ig n at u r e  o n   th e   m es s ag e . M                 User                                               Sig n er                                                   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E     Vo l.  7 ,   No .   5 ,  Octo b er   2 0 1 7   :   2 6 7 4   –   2 6 8 2   2678                                                                           * Rq rZ                                                                                                       C o m p u te    ID X r d                                            X                * ,  Rq a b Z         C o m p u te  ˆ   ( ,   ) pub U e a P b X P    2 ( ,   ) H ID U   1 2 1 ( )     ( ( ( ) ) ) F M F F M M    10 [] h       1 m od h b h q                                                 h                                                             C o m p u te    ID V X h d                                                 V   C o m p u te    pub V b V a P      Fig u r e   1 .     T h e  b lin d   s ig n at u r e  is s u i n g   p r o to co l       4.   B lin d   Si g n at u r e  Ver i f i ca tio n   :   Giv e n     I D    an d     t h e    s i g n at u r e    ( ,   ) hV ,   an y     o n e   ca n   v er i f y   th e   s i g n at u r e   an d   r ec o v er   th e  m e s s a g e    as   f o llo w s :   a.   C o m p u te  2 ˆˆ ,   ( ,   )   ( ,   ) . p u b I D H I D e P V e P h Q    b.   C o m p u te 2 [] h    .   c.   R ec o v er   th e  m es s ag e  a s 12 2 () ll hF    .   d.   A cc ep t   ( ,   ) hV    as   a    v alid     s ig n at u r e     o n     th e    m es s a g e    () hM   if     an d     o n l y     if     2 1 ( ) . l Fh       5.   ANALY SI S   O F     T H E     P RO P O SE D    I B B SS M R   I n     th i s     s ec tio n ,     w e    p r ese n t     th e    p r o o f     o f     co r r ec tn ess ,     s ec u r it y   an d   e f f icien c y   a n al y s is     o f     t h e    p r o p o s ed     I B B SS MR sch e m e.     5 . 1 .  P r o o f   o f   Co rr ec t nes s     T h e  f o llo w i n g   eq u atio n s   g i v e  t h e  co r r ec tn ess   o f   th e  p r o p o s ed   s ch e m e.   C o n s id er       ˆ ˆ ˆ ˆ  ( ,   )    ( ,   )  =    ( ,   )    ( , )   ˆ ˆ ˆ                                               ( ,   )    ( ,   )    ( ,  )   ˆ                                               ( ,   p u b I D p u b p u b I D p u b p u b I D e P V e P h Q e P b V a P e P h Q e P b V e P a P e P h Q e P b  ˆˆ ( ) )    ( ,   )    ( ,  ) ˆ ˆ ˆ ˆ                                             =     ( ,   )    ( ,   )    ( ,   )    ( ,  ) ˆ                                               ( ,   I D p u b p u b I D I D p u b p u b I D pub X h d e P a P e P h Q e P b X e P b h d e P a P e P h Q e P a P b X   ˆˆ )    ( ,   )    ( ,  )   ˆ ˆ ˆ                                               ( ,   )    ( ,   )    ( ,  ) ˆ                                               ( ,   )                 p u b I D p u b I D p u b p u b I D p u b I D pub e P h Q e P h Q e P a P b X e P h Q e P h Q e P a P b X                                  . U       5 . 2 .  Securit y   Ana ly s is     I n   th e  f o llo w i n g ,   w e  w i ll  s h o w   t h at  p r o p o s ed   I B B SS MR  s atis f ies  all  t h e  s ec u r i t y   r eq u ir e m en ts   s ta ted   in   s ec tio n   3 . 2 .   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708       I d en tity - B a s ed   B lin d   S ig n a tu r e  S ch eme   w ith   Mes s a g e  R ec o ve r y  ( S a lo me  Ja mes )   2679   5 . 2 . 1 .     B lin dn ess   P ro pert y       I n   o r d er     to     p r o v e  th e  b lin d n e s s   p r o p er ty ,     w e    w il l   s h o w     t h at    f o r     a    g iv e n     m e s s a g e - s i g n atu r e    p air     ( ,   ,   ) M h V     an d     th e    s ig n er ’ s   v ie w     ( ,   ,   ) M h V ,   th e r e    al w a y s     e x is ts     a    u n iq u e    p air     o f     b lin d in g     f ac to r s     ,  ab    th at    m ap s     ( ,   ,   ) M h V    to     ( ,   ,   ) M h V .   Sin ce     th e    u s er     ch o o s es    th e    b lin d in g     f ac to r s     ,  ab    r an d o m l y ,     t h e    s i g n er     ca n n o t     g et     a n y     i n f o r m atio n     f r o m     h is /h er     v ie w     an d     t h e    s i g n a tu r e    s c h e m e    w ill    b e    b lin d .   Fo r   a  s ig n at u r e   ( ,   ) hV   g en er at ed   o n   a  m es s ag e M ,   d u r in g   t h e  p r o to co l,  th e  f o llo w in g   eq u atio n s   m u s t   h o ld .     ˆ   ( ,   ) pub U e a P b X P                                                                            ( 1 )     1 m od h b h q                                                ( 2 )     pub V b V a P                                                ( 3 )     I m p lies     1 m od b hh q an d         l o g ( ) m o d . P pub a V b V q      T h e    ab o v e    f o r m u la,     f o r     a    in v o l v es    th e    ellip tic    cu r v e    d is cr ete    lo g ar ith m     o f     1 ( )   V b V G     w it h     r esp ec t    to     t h e    b ase    pub P .   So   w e   ca n   u s e     pub aP    in   t h e  r est   o f   t h e  p r o o f   in s tead .   I t  is   o b v io u s   t h a t     * ,  q a b Z    ex is t s   u n iq u el y   f r o m ( 2 )     a n d     ( 3 ) .   Nex t   we  s h o w   th a t  s u ch     * ,  q a b Z    s atis f ies  E q u atio n   ( 1 )   also .     Ob v io u s l y ,   d u e  to   th e  n o n - d eg e n er ate  p r o p er ty   o f   th e  b ili n ea r   p air in g s ,   w e  h a v e       ˆ ˆ ˆ ˆ   ,       ,       ( ,   ) ,   . p u b p u b p u b p u b U e a P b X P e U P e e a P b X P P   So   w e   o n l y   n ee d   to   s h o w   th a t           a n d         ab    s atis f y     ˆ ˆ ˆ ,       ( ,   ) ,   . p u b p u b p u b e U P e e a P b X P P    C o n s id er             1 ˆˆ   ,   ,   ˆˆ     ,   ,   ˆˆ       ,   , ˆˆ       ,   ,   ˆˆ     ,   ,   ˆ ˆ ˆ       ,     ,   ,   ˆ ˆ ˆ     ,       ,   ,   ˆ   ,   pu b pu b pub I D pu b I D pu b I D pu b I D pu b I D pu b pu b pub e e aP bX P P e e V bV bX P P e e V b X hd bX P P e e V bhd P P e e V hh hd P P e e V P e hd P P e e V P e hQ P P e U P     .       T h u s ,   th e  u n iq u e  s o l u tio n s   o f   E q u atio n s   ( 2 )   an d   ( 3 )   s atis f y   E q u atio n   ( 1 ) .   Sin ce     th e    b li n d in g     f ac to r s     ar e     u n iq u e    a n d     r an d o m l y     ch o s en     d u r i n g     th e    p r o to co l,    h en ce   t h e    b lin d n ess     p r o p er t y    o f     th e    p r o p o s ed     s ch e m e    f o llo w s .     5 . 2 . 2 .     Unf o rg e a bil it y       I n   o r d er     to     p r o v e    u n f o r g ea b i lit y ,     w e    f ir s t    as s u m e     th a t    t h er e    ex i s ts     a    p r o b ab ilis tic    p o ly n o m ial     ti m e    al g o r ith m   A ,   w h ic h     ca n     cr ea te    f o r g ed     s ig n atu r e s     o f     th e    s i g n er .   W e  ca n   th e n   u s e  A   to   s o lv e  th e   C DH  ( C o m p u tatio n al   Di f f ie - Hell m a n )   p r o b le m .   A s s u m e     t h at  A   is     ab le    to     f o r g e    v a lid   b lin d     s i g n at u r es     w h ic h     ca n     b e    ac ce p ted     b y   th e    v er if ica tio n     alg o r ith m     w it h     n o n - n eg lig ib le    p r o b ab il it y .   B y     th e    Or a cle    r ep lay     attac k   an d     t h e    Fo r k in g     L e m m a  [ 1 8 ] ,   ass u m e  A    h as    co n s tr u cted     t w o     d if f er en t    v alid     b lin d     s ig n at u r es   f o r     a    m es s ag e    M .     Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E     Vo l.  7 ,   No .   5 ,  Octo b er   2 0 1 7   :   2 6 7 4   –   2 6 8 2   2680         1 1 1 2 2 2 ( ,   )       a n d     ( ,   ) h V h V       Sin ce     t h ese     t w o     v alid     b lin d     s i g n a tu r es     o b tai n ed     f r o m   th e   s a m e    r an d o m     tap e   w it h     d if f er e n t     o r ac les 1 h an d   2 . h   I t   is     ad m i s s ib le    t o     ass u m e    th at             11 ID V X h d     an d     22 ID V X h d       w h er e    12 . hh     T h u s ,   w e  h av e  1 2 2 1 ( ) ( ) ID V V h h d   an d   w e  ca n   co m p u te  ID d   as   f o llo w s     1 2 1 1 2 ( )    ( ) . ID d h h V V   B y     th e    s y s te m     i n itializat io n     alg o r ith m     o f     th e    b lin d     s ig n atu r e,   w e    ar e    ab le    to     s o lv e    an     in s ta n ce     o f     th e     C DH    p r o b le m ,   n a m e l y   g i v e n     ( ,   ,   ) I D p u b P Q a P P s P  ,   it    i s     p o s s ib le    to     co m p u t e    ID ID d s Q s a P  ,   w h ic h     i s     a     co n tr ad ictio n ,   wh ich     ar is e s     d u e    to     t h e    a s s u m p tio n     th at     A    s u cc ess f u ll y     co n s tr u cted     t w o     d if f er e n t   v al id     b lin d     s ig n at u r es   f o r     M .   Hen ce   th e  b li n d   s ig n a tu r e  is   u n f o r g ea b le.     5 . 3 .     E f f iciency   o f   t he  P ro po s ed  I B B SS M R   I n   t h is   s ec tio n ,   w e   an al y ze   th e  p er f o r m an ce   o f   o u r   I B B SS MR  s ch e m e  a n d   t h e n   w e   co m p ar e  it  w it h   th e  r el ated   s ch e m es  i n   ter m s   o f   co m p u tatio n al  an d   co m m u n icatio n a l  ( s ig n at u r e  len g th )   co s t  p o in t  o f   v ie w .     Fro m   t h e  e x p er i m e n tal  r e s u l ts   [ 1 9 ] - [ 2 1 ] ,   to   ac h iev e  t h e  co m p ar ab le  s ec u r i t y   w it h   1 0 2 4 - b it  R S A  k e y   w h er e   th e  b ili n ea r   p air in g   ( T ate  p air in g )   is   d e f in ed   o v er   t h e   s u p er s in g u lar   ellip tic  c u r v e   23 /: p E F y x x    w it h   e m b ed d in g   d e g r ee   2   an d   th e  1 6 0 - b it  So lin as  p r i m e  n u m b er   1 5 9 1 7 2 2 1 q   w it h   5 1 2 - b it  p r i m e  n u m b er   p  s atis f y in g   1 1 2 . p q r    I n   ad d itio n ,   w e  c o n s id er   th e  r u n n i n g   ti m e  c al cu lated   f o r   d i f f er e n t  cr y p to g r ap h ic   o p er atio n s   in   C ao   et  a l.  [ 1 9 ] ,   He  et  al.   [ 2 0 ] ,   R en   et  al.   [ 2 1 ]   u s in g   MI R A C L   [ 2 2 ] ,   a  s tan d ar d   cr y p to g r ap h ic   lib r ar y   a n d   i m p le m e n ted   o n   a   h ar d w ar e  p lat f o r m   P I V  ( P en tiu m - 4 )   3 GH Z   p r o ce s s o r   w i th   5 1 2 - MB   m e m o r y   an d   a  w i n d o w s   XP   o p er atin g   s y s te m .   Fu r t h er m o r e,   C h u n g   et  al.   ( 2 0 0 7 )   [ 2 3 ] ,   in d icate   th at  t h e  ti m e  n ee d ed   to   ex ec u te   th e   elli p tic  cu r v e   s ca lar   m u ltip licatio n   () EM T   is   ap p r o x i m atel y   2 9 , ML T    an d   th e  ti m e  n ee d ed   to   ex ec u te  th e  m o d u lar   ex p o n en t iatio n   () EX T   is   ap p r o x i m at el y     24 0 . ML T   I t  w as  al s o   m e n tio n ed   in   C ao   et  al.   [ 1 9 ]   an d   He  et  al.   [ 2 0 ]   th at  t h e  ti m e  n ee d ed   to   e x ec u te  o n e  p air in g   b a s ed   s ca lar   m u ltip licatio n   () EM T   is   ap p r o x i m atel y   6 . 3 8 , ms i.e   6. 38 , EM T ms   th e  ti m e  n ee d ed   to   ex ec u t e  o n e  b ilin ea r   p air in g   ( T ate   p air in g )   o p er atio n     () BP T   is   ap p r o x im a tel y   2 0 . 0 1 ms   i.e .   2 0 .0 1 BP T m s   an d   t h e  ti m e  n ee d ed   to   ex ec u te  o n e  p air in g - b ased   e x p o n en tiatio n   PX T   is   ap p r o x i m atel y   1 1 . 2 0 ms   i.e .   1 1 . 2 0 . PX T m s No w   f r o m   t h e  w o r k s   p r o p o s ed   in   B ar etto   et  al.   2 0 0 4   [ 2 4 ]   an d   T an   et  al.     2 0 1 0   [ 2 5 ] ,   13 BP EM TT   an d     1 ( 1 / 2) . PX BP TT   W e  s u m m ar ize  th e s e  co m p u ta tio n al   r esu lt s   in   T ab le  1 .       T ab le  1 .   No tatio n s   an d   d escr ip tio n s   o f   v ar io u s   cr y p to g r ap h ic  o p er atio n s   an d   th eir   co n v er s io n s   N o t a t i o n s   D e scri p t i o n s     ML T     T i me     n e e d e d     t o    e x e c u t e     t h e     mo d u l a r     m u l t i p l i c a t i o n       o p e r a t i o n   EM T     T i me     n e e d e d     t o     e x e c u t e     t h e     e l l i p t i c     c u r v e     p o i n t   mu l t i p l i c a t i o n                                               ( S c a l a r     m u l t i p l i c a t i o n     i n     1 G )   : 29 E M M L TT   BP T   T i me     n e e d e d     t o     e x e c u t e     t h e     b i l i n e a r     p a i r i n g     o p e r a t i o n     i n     2 G :  87 B P M L TT   PX T   T i me   n e e d e d   t o   e x e c u t e   t h e   p a i r i n g - b a se d   e x p o n e n t i a t i o n   o p e r a t i o n     i n     2 G :     4 3 . 5 P X M L TT                     EX T             T i me     n e e d e d     t o     e x e c u t e     mo d u l a r     e x p o n e n t i a t i o n     o p e r a t i o n   i n                                                                                       * : q Z     240 E X M L TT        IN T     T i me     n e e d e d     t o     e x e c u t e     mo d u l a r     i n v e r si o n     o p e r a t i o n     i n                                     * : q Z     1 1 . 6 I N M L TT       MT P T   T i me     n e e d e d     t o     e x e c u t e     a     ma p - to - p o i n t   ( h a s h   f u n c t i o n ) :   29 M T P E M M L T T T       PA T     T i me       n e e d e d   t o   e x e c u t e   a d d i t i o n   o f   2   e l l i p t i c   c u r v e   p o i n t s .       ( p o i n t     a d d i t i o n     i n     1 G ) :     0 . 1 2 P A M L TT     Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708       I d en tity - B a s ed   B lin d   S ig n a tu r e  S ch eme   w ith   Mes s a g e  R ec o ve r y  ( S a lo me  Ja mes )   2681     W e  an al y ze   t h e  ef f icie n c y   o f   o u r   p r o p o s ed   I B B SS MR sc h e m e  b y   co m p ar i n g   i t  w it h   th e  e x i s tin g   s ch e m es [ 1 4 ] ,   [ 1 7 ] .   T h e  co m p ar is o n   is   s u m m ar ized   in   T ab le   2 .                               T a b le  2 .    E f f icie n c y   c o m p ar is o n   o f   o u r   Sc h e m e  w it h   r elate d   s ch e m es                           Fro m   T ab le  2 ,   it  is   clea r   th at  t h e  s i g n a tu r e  le n g t h   o f   t h e  p r o p o s ed   I B B SS MR  s ch e m e  i s   1 ( ) , qG   w h ic h   is   less   t h an   Ha n   et  al.   [ 1 4 ]   s ch em e  an d   eq u al  le n g th   w i th   Hass a n   et  al.   s ch e m e  [ 1 7 ] .   A ls o ,   th e  co m p u ta tio n a l   co s t  f o r   s i g n i n g   a n d   v er if ica tio n   o f   th e  p r o p o s ed   I B B SS MR  s c h e m e  i s 4 7 5 .8 4   ML T w h ich   is   le s s   th a n     Han   et  al.   [ 1 4 ]   an d   Hass an   et  al.   [ 1 7 ]   s ch e m e s ;  an d   s o   o u r   s ch e m e  i s   co m p u ta tio n all y   m o r e  ef f icie n t  t h an   t h e   Han   et  al.   [ 1 4 ]   an d   Hass an   et  al.   [ 1 7 ]   s ch em e s .     Hen ce ,   f r o m   t h e  ab o v e  d is cu s s io n ,   th e  p r o p o s ed   I B B SS MR  s ch e m e  is   co m p u tatio n all y   an d   co m m u n icat io n all y   ef f ic ien t   th an   t h e  r elate d   s ch e m e s .       6.   CO NCLU SI O N   I n   th i s   p ap er ,   w e  p r o p o s ed   a  n e w   b li n d   s i g n at u r e  s c h e m e  w it h   m e s s a g e  r ec o v er y   i n   t h e  I D - b ased   s ettin g   u s i n g   b ilin ea r   p air in g s   o v er   ellip tic  cu r v es.  T h is   s ch e m e  co m b in es  th e  ad v a n ta g es  o f   b lin d   s ig n at u r e,   m es s ag e   r ec o v er y   w it h   I D - b ased   cr y p t o g r ap h y   a n d   p la y s   a n   i m p o r ta n t  r o le  in   cr y p to g r ap h ic  p r o to c o ls   s u c h   as  e - v o ti n g   an d   e - p a y m e n t.  T h e  B lin d n e s s   p r o p er ty   o f   o u r   s c h e m e  p r o v id es  th e  a n o n y m it y   o f   t h e   u s er   a n d   m es s a g e   r ec o v er y   p r o p er ty   p r o v id es  to   w o r k   w i th   lo w   b an d   w id t h   d ev ices   li k e  P D A s ,   m o b ile  d e v ices   etc.   A l s o   t h e   p r o p o s ed   s ch e m e  is   s ec u r e  w i th   th e  as s u m p tio n   th at  t h e  C DH  p r o b lem   is   i n tr ac tab le.   E f f icie n c y   a n al y s i s   o f   o u r   s ch e m e  w it h   o th er   s ch e m e s   s h o w s   t h at  t h e  p r o p o s ed   I B B SS MR  i s   ef f icie n t  i n   ter m s   o f   co m p u tatio n al   an d   co m m u n icatio n a l p o in t o f   v ie w .       RE F E R E NC E S    [1 ]   D.  Ch a u m ,   “ Bli n d   sig n a t u re s  f o r  u n trac e a b le  p a y m e n ts, ”   In   Pro c .   o f  CR Y PT O’8 2 ,   Ne w  Y o rk :  P len u m  Pre ss         p p . 1 9 0 - 2 0 3 ,   1 9 8 3 .       [2 ]   R.   A .   S a h o o ,   a n d   S .   P a d h y e ,   " ID - b a se d   sig n a tu re   sc h e m e   f ro m   b il in e a r  p a iri n g s:  A   s u rv e y , "   Fro n t.   El e c tr.   El e c tro n .   E n g g .   C h i n a ,   v o l.   6 (4 ),   p p .   4 8 7 - 5 0 0 ,   2 0 1 1 .   [3 ]   M . li ,   P ro v a b le  se c u re   a n d   e f f ici e n t  ID - b a se d   stro n g   d e sig n a ted   v e rif ier  sig n a tu re   sc h e m e   w it h   m e ss a g e   re c o v e r y , "   In d o n e s i a n   J o u rn a l  o f  El e c trica l  En g i n e e rin g   a n d   C o mp u ter   S c ien c e , v o l. 1 2 ,   No .   1 0 ,   p p .   7 3 4 3 - 7 3 5 2 ,   2 0 1 4 .   [4 ]     G .   S w a p n a   e t  a l.   " A n   e ff icie n t  ID - b a se d   p ro x y   sig n c r y p ti o n   sc h e m e , "   In ter n a ti o n a l  J o u rn a l   o f  Ne two rk s  S e c u rity , ,   v o l .  1 ,   n o.   3 ,   p p .   2 0 0 - 2 0 6 ,   2 0 1 2 .   [5 ]   F .   Zh a n g     a n d   K.  Kim ,   “ ID - b a se d   b li n d   sig n a t u re   a n d   ri n g   sig n a tu re   f ro m   p a iri n g s,"   AS IACR Y PT - 2 0 0 2 ,   L NCS,   v o l.   2 5 0 7 ,   p p .   5 3 3 – 5 4 7 ,   2 0 0 2 .   [6 ]   Hu a   S u n ,   " Ne w   C e r ti f ic a tele ss   B li n d   R in g   S ig n a t u re   S c h e m e , ”   T EL KOM NIKA  In d o n e sia n   J o u rn a l  o f  El e c trica l   En g i n e e rin g . ,  v o l .   1 2 ,   n o .   1 ,   p p .   7 7 8 - 7 8 3 ,   2 0 1 4 .   [7 ]   Hu a n g ,   e t  a l. ,   “ Ef f icie n t  id e n ti ty - b a se d   sig n a tu re s  a n d   b li n d   sig n a tu re s,”  CANS ’0 5 ,   L NCS   3 8 1 0 ,   S p rin g e r - Ver la g ,   p p . 1 2 0 - 1 3 3 ,   2 0 0 5 .   [8 ]   Z.   Zh a o ,   e t  a l. ,   “ A   Ne w   ID - Ba se d   Bli n d   S ig n a t u re     f ro m   Bil in e a r  P a iri n g s,”  Pro c e e d in g s  o f  t h e   ICW M M N  2 0 0 6 ,     p p . 4 0 2 - 4 0 3 ,   2 0 0 6 .   [9 ]   S .   Ka lk a n ,   e t  a l. ,   “ G e n e ra li z e d   ID - b a se d   Bli n d   S ig n a tu re s  f ro m   Bil in e a r  P a iri n g s,”  In   p ro c e e d i n g   o f  th e   2 3   In ter n a t io n a l  S y mp o si u m o n   C o m p u ter   a n d   In f o rm a ti o n   S c ien c e s ( IS CIS   2 0 0 7 ) ,   p p   4 5 - 4 8 ,   2 0 0 7 .   [1 0 ]   Z.   Zh a o ,   “   ID - Ba se d   A u th e n ti c a ted   Bli n d   S ig n a t u re   S c h e m e   f ro m   Bil in e a r  P a iri n g s,”    p r o c e e d in g s  o f   th e   In t.   Co n f.   o n   Co m p u t a ti o n a l  I n telli g e n c e   a n d   S e c u rity W o rk sh o p s ,     IE EE ,   p p .   7 2 5 - 7 2 8 ,   2 0 0 7 .   [1 1 ]   B.   U m a p ra sa d a   R a o ,   e t  a l. ,   “ A n   ID - Ba se d   Bli n d   S ig n a tu re   S c h e m e   f ro m   Bil in e a r  P a iri n g s,”  In ter n a t io n a l   J o u rn a l   o f  Co m p u ter   S c ien c e   a n d   S e c u rity .   v o l.   4   (1 ) ,   p p .   9 8 - 1 0 6 ,   2 0 1 0 .   S c h e me   S i g n a t u r e   l e n g t h   ( b i t s)   S i g n i n g   c o st   V e r i f i c a t i o n   c o st   T o t a l   c o st   H a n   e t   a l .   sch e me   [ 1 4 ]   1 2 G   6 2 1 2 EM BP I N PA T T T T   31 B P P X TT   6 6 4 . 3 4 ML T   H a ssan   e t   a l .   sch e me   [ 1 7 ]   1 qG   6 1 1 2 E M B P I N P A T T T T   21 B P P X TT   4 9 0 . 3 4 ML T   P r o p o se d   I B B S S M R   1 qG   6 1 1 2 E M B P I N P A T T T T   21 B P E M TT   4 7 5 . 8 4 ML T   Evaluation Warning : The document was created with Spire.PDF for Python.
                      I SS N :   2 0 8 8 - 8708   I J E C E     Vo l.  7 ,   No .   5 ,  Octo b er   2 0 1 7   :   2 6 7 4   –   2 6 8 2   2682   [1 2 ]   G .   X u   a n d   G .   X u ,   “ A n   ID - b a se d   Bli n d   S ig n a tu re   f ro m   Bil in e a r  P a iri n g   w it h   Un li n k a b il it y , ”   IEE E  c o n fer e n c e   o n   In fo rm a t io n   se c u rity,   p p . 1 0 1 - 1 0 4 ,   2 0 1 2 .   [1 3 ]   R.   P a n c e   a n d   A .   L ju p c h o ,   “ Co m p a riso n   o f   ID - Ba se d   Bli n d   S ig n a tu re s  f ro m   P a iri n g s  f o r  E - v o ti n g   P ro t o c o ls, ”   M IPR O 2 0 1 4 ,   O p a ti ja,  Cr o a ti a   p p . 2 6 - 3 0 ,   2 0 1 4 .   [1 4 ]   S .   Ha n ,   a n d   E .   Ch a n g ,   “ A   P a iri n g - Ba se d   Bli n d   S ig n a tu re   S c h e m e   w it h   M e ss a g e   Re c o v e r y , ”   In ter n a ti o n a l  J o u rn a l  o f  In fo rm a t io n   T e c h n o l o g y ,   v o l.   2   (4 ),   2 0 0 5 .   [1 5 ]   J.  W a n g   a n d   H.  Qia n ,   “ A n   Op ti m a l  Bli n d   S ig n a tu re   P a d d i n g   w it h   M e ss a g e   Re c o v e r y , ”   Fi ft h   In ter n a t io n a l   Co n fer e n c e   o n   In f o rm a ti o n   Assu r a n c e   a n d   S e c u rity ,   2 0 0 9 .   [1 6 ]   J.  S .   Z h a n g ,   “ A   Kin d   o f   M e ss a g e - Re c o v e ra b le  F a irn e ss   Bli n d   Dig it a l  S ig n a tu re   S c h e m e , ”   Pro c e e d ia    En g i n e e rin g   v o l. 1 5 ,   p p .   2 1 0 3 - 2 1 0 7 ,   2 0 1 1 .   [1 7 ]   E.   Ha ss a n   a n d   A .   Ya s m in e ,   “ A  Ne w   Bli n d   Id e n ti ty -   Ba se d   S ig n a tu re   S c h e m e   w it h   M e ss a g e   R e c o v e r y , ”   T h e   On li n e   J o u rn a l  o f  El e c tro n ics   a n d   El e c trica l  E n g in e e rin g   ( OJ EE E) ,   v o l. 2   (2 ),   2 0 0 6 .   [1 8 ]   D.  P o i n tch e v a l  a n d   J.  S ter n ,   “ S e c u rit y   a r g u m e n ts  f o r  d ig it a l  sig n a tu re s  a n d   b li n d   sig n a tu re s, ”   J o u rn a l  o f  Cry p to lo g y ,   v o l.   1 3 (3 ) ,   p p . 3 6 1 - 3 9 6 ,   2 0 0 0 .   [1 9 ]   X .   Ca o ,   e t  a l. ,   “ A  p a iri n g - fre e   id e n ti ty - b a se d   a u th e n t ica ted   k e y   a g re e me n t  p ro t o c o l   wit h   min i ma l  me ss a g e   e x c h a n g e s ,”   In fo rm a ti o n   S c ien c e s ,   v o l.   1 8 0 (1 5 ),   p p .   2 8 9 5 - 2 9 0 3 ,   2 0 1 0 .   [2 0 ]   D.  He ,   e t  a l. ,   “ A n   ID - b a se d   p r o x y   sig n a tu re   sc h e m e   w it h o u t  b il i n e a r   p a iri n g s, ”     An n .  o f    T e lec o mm u n ica ti o n ,     v o l .   66 ,   p p .   6 5 7 – 6 6 2 ,   2 0 1 1 .   [2 1 ]   K.  Re n ,   e t  a l. ,   “ On   b r o a d c a st  a u th e n ti c a ti o n   in   w irele ss   se n so r  n e tw o rk s,”  IEE E  T ra n sa c ti o n   o n   W ire les s   Co mm u n ica ti o n ,   v o l .   6 ( 1 1 ) ,   p p .   4 1 3 6 – 4 1 4 4 ,   2 0 0 7 .   [2 2 ]   S h a m u s S o f twa re   L td .   M irac l  L ib ra r y .   Av a il a b le:  h tt p :/ /ce rti v o x . o r g /d isp lay /E X T /M IRA C L .     [2 3 ]   Y.  F .   Ch u n g ,   e t  a l . ,   “ ID - b a se d   d ig it a l  sig n a tu re   s c h e m e   o n   th e   e ll ip ti c   c u rv e   c r y p to s y ste m , ”   Co m p u ter   S ta n d a rd s   a n d   In terf a c e s,  v o l.   2 9 ( 6 ),   p p .   6 0 1 - 6 0 4 ,   2 0 0 7 .   [2 4 ]   P .   S .   L .   M .   Ba rre to ,   e t  a l. ,   “ Ef fi c ien t  a n d   p ro v a b ly - se c u re   id e n ti ty - b a se d   sig n a tu re s  a n d   sig n c ry p ti o n   fro m   b il in e a r ma p s,”   I n   Pro c .   o f   AS IA CRY PT ’0 5 ,   v o l.   3 7 7 8   o f  L NCS ,   p p .   5 1 5 - 5 3 2 ,     2 0 0 5 .   [2 5 ]   S .   H .   T a n ,   e t  a l . ,   “ Ja v a   Im p le m e n tatio n   f o r  P a ir in g - Ba se d   Cr y p to s y ste m s,”  Pro c .   o f  t h e   In t.   Co n fer e n c e   in   Co mp u t a ti o n a l  S c ien c e   a n d   Its  A p p li c a ti o n s  ( ICCS A ' 1 0 ),   L NCS  6 0 1 9 ,   p p .   1 8 8 - 1 9 8 ,   2 0 1 0 .         Evaluation Warning : The document was created with Spire.PDF for Python.