TELKOM NIKA Indonesia n  Journal of  Electrical En gineering   Vol. 12, No. 10, Octobe r 20 14, pp. 7523  ~ 753 2   DOI: 10.115 9 1 /telkomni ka. v 12i8.594 9          7523     Re cei v ed Ma rch 1 0 , 2014;  Re vised July   30, 2014; Accepted Augu st  20, 2014   Study on Commitment Schemes of Secure Multi-party  Computation      Xiaoqiang G uo, Yan Yan, Cuiling Luo, Shuai Zhan g   Coll eg e of Scie nce, Heb e i Un i t ed Univ ersit y ,    No.46  Xi nh ua  W e st Street,  Tangs ha n 063 0 09, Heb e i Prov ince, Ch ina   Corresp on din g  author, e-mai l : guo xi ao qia n g @ he uu.ed u.cn,  guo xq 20 04@ 1 63.com       A b st r a ct    T he pro b le m  o f  secure  multi- party co mp utation (S MPC)  is one  of the mos t  funda me ntal  prob le ms   in infor m ation  security. F i rst,  w e  introduce t he bas ic  conc ept of SMPC and four  SMPC  basic agr ee ment:   key distri butio n, obl ivio us tra n sfer, bit co mmit me nt  an d  zero kn ow led g e  proof. Sec o n d ly, w e  separ a t ely   illustrat e  co mmit me nt sch e m es  co mmit ment transfe r  protoco l ,  co mmit me nt  sh ari ng protoco l  and   commitment  multipl i cati on  pro t ocol. F i n a lly,   w e  prese n t  u n c ond ition a lly  se cure  multi-p a rty co mp utatio n  w i th   a passiv e  adv e r sary, an active  adversary, ge nera l  advers a r y  structures.    Ke y w ords :   secure   multi- p a rty co mp utati on, i n for m atio n   security, c o mmit me nt sch e m e, v e rifi abl e  secret  shari n g     Co p y rig h t   ©  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.  Introducti on  Secu re multi-party com put ati on (SMPC)) is  a su bfield of crypto grap hy. The  goal of   method s for  se cure multi-party com put ation is to  en able pa rties t o  jointly com pute a functi on   over their in puts, whil e a t  the same time ke e p ing  these inp u ts private. Fo r example, two   millionaires can  comp ute  whi c h o ne i s   rich er, b u t wi t hout revealin g their net  worth. In fa ct, the  example was initially sugg ested by And r ew  C.  Yao in  1982 [1].  And it was la ter name d  the  millionaire problem.   The co ncept is impo rtant in  the field of cryp tograp hy and is cl osely related to the idea of   zero-kn o wl ed gene ss. In general it refe rs  to computatio nal system s i n  whi c h multi p le partie s  wi sh  to jointly compute som e  value ba sed o n  individua lly  held se cret bits of  inform ation, but do not  wish to reve al their se cre t s to one an other in  the pro c e ss. Fo r example, two  individuals  who  each  p o sse s s som e  se cret  inform atio n  x  and  y , r e spec tively may w i sh to jointly c o mpute  s o me func tion  (, ) f xy  without re vealing any informatio n a bout  x  and  y other than what can   be rea s on abl y dedu ced  by  kn owin g the  actual val ue  of  (, ) f xy , whe r e " r e a so nably d e d u ce d" is  often interp re ted as eq uivalent to compu t ation  within polynomial time. The primary motivation f o r  studying m e thods of secure   computation is to de si gn system s that  allo w for maximum utility of  informatio n without comp ro mising u s e r  p r ivacy.  Secu re comp utation wa s formally intro d u ce d  by A. Yao in 198 2  as secure two-pa rty  comp utation.   The million a i r e p r oble m  a nd its  solutio n  gave way to a gene rali zation to m u l t i-party  proto c ol s [2]. In an MPC,  a given nu mber  of parti cipa nts  12 ,, , n p pp  each have a p r i v ate   data, re spe c ti vely  12 ,, , n dd d . The pa rticipant s wa nt to compute t he value of a  publi c  functio n   F  on   N  variable s  at  the  poin t   12 (, , , ) n dd d .  An MPC proto c ol is d ubbe d se cu re if no   partici pant ca n learn mo re  from the de scription of  the publi c  functio n  and the re sult of the global  cal c ulatio n than what he o r  she  can lea r n from  hi s or her own entry  under parti cula r co nditio n s  depe nding o n  the model used.  Like  many  cryptograp hic p r otocols, th e  se curity  of  an  MPC  proto c ol can  rely o n  different  as sumpt i o n s:   It can be co mputational (i.e. based on  some mathe m atical probl em, like fact oring )  or  uncondition al  (usu ally with some p r o babi lity of error which  can b e  made a r bitra r ily small).   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:  752 3  – 7532   7524 The m odel i n  which  the  scheme  is d e scrib ed  mig h t assum e  th at parti cipa nts u s e  a   synchro n ized   network (a m e ssag e sent   at a "tick" al ways a rrive s  at  the n e xt "tick"), that a  se cure   and reli able  broa dcast ch annel exist s , that a se cure commu nica tion chan nel  exists betwe en   every pai r  of parti cipa nts (an  adve r sa ry ca nnot  re ad, modify o r  ge ne rate  messag es in  the   cha nnel ), etc.  The centrally controlled  ad versa r y con s i dere d  can b e  passive (onl y allowe d to read the  data of a  ce rtain nu mbe r  of parti cipa n t s) o r  a c tive (ca n  corrupt the  ex ecutio n protocol or a   certai n num b e r of parti cipa nts).   An adve r sa ry can  be  st atic (ch o o s e s  its vi ctims before the   start of th e  multi-pa rty  comp utation )  or dynami c  (can ch oo se its victims dur i n g the cou r se of execution  of the multiparty  comp utation ) . Attaining security again s t a dynamic  ad versa r y is often much harder than  se cu rity  again s t a stat ic adversa ry.  An adversary  can be d e fin ed as a thre shol d  stru ctu r e (mea ning t hat it can co rrupt or   simply re ad the memo ry of a number of  particip ants  up to some t h re shol d), or  be define d  a s  a  more  com p le x structu r e (i t can affect  certai n prede fined su bsets of parti cip ants, mod e li ng  different po ssible collu sio n s). Th ese stru ct ures a r e commo nly referred to  as adversa ry  structures. T he  oppo site set consi s ting  of  the sets  of  honest parties that  can  still execute  a  comp utationa l task is  relate d to the con c ept of access stru cture s .   Un con d itional ly or info rmat ion-the o retica lly SMPC is  clo s ely relate d to the  prob lem of  se cret  sha r in g, and m o re  spe c ifically verifiable  se cret sha r ing  (V SS); many SMPC p r oto c ol s that  protect against active  adversaries use VSS.  Performi ng a   comp utation  usin g MPC p r otocols  is stil l  ord e r of  ma gnitude s slo w er  tha n   perfo rming t he co mputati on usi ng a t r uste d third  party. Ho wev e r, more an d more  effici ent  proto c ol s fo r  MPC h a ve  b een  propo se d, and  MP C  can  be  no w  use d  a s  a  practical  solutio n  to  variou s real -life pro b lem s   su ch a s   distributed  voting,  private bi ddi ng an d a u cti ons,  sha r in g  of  sign ature  or  decryption fu nction s, p r iva t e inform atio n retri e val, e t c. The first l a rge - scale a nd  pra c tical  ap p lication  of m u ltiparty com putati on too k  place in  De nmark in  Ja nuary  200 8, as  descri bed by  Bogetoft et al. [3].      2. SMPC Un derly i ng Protocol   In this  section we m a inly disscuss  t he  follo win g  four  SMP C  basi c  agree ment:  key  distrib u tion, o b livious tra n sf er, bit commit m ent and zero kno w le dge  proof.     2.1. Ke y  Distribution    For the  peo pl e eng age d in  the field of seure  multi-p a r ty comp utation an d cryptogra phy,  key di strib u tion i s  the  mo st basi c   agree men. Its  m a in  goal  is to m a ke  di screte  comm unij c ati ons  se cur e ly  sh ar e st rin g  (u su ally  set  t o  binary  bit   stri n g ) to prepa re  for the future use  of se cret  comm uni cati on tasks. We kno w  that, in the  classic enviro n me nt, the bigge st enemy is  not  cha nnel  noi se, but  a p o te ntial eave s d r oppe r. If  t he eavesdro ppe r mastere d  bo th sides of the   legitimate co mmuni cation  key, in  sub s eq uent com m unication, he  can  ille g a lly  eavesdropp  se cret s, forg ed identity and eng age in  other act s . In the cla ssi c environm ent , eavesdropp ing    can n o t be avoided in a certain extent. Howeve r, in  quantum en vironme n t, accordi ng to the  uncertainty p r inci ple an d  no-cloni ng th eore m   of qu antum, eave s droppi ng de tection be co mes  fairly eas y [4].    Public  key cryptograp hy is the basi c  of  key  dist ributio n. S. Goldwa sser a nd S. Micali p u t  forwa r d the first pro babili stic pubic  key  encry ptio n schem e[5], ca lled Gold wa sser-Mi c ali ( G M )   scheme. GM  sch eme i s  a dditively homomorphi c.  I t s  sec u rit y  is b a se d on Q u a d rat i c  Re sidu e   ass u mption.   is th e me ssage  extensi o n rate  of the  en cryption  a l gorithm,a nd  2 lo g N ,  whe r e se cu rity  param eter  Np q . The bit  co mplexity of the cryptog r a phic  ope ratio n  on th e   messag e  m  is  2 2 (( l o g ) ) Om N , s o  GM enc r y p tion s y s t em is  ineffic i ent.  T. ElGamal proposed homomorphi c probabilisti c cryptosystem  [6]. It is multi p licaivaly   homom orp h ic to realize secu re multip arty multip lication of the  encrypted da ta. Its securit y  is  based o n  De cisi on  Diffie-Hellma n  a s su mption. Its  sh ortco m ing i s  t hat me ssage  expan sion  rate   of the  en cryp tion sch e me   on the  finite f i eld i s  treme ndou s, to  a c hieve p r a c tical security, la rge  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Study on Co mm itm ent Schem es of Secure  Multi-pa rty Com putat io n (Xiaoqi ang  Guo)  7525 prime numb e r   p  needs at le ast 30 0 de ci mal digits, its  bits len g th  p  at least 1 024, a nd at lea s t  there shoul d be a larg e pri m e factor of  1 p .   J. Benalo h  p r opo se d hom omorphi c de nse  pro babili stic e n cryptio n  schem e [7 ]. It is   extensio n of  the GM  prog ram,  simila r t o  the  GM  progra m , al so  additively ho momorphi c. I t s  se curity is ba sed o n  the Hi gh-d e g r ee Resid u o s ity problem, me ssage expan sio n  rate  clo s e t o   1.   P. Paillier propo sed  hom omorphi c pro babili stic  pu b lic key en cry p tion algo rith m [8],  whi c h i s  a ddit i vely homom orphi c. Its  se curity i s  b a se d on th e  De cision al Comp osite  Re sidu o s ity  assumptio n , messag e exp ansi on rate  is a c o ns tant.      2.2. Obliv i ou s Trans f er   The  obliviou s  tran sfer  m ean s the  re cipient   can  g e t their want  me ssage s f r om th e   sen der's  se cret messag e set but you ca n not  get the other me ssag e, and the se nder  do se no t  kno w  the  re cipie n t ch oo se whi c h  me ssag es. O b livious t r an sfer  is an i m po rtant co ncept  in  mode rn  crypt ogra phy. No w it wi dely i s  u s ed  to b u ild zero-kno wled ge p r oof , verified secret  sha r ing p r oto c ol  etc. The  obliviou s  tran sfer a nd bit commitment to gether  con s titute the basi s   of    se cure multi-party co mput ations. It is a  hot sp ot of   rese arch in th e field of info rmation  se cu rity.  An intere stin g appli c ation  called the  secret all-o r -n one lea k , ref e rs to  su ch  a se cret learning   t a sk:  t h e  o w n e r of   sev e ral  se cret s A lic e  woul d lik e to  sell  any of h e r  se cret s to  Bob, Bob p a y  money to  get  a  se cret wha t  he  want s  (that is he   kne w  n o thing  ab out the  othe r  se cret ), an d  ask  Alice ca n not kno w  Bob pu rcha se  whi c h  se cret.              The  con c e p tion of o b liviou s  tra n sfe r   wa s p r op osed  b y  Rabin  in [9] .  Even, Goldreich  and   Lempel  ha d  given  2 1    -OT i n   [10]. And  Cre peau  ha d p r o v en the  equi valance Even ’s  2 1    -OT   and Rabin’ s  OT in [11]. Then Bra s sard , Crep eau a n d  Rob e rt ha d  given AN-DOS and GO T   in   [12,13]. Cach in had con s tructed  UOT in  [14].       2.3. Bit Com m itment  Consider  such a scene: Alice cl aimed t hat  she  has some  predicti ve capability, but Bob  is skepti c al. In ord e r to m a ke Bo b to convince  her  predi ctive abi lity, A lice decided to sh ow her  the predi ctive ability for th e upcoming a soccer  game. How to make Bob believe her predi ctive  power? In  cl assic environment, th is problem  can  be easily  solv ed. Before the game, Alice will  predi ct the score to written  on a small p i ece of  pa pe r, then hand to Bob. After the game, Bo b  contrast to  th e note  on th e  score of th e  game to   dete r mine  the p r e d ictive  capa bi lity Alice re ally  has  claime d. The co re of  this exampl e is Alic e in  somethin g  of a prior  cl aiming a s sertion,  afterwa r d s , she could  not  deny the a ssertion.  With o u t loss of ge n e rality Alice’ s assertio n a s   one   bit, such SM PC model i s  the bit commit m ent. The co nce p tion of bi t commitment  was p r op ose d   by M.Blum. Bit commitm ent schem e can b e  u s ed  to build up  zero kno w led ge proof, verified   se cret  shari n g, coi n s throwin g  et c.  A bit commi tment sch e m e  mu st m e e t  the follo wi ng   prop ertie s :   Corre c t: if Ali c e and Bob a ll honestly executiv e ag ree m ent, then Bob will pro perly gain a  bit Alice com m itment in re veal stage.   Confid entiality: Bob cannot  learn the bit in commitme n t  stage.  Binding: in the end of com m itment stag e Bob  can g e t  the only bit in reveal sta g e .     The first mo d e l wa s propo sed by A. C. Y ao [15], even though Ya o  has not em p hasi z e d   the gene ralitty of the model, but the model was ev a l uated a s  " re ally applies t o  any actual  both   se cure comp utation ". No w we call ed  Yao mod e l. Hoi-K w o ng L o  and  H. E. Cha u  propo sed L C   model i n  [16] . They mad e  two  cha nge s to Yao mo d e l. First,  the  initial state  set to pure  state   from mixed  state in Yao   model. Se co nd, in m odel   Yao, in e a ch  rou nd  com m unication d o   two   things: me asurem ent and  unitary tran sform a tion,  b u t measure m en is d e leted ,  only a unitary  transformation in  LC model. This sim p lification is  hel p f ul for th e a n a lysis of u n co ndion al  se curity  existen c e or  not. It greatly  simplif ie s the certification p r ocess.     2.4. Zero Kn o w l e dge Pro o f  Many  mo re complex se cu re  multi-party comp utation  t a sks  ne ed ze ro kno w le dge   pro o f,  su ch a s  ident ity authentica t ion, si gnatu r e, etc. Consi der a sce ne: Alice sai d  to Bob “ I know  the   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:  752 3  – 7532   7526 mathemati c al  proof of the  theore m ”. Bo b expre s sed  doubt ag ain.  Alice wanted  Bob to belie ve   that she did know the meth ods of  proof of the theore m , but not le t  Bob kno w  proof pro c e ss.  Say  simply, zero kno w le dge proof purp o se is that make   verifier believ e  prover  who  really maste r ed   this kn owl edg e unde r the p r emi s e not le akin g.  The e a rlie st  Gold wa sser  prop osed the  con c e p t of zero  kno w led ge proof [17] . After  verifier parti cipated  i n   the   pro c e s s of zero kno w le dge pro o f,  a n y  inform atio n  that can  be   cal c ulate d  in  polynomial  time, also ca n be  cal c ulat ed ind epe nd ently by verifier in  polyno m ial  time, as long  as he beli e ve s the authenti c ity of t he propositio n. The definition of zero kno w led g e   proof sy stem s mainly consider two  different probabilit y distribution:    a)  Finish ed  with  proof of int e ra ction,  the  prob ability distrib u tion g enerated by  the   polynomial ti me verifier.   b)  A proba bilisti c polyno m ial  time autom ata gene rate d the pro b a b ility distribut ion   based on the  premi s e to be  prov en p r op osition  corre c tness.   The re sultin g three differen t  levels of zero kno w le dge  proof sy stem s:  a)  Perfect  zero  kno w le dge: i n  this sy stem  in  the    ab ove two di stri bution compl e tely  identical.  b)  Cal c ulation  zero  kn owl edg e: in this sy st em the t w o  d i stributio ns in  polynomi a l ti me  indistinguishability, that is  the two dist ributio ns can not be separated from the test of any  probabili stic polynomial tim e .   c)  Statistical  zero kn owl edge:  in this  syste m  the two  distribution  clo s e to the stati s tical  cha r a c teri stics, namely the  statistical diff eren ce b e twe en the two ca n be negl ecte d.      3. C o mmit m ent  Scheme  A commitme n t scheme, fo r an adve r sary struct u r e, is a schem e that allows a pl ayer  i p   to commit to  a value a whi l e kee p ing th e value hid d e n  in the presence of an  -a dversary an d  also  bin d ing   i p to the val ue i n  such a  way that when  h e  in  a late r  st age  de cide s t o  reveal the   value, only the value a will  be ac ce pted  among the ot her playe r s.  For  com putat ionally SMPC, we  can use a VSS  scheme for unconditi onally or perfectly  information. We will use a commitment  schem e devised by Cramer et al. in [18].  Commitme n t scheme:   a) COMMIT ( s ): Commitment al lows a player  to commit to a value  s .  b) CTP( , sj ): Co m m itment tran sfer  proto c ol  allows a  player  i p to trans fer a  c o mmitment of  s  to player  j p .  c )  CSP( s ): Com m itment sh ari ng pr otocol al lows a playe r   i p to c onvert a c o mmitment   to  s  into a  set  of com m itments o n  the  share s   of  12 (, , , ) n ss s s . In other  wo rd s, each playe r   j p will be commi tted to his share  j s  .  d)  CMP: Commi tment multiplication p r oto c ol allows a pl ayer  i p  who i s  committed to  , ab  and  ca b  to prove  to the other players that  c  is inde ed eq u a l to  ab .  e) OPEN( s ): Op en reve als  a commitm e n t, i.e.,  the value is revealed to  all  partici pant s. Only the co rrect value, the  one  D com m ite d  to, is accep t ed by the honest playe r s.   The co mmitm ent scheme i s  also homo m orp h ic, that  is given two commitme n ts  a C  and   b C  each pl ayer  can  comp ute non-i n teractiv ely the comm itment  ab C  and  ab C .   In order for a  deal er  D  to  commit to a value  s , he  co u l d sim p ly sha r e  s  amo ng th e   players. Thi s   woul d work if  we  coul d gu arente e  that  D  wa s ho ne st, but if  D  wa s corrupt, he  coul d send i n co nsi s tent  share s  to the  differ ent pla y ers. To  avo i d this, we  must force  D to   d i s t r i bu te  c ons is ten t  s h ar es :  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Study on Co mm itm ent Schem es of Secure  Multi-pa rty Com putat io n (Xiaoqi ang  Guo)  7527 a)  D  choo se s a s y mmet r ic  ma t r ix   mm R  at rando m and sets  1, 1 R  to  s . For each row   i v  belongi ng to   i p ,  D  send s the  vector  i T iv uR  to  i p . The first el eme n t of  i u  is  i s ,  i p ’s share in  s .  b)  i p  sen d s t o  ea c h   j p the value   , ij j i sv u  .  j p  comp ares th e  re ceived val ue with  , ij vu   and bro a d c a s ts the me ssage fail  (, ) ij  if they are not equ al.  c )   If a fail (, ) ij  is received,  D  broad ca sts the  val ue  ij s . If any of the playe r s f a il to   agre e  that the value  ij s  is co rre ct, they broad ca st an a c cusation tha t   D  is  c o rrupt.  d) Say  j p  ac cuses  D  of  co rruptio n.  D   can  di spro ve the a c cu sation by  broa dca s ting   the informatio n sent to  j p  in step i).  e)  Each pl ayer  checks the val ues b r o a d c a s ted by  D  to see  if they are co nsi s tent with   the values th ey have rece ived. If they   are not he send s an accusatio n  that  D  is  c o rrupt. By t he  2 Q  property of the adver sary structure,  the protocol  will only be  reje cted  if at  lea s t on e  of the  hone st  pl ayers  sen d s  a n  a c cu sat i on. Li ke wise , the   protocol will be accepted if  all the accusi ng  players are in  .  Commitment Trans f er Pr otocol : A  co mmitment tra n sfer protoco l  allows a  pla y er  i p ,  who ha s a c o mmitment to  s  to transfer the com m itment to a player  j p  . If   j p  and  i p  are   hone st, the proto c ol lea k s no informa t ion to the adversary.  j p  learn s  the value  s  in the   p r oc es s .   1)  i p  sec u rely   s end s  j p  all the i n formatio n h e  use d  to cre a te a co mmitment  C  to  s .  This includes  s .  2) j p  create s  a new  commit m ent  C  to  s  usi ng the inform ation re ceive d  in step 1 a n d   c h eck s   w h e t he r  o r  no t  0 CC  .  If any of the   above  step s f a il,  i p or  j p   must be co rru pt.  T o   di sp rove hi s co rru ption,  i p can o pen s .  Commitment Sharing Protocol : A com m itment sha r i ng proto c ol i s  a proto c ol that  allows a play er  i p  c o mmitted to a value  s t o  se cret   sha r e  12 (, , , ) n ss s s   so that ea ch  player  j p  is  c o mmitted to the s hare  j s . To acc o mplis h  this ,  i p , already committe d to  s , generat es a  rand om vecto r   R  of  size  1 m and  commit s  to each valu e in R. Usi ng CTP ,   i p  tran sfers the  c o mmitment of  j s to  j p  and he n c e  j p  also learn s   j s . Since  j s  is a result of linear operation  on the previo usly com m itted values,  j p  can che c k that  j s  is inde ed a share of  s .  Commitment Multiplicati on Protocol : A commitment multiplicat ion p r oto c ol  a llows a   player  com m i tted to the val ues  a ,  b  an d  ca b  to convin ce  the  other playe r s that  ab c .  If  the scheme i s  st rongly multiplic ative, the CMP  will be perfectly  secure. Otherwi s e it will  have a  negligibl e  error probability  .  CMP with negligible error:   1)  i p  ha s al re ady committed to th e va lues a ,  b  an d  ca b . We’ll  de not e tho s e   c o mmitments  a C ,  b C  and  c C . In o r der to  convin ce th e  other  players th at  c  is indeed equal to   ab ,  i p  choo se s a  rand om   and cre a tes th e commitment  C  and an othe r commitme n t for  the value  , we will call it  C  .  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:  752 3  – 7532   7528 2) T he oth e r players g e n e rate  a rand om challe ng e  {0 , 1 } r  using  the  app rop r iate   proto c ol s.  3)  i p  open s the  commitm ent  a rC C , which revea l s the valu e  1 rr a  , and h e   also o pen s a  commitme n t to  1 bc rC C r C  , which  sho u ld reveal 0 .   If  i p  is  hon est, then all th e op ened val u e s   are  either  ra n dom o r  0. If  i p  can an swer  t w o   different ra n dom ch allen ges  corre c tly, then  ab c  with an error p r obability of  1 2  . This   prob ability ca n be red u ced  by iterating  the pro c e s s u n til the desired pro bability    is reached   [19].  CMP with z e r o  err o r:   1)  i p has co mmi tted to three value s   a ,  b  and  c .  2) Using  CSP,  i p create s   and distrib u tes sh are s   of  a ,  b  and  c . Each player  j p   receives the  sha r e s   j a ,  j b  and  jj j ca b  and is comm itted to them.  3) Since  i p  is committed, we  kno w  that the sha r e s  of  a ,  b  and  c are con s iste nt  and   (0 ) a f a ,  (0 ) b f b  and  (0 ) c f c  where  deg( ) a f t ,  deg( ) b f t , and  deg( ) 2 c f t .  Each pl ayer  che c ks  wh eth e r o r  not hi s  sha r e s  comp ute  ii i ca b and bro a dca s ts an  a c cu sation  if this  fails .  In orde r to have a CMP with ze ro e r ror the secret  sha r ing sch e mes m u st b e  stro ngly   multiplicative.  That is,  3 n t . That mean s tha t  there are at  least  nt  honest players in t he  scheme. A n d  sin c e  2 nt t  , w her e   2 t  is  also the maximu m  deg ree  of  c f , the ho ne s t   players  can   alway s   corre c tly re con s truct the  poly nomial if  ca b . If  ca b , at lea s t o ne  hone st player, in addition to the co rru pt players, woul d have to accuse  i p .  This p r oto c ol  can  also be g eneralised to  work fo r any  se cret  sha r in g schem e wit h  a  3 Q   adversa ry structure, pr ovid ed that the scheme is  reali s ed  wi th a strongly multipli cative MSP.  Open reveal s a commitme n t. To open a  commitment  on s, the dea ler  D  broa dcasts s   and all th e sh are s  of  12 {, , , } n ss s s . If th e numb e r  of players that a g ree to t he b r oad ca sted  values of  s  and  i s  is greater t han the set o f  play ers fro m  the adversary stru cture   ,  then the  openi ng of  s  is accepted.       4. Uncondi tionally  Secure Multi-par t y  Computatio n  First, we def ine the ne ce ssary a r ithm etic  ope ratio n s for  com p utation in a  passive  adversa ry ca se.  Com puta t ions i n  a n   a c tive adv e r sa ry setting  will  be  add re ssed late r i n  th is   se ct ion.   Thre sh old  scheme s  u s ed  to se curely compute a fu nction  f  with  a pa ssive  st atic o r   adaptive adv ersary  can o n ly comp ute a  function se curely  if  2 n t . For a stati c  or  adaptive   active a d versary  where  a  bro a d c a s t  chan nel   doe s n o t e x ist, the b o und i s   3 n t .   Un con d itional ly Secure Mul t i-party Comp utat ion 36 m u ltiplicative thresh old fun c ti on is  2 Q  ( 3 Q ).  This lea d s u s  to a more ge neral p r oto c ol  for multi-pa rty computatio n:  1)  We can comp ute any functi on with a pa ss ive adversa ry structu r e p r ovided that o u r  secret sharing  scheme  i s  resilient to a  2 Q  adversa ry  structure.  Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Study on Co mm itm ent Schem es of Secure  Multi-pa rty Com putat io n (Xiaoqi ang  Guo)  7529 2)  To com pute a  function f in the pre s e n ce of an active a d versary ou r adversa ry  stru cture mu st be  3 Q .  4.1. SMPC  w i th a Passiv e  Adv e rsar y   Given two in stan ce s of S hamir ’ s  se cr e t   sha r ing   s c h e me,   t he part i cipa nt s can  comp ut e  the addition o f   secret simp ly by adding the sh ar e s  of one in stan ce  to  their co rre spondi ng shares  in the other in stan ce.     2 1 , 1 2, 1 1 , 2 2,2 1 , 2 , 12 () ( ) ( ) nn f fs s s s s s ss       Multiplicatio n  of a con s tant  c  ca n be  comp uted by h a vin g  ea ch  pa rtici pant  i p  com pute   ii cs c  . The resulting sha r e s   12 ,, , n cc c  determi ne  sc . Multiplication is a  bit more  compli cate d as the multip lication of two polynom ial s  wo uld re su lt in a new polynomial  with   degree of at most  12 de g( ) d e g ( ) 2 f ft   and the coefficie n ts o f  the new pol ynomial wo ul d not   be ran domly  distrib u ted. T o  solve this p r oble m ,  we p e rform  a sa ni ty operation,  a re sha r e, after   every multiplication that  re duces the de gree of  12 f f  and add s uniformly random val ues to al l   coeffici ents i n   12 f f , except fo r first coeffici ents  of ea ch  polynomi a l,  ie, the  se cret. We  will   illustrate how to perform  multip lication of two  polynomial s  gene rated using Shamir’ s   secret   sha r ing  sche me with an e x ample.  Example .  G i ven two  valu es  a  a nd  b , we  ca n  se cu rel y  com pute th e value   ca b   with a pa ssiv e  adversa ry by  executing the followi ng steps:   1) Sha r e  a  to  12 ,, , n aa a  and  b  to  12 ,, , n bb b  su ch that  i p  re ceiv es  sha r e s   i a   and  i b ;  2) Each playe r   i p  then com p u t es the produ ct of his two share s ,  ii i ca b ;  3) Ea ch pl ayer  i p  then sha r es  i c to  ,1 , 2 , ,, , ii i n cc c  and  sen d s th e sh are s  to thei r   respe c tive players;   4) Ea ch  play er  j p  ca n no w  comp ute the   value  j c  usin g  the value s   re ceived  and  the   recombi natio n vector.     1 1 , 1 2 ,1 ,1 1 1, 2 2 , 2 , 2 2 2 1, 2 , , n n nn n n n n c cc c r cc c r c cc c r c                           5) The  sha r e s   12 ,, , n cc c   determi ne  ca b   compl e ting the multiplication.  Usi ng the s e primitives, we can no w e v aluate an arithmetic ci rcu i t  C  over a field  F   comp uting a f unctio n   f  su ch  that when th e circuit  com p letes, e a ch  player  will ha ve a sha r e o f   the resulting  comp utation.   Theorem  ([2 0 ]). There e x ists functio n s  that can n o t  be securel y  computed  with a  passive adve r sa ry if the adversa ry struct ure is n o t at least  2 Q .   Proof. Con s i der for  exam ple the  OR -funct i on between  two playe r s.  It is easy to see  that this fun c t i on can  never be  co m puted  by the two p a rticip ants,   e a ch  providing  one  bit, with out  one of them leaki ng inform ation.  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:  752 3  – 7532   7530 Conve r sely, we can com pute any function  f  secu rely with a  passive adv ersary  provide d  that  the adve r sary  stru cture is at lea s t  2 Q . To prove this , it  is   s u ffic i ent to s h ow that  given thre e value s   ,, ab c F , we ca n alway s  securely comput e  ,, ab c a a b  [21]. This  was   sho w n in the  above examp l e.     4.2. SMPC  w i th an Ac tiv e  Adv e rsar y   In orde r to safely comp ute a functio n  f on a set of values  whe r e  we have  a  static o r   adaptive a c ti ve adversa ry we  req u ire  a  method th at  allows the  pa rticipa n ts to  check  wheth e r a  player is exe c uting the p r otocol  corre c t l y and pr ovidi ng valid sha r es. In other  words, we ne ed a   stronger prim itive that allows pl ayers to commi t to a value. To achi eve this,  we will use  the   commitme n t scheme d e scribed in thi s  Section.    Usi ng thi s   schem e, we  can no w  co nstruct a  information the o retic  SMP C   proto c ol  resili ent a gai nst a n  a c tive  adaptive  adv ersary  3 Q  struct ure. A s sume  two  committe d inp u t value s   a and b share d  with CSP so that each pl ayer  j p holds  a  c o mmitment to that s h are  j a  and  j b  .  To com pute the additio n  of   a and  b , each p l ayer  i p  add s hi s two sha r es  ii i ca b   and  comp utes a  commitment fo r  ii ab . Multiplicati on of the values  a  and  b :  1)   Each pl ayer  i p   multiplies his shares  ii i ca b and commits to  the res u lt. Eac h   i p   then perfo rm s CMP ( a C , b C , i c C ) wh ere  a C , b C  and i c C  are  the commitm ents to  , ii ab  and  i c .  2)  Each pl ayer then  sha r e s  his  commit m ent to  i c  usin g the CSP protocol.   3) Every pla y er no w com putes th e value  1 n ji i j i cc and a co mmitment  j c C for it.   Players  can  check if the value is corre c t becau se 11 j nn ci i j i j i ii CC C     .   If a particip a n t fails in an y of the above step s, he i s  disqualifie d ,  and if the adversary  st ru ct ur e i s   3 Q , his i nput  can  be i gno red, i.e., we  rem o ve  co rru pt playe r s from th e  recombi natio n vecto r . Th e  re con s tructio n  is st ill  po ssi ble, be ca use  the num be r o f  hone st pl ayers  is suffici ent e noug h to reco nstru c t the mi ssi ng lo cal  m u ltiplication. T o  illustrate thi s , recall that fo r   a  3 Q  threshold   scheme  the  a d versary th re shol d i s   3 n t . Given thi s  requi rement, the  n u mbe r   of hon est pl a y ers i s   at lea s t  2 nt t  , which me ans that the r e exist e nou g h  ho nest  play ers to   recon s tru c t the missi ng lo cal multiplicati on, whi c h wo uld be a poly nomial of deg ree  2 t .  If we allo w fo r a  negligi b le  error and  a s sume  a b r o a dca s t  chan ne l, then  32 nn t   is   sufficie n t for  se cure multi-party comput ation [19].  In pape r [18], it sho w e d  that  we  can  co nst r uct   a gen eral se cure m u lti-pa rty com putati on  sc heme  from  any line a r  se cret sh aring  sch e m e   provided that  the acc e s s   s t ru c t ure allows MPC and VSS. That is , we  c a n cons truc t  a  s e cure   multi-pa rty co mputation p r o t ocol from a n y  M with a  2 Q  ( 3 Q ) adversa ry structure.    4.3. SMPC  w i th Gener a l Adv e rsar y  Struc t ure s   It is relatively  straig htforward to use the te ch niqu es we  have seen to  con s tru c t pro t ocol s  se cure agai n s t gene ral ad versa r ie s, i.e., where  the adversa ry’s  corrupti on cap abilities  a r e not  descri bed  onl y by a thresh old t on the n u mbe r  of  pla y ers that  can  be co rrupt, b u t by a gene ral  adversa ry structure,  as def ined ea rlier.   What we hav e see n  so far can b e  thou ght of as a  way to build secu re MP C p r otocols  from Shami r ’ s  secret sha r ing  scheme.  The  idea i s  no w to re place Shami r ’s  scheme  by  somethi ng m o re ge ne ral, but otherwise  use e s sential l y the same h i gh-level p r ot ocol.   Evaluation Warning : The document was created with Spire.PDF for Python.
TELKOM NIKA   ISSN:  2302-4 046     Study on Co mm itm ent Schem es of Secure  Multi-pa rty Com putat io n (Xiaoqi ang  Guo)  7531 To see h o w  su ch a mo re  general sch e me co uld work, ob se rve  that the evaluation of  sha r e s  in Sh amir’ s  sch e m e  ca n be  de scrib ed in  an  alternative  way. If the polynomial u s ed  is  1 () n n f Xs a X a X  , we  c a n think  of the  coeffic i ent s   1 ( , ,,) n sa a  as b e ing  arrang ed in   a col u mn ve ctor  . Evalua ting  () f X  in point s   1, 2 , , n  is no w  eq uivalent to  multiplying th e vecto r  by a  Van de r Mo n de matrix  M , with rows   of form  01 (, , , ) n ii i . We  may   think of th e schem e a s  b e i ng defin ed b y  this fixed  matrix, and  b y  the rule th a t  each  playe r  is   assign ed 1  ro w of the  matri x , and get s a s  hi s  sha r e th e coordinate  of  M  co rrespon ding to  h i s  row.   It is now im mediate to th ink of gen era lization s  of this: to other m a trice s  tha n  Van der  Monde, an d to ca se s whe r e players ca n  have mo re then one  row  assign ed to them. This lea d s  to gene ral lin ear  se cret sh aring  schem e s , also kn own as M onoto ne Span P r o g ram s (MSP).  The  term “li nea r”  is motivated  by the fact a n y su c h   sc he me  ha s  the s a me  pr o p e r t y a s  Sha m ir ’s  scheme, th at  sha r ing  two  secrets  , ss and  ad ding  co rre sp o nding  sh ares  of  s  an d  s , we obtain  s h ar es  o f   ss . The p r oto c ol  constructio n s  we h a ve see n  have p r ima r ily used thi s  linearity  property, s o  this  is  why it  mak e s  sens e to tr y  to plug in MSP’s instea d of Shamir’ s  schem e.  There are, h o weve r, seve ral techni cal  difficultie s to  sort o u t alon g the way, primarily be cau s e   the method  we used to do  se cure multip lication o n ly  g eneralizes to  MSP’s with a  certai n spe c i a l  property, so  called multipli cative MSP’s. Not all  MSP’s are m u ltiplicative,  but it turns that any  MSP can be  use d  to con s t r uct a n e w on e that is inde ed multiplicative [22].  Furthe rmo r e,  it turns out t hat for any adversary stru ctur e, the r e exists an MS P-ba sed  se cret sha r in g scheme fo r whi c h the  unqu alifi ed sets are exa c tly those in the adversa ry  stru cture. Th erefo r e, the s e i dea s le ad t o  MPC p r oto c ol s for  any  a d versary  stru cture  wh ere  MPC   is po ssi ble at all.      4.  Conclusi on  Study on SM PC is a  hotspot in int e rn a t i onal  cryptog r aphy. SMP C  plays an i m portant  role i n  e - votin g , e-a u ctio n,  se cret  sh arin g,thres hold  si gnature et c. In this  pap er,  we int r od uce  the  basi c  con c ep t of SMPC and four b a si c agre e ment.  And we  sep a r ately illustrate commitm e n t  transfe r proto c ol, com m itment sha r ing p r otocol  a nd co mmitment mu ltiplication p r o t ocol. La st, we   pre s ent u n co nditionally se cure multi-pa rty comp utation. In-de p th  work i s  ne ed ed for SMP C   further  re sea r che s  an d app lication s  in rel a ted fields.       Ackn o w l e dg ements   This  wo rk  wa s supp orted  b y  the Scientific Te chn o logy  Re sea r ch an d Develo pme n t Plan  Proje c t of Tangshan (No.  1213 0200 1a ).      Referen ces   [1] Ach  Yao.  Proto c ols for Secure  Computati o n .  Procee din g  of the 23r d IEEE S y mp osi u m on  Foundati o n s   of Computer S c ienc e. 198 2: 160-1 6 4   [2]  O Goldreich, S Micali, A Wigderson.  H o w  to play A n y  ment al g a m e . In Pr ocee din g s of t he n i net eent h   ann ual ACM c onfere n ce o n  T heor y  of comp uting. 19 87: 21 8-22 9.  [3]  P Bogetoft, DL Christens en.  Secure  Multipart y  Com put ation Goes Liv e .  Cryptology   e- Print Archiv e  Rep o rt . 2008.   [4]  Guo  Xi ao qia n g , Z han g S h u a i, L i  Yi ng. K e y T e c hnol og i e s a n d  App lic ations  of S e c u re M u ltip art y   Comp utation.  TEL K OMNIKA . 2013; 1 1 (7): 3 774- 3 7 7 9 .  [5]  Gold w a sser S, Micali S. Probabilistic Encr y p tion.  Jour nal  of Co mputer  an d System Sc ie nces . 1 984;  28(2): 27 0-2 9 9 .   [6]  ElGamal T .  A Publ ic-Ke y  Cr ypt o s y stem an d  A Sig natur e  Scheme B a s ed o n  Discr ete Lo garithms .   IEEE Transactions on Infor m a t ion Theory.  1 9 85; 31(4): 4 69- 472.   [7] Bena loh  J.  D e nse Pro b a b ilisti c Encryptio n . Proc. of the W o r kshop  on S e le cted Areas  of Cr yptogr aph y.   Kingsto n, Can ada. 19 94: 12 0 - 128.   [8] Paill ier   P.  Pu bl ic-Key Crytosy s tems Base d on Co mp osite  Degr ee Resi du osity  C l asses . Advanc es  i n   Cr yptol o g y  EU ROCRYPT  LNCS15 92. Berli n : Springer-V erl ag. 199 9: 223- 238.   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:  752 3  – 7532   7532 [9]  Micha e l O R a bin. H o w  to  e x ch an ge s e cre t s  w i t h  o b liv io us transfer.  H a rvard Univ ers i ty  T e chnic a l   Rep o rt , 1981.   [10]  Shimo n  Eve n , Oded Gol d re ic h, A Lem pel.  A rand o m i z e d   protoco l  for si g n in g co ntracts .         P r o c .   CRYPT O’82. Ne w  Y o rk. 198 3:  205-2 10.   [11] C  Crepe au.  Eq uival enc e betw een tw o flavou rs of oblivio us transfers . CRYPTO’87. Berlin  Heid elb e r g .   198 7.  [12]  G Brassard, C  Crep eau, JM Robert.  Informati on theor etic re ductio n s a m on g disclos ure          proble m s .  Proc. the 27th IEEE S y mp osiu m F oundati ons  of Computer S c ienc e.  Califor il ia, 198 6: 168- 1 73.   [13]  G Brassard, C Crep eau, J M  Robert.  All  or nothin g  d i sclosur e of secrets . CRYP T O’86. Berlin   Heid el berg. 1 9 86; 234- 23 8.  [14] C  Cachi n .  On the foun dati on  of obliv ious tra n sfer .  LNCS, CRYPT O’98. Berlin H e i del ber g. 1998.   [15] A  Yao.  Pr otoc ols for S e cur e  Co mp utatio n . Proc of the  23rd IEEE S y m posium on Foundations of   Comp uter Scie nce. 198 2: 160 -164.   [16]  HK Lo, HE Ch au. W h y  Qu an tum Bit Commitment  and Id e a l Quant um C o intoss ing  are  Impossibl e.   Physica D ., 19 98; 120: 1 77-1 87.   [17]  S Gold w a sser, S Micali, C Rackoff.  T he Know ledg e Co mp lexity of  Interactive Proofs System s . Proc.   ST OC, Ne w  Y o rk: ACM Press, 1985: 29 1-3 04.   [18]  R Cram er, I  Damg ard, U  Maurer. Ge ner al sec u re  mult ipart y  com puta t ion from  an y lin ear s e cre t   shari ng schem e.  Cryptolo gy e - Print Archive  Rep o rt.  2000.   [19]  R Cramer, I Damgard. Multi p a r t y  comput atio nan i n trod uctio n . 2002.   [20]  B Micha e l, S  Gold w a sser, A  W i gders on.  C o mpl e teness  theor e m s for  n on-crypto grap h i c fault-tol e ra nt   distrib u ted c o mp utatio n.  In  ST OC ’88: Pr ocee din g s  of the t w e n tiet h a nnu al A C M s y mposi u m o n   T heor y  of com putin g. 198 8: 1–10.   [21]  R Cramer, I Damgard, JB Nie l s en.  Secure M u ltip art y  C o mp utation. 2 012.   [22]  China Sc ience and  T e chnology  Ass o ciation. Cr y p tography  Subject  Development Report, China  Scienc e an d T e chn o lo g y  Pre ss.  2007-20 10 .        Evaluation Warning : The document was created with Spire.PDF for Python.