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 4 5 ~2 650   I SS N:  2 0 8 8 - 8708 ,  DOI : 1 0 . 1 1 5 9 1 / i j ec e . v7 i 5 . pp 2 6 4 5 - 2 650          2645       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   Priva cy  P reserv in g  Auct io n Ba sed  Virtual M a chine   Ins tances   Allo ca tion Sche me for Cloud  Co mputing  Env iro n ment       Su neet a   M o ha nt y ,  P ra s a nt  K u m a r  P a t t na i k ,  G .   B .   M un d   S c h o o l  o f   Co m p u ter  E n g in e e rin g ,   KIIT   Un iv e rsit y ,   Bh u b a n e sw a r,   In d ia       Art icle  I nfo     AB ST RAC T   A r ticle  his to r y:   R ec eiv ed   J u l   23 ,   2 0 1 6   R ev i s ed   J u n   7 ,   2 0 1 7   A cc ep ted   Sep   11 ,   2 0 1 7       Clo u d   Co m p u ti n g   E n v iro n m e n t  p ro v id e s  c o m p u ti n g   re so u rc e s  in   t h e   f o r m   o f  V irt u a l  M a c h in e s  ( V M s),   t o   t h e   c lo u d   u se r s   th ro u g h   I n tern e t.   A u c ti o n - b a se d   V M   i n sta n c e s  a ll o c a ti o n   a ll o w s   d if fe re n t  c lo u d   u se rs  to   p a rti c i p a te  in   a n   a u c ti o n   f o r  a   b u n d le  o f   V ir tu a l  M a c h in e   in sta n c e s  w h e re   th e   u se r  w it h   th e   h ig h e st  b i d   v a lu e   w il l  b e   se lec ted   a s  th e   w in n e r  b y   th e   a u c ti o n e e r  (Clo u d   S e rv ice   P ro v id e r)   to   g a in   m o re .   In   th is  a u c ti o n   m e c h a n is m ,   in d iv id u a l  b i d   v a lu e s  a re   re v e a led   to   th e   a u c ti o n e e r  in   o rd e r  to   se lec t  th e   w in n e r  a s  a   r e su lt   o f   w h ich   p riv a c y   o f   b id   v a lu e s  a r e   lo st.  In   th is  p a p e r,   w e   p ro p o se d   a n   a u c ti o n   sc h e m e   to   se lec t  th e   w in n e r  w it h o u t  re v e a li n g   th e   i n d iv id u a l  b id   v a l u e s  to   t h e   a u c ti o n e e r  to   m a in tain   p riv a c y   o f  b id   v a lu e s .  T h e   w in n e r  w il l  g e t  th e   a c c e ss   to   t h e   b u n d le  o f   V M   i n sta n c e s.  T h is  sc h e m e   re li e s  o n   a   se t  o f   c r y p to g ra p h ic  p ro t o c o ls  i n c lu d in g   Ob li v i o u s   T ra n sf e r  (O T )  p ro to c o l  a n d   Ya o ’s  p ro t o c o l  t o   m a in tain   p riv a c y   o f   b id   v a lu e s.     K ey w o r d s :   Au ctio n   C lo u d   s er v ice  p r o v id er   ( C SP )   C lo u d   c o m p u ti n g   e n v ir o n m e n t   ( C C E )   P r iv ac y   Vir tu al  m ac h in e   ( VM )     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 :   Su n ee ta  Mo h a n t y ,     Sch o o l o f   C o m p u ter   E n g i n ee r i n g ,   KI I T   Un iv er s i t y ,   B h u b an e s w ar ,   I n d ia.   E m ail: s u n ee ta m o h a n t y @ g m a il.c o m       1.   I NT RO D UCT I O N   ( 1 0   P T )   C lo u d   C o m p u ti n g   E n v ir o n m e n t( C C E )   e n ab les  t h e   c lo u d   u s er s   to   d ep lo y   t h eir   ap p licatio n s   i n   clo u d   v ia  I n ter n et  o n   d e m a n d [ 1 ] .   C lo u d   is   a  t y p e  o f   d is tr ib u ted   a n d   p ar allel  s y s te m   co m p r is in g   o f   a  co llectio n   o f   in ter co n n ec ted   an d   v ir t u alize d   co m p u ter s   w h ic h   ar e  d y n a m icall y   p r o v is io n ed   a n d   p r esen ted   as  o n e  o r   m o r e   u n i f ied   c o m p u ti n g   r eso u r ce s   b ased   o n   Ser v ice  L ev el   A g r ee m en t ( S L A )   [ 2 ] [ 3 ]   u s in g   p a y   p er   u s e  m o d el.   A t  t h e   s a m e  ti m e,   C lo u d   Ser v ice  P r o v id er   g et  b en ef it  d u e  to   co m m er cial izatio n   o f   h u g e  co m p u ti n g   r eso u r ce s   th r o u g h   clo u d   p latf o r m .   S L A   i s   a  le g al  co n tr ac t  b et w e en   C SP   an d   clo u d   u s er   to   ac h iev e  Qu al it y   o f   Ser v ice( Qo S)  [ 3 ] .   A   v ir t u aliz atio n   en v ir o n m e n t  en ab le s   th e  s er v ice  p r o v is io n   b y   cr ea ti n g   V ir tu al  Ma c h i n e   in s ta n ce s   w h ich   h a s   b ec o m e  th e  e s s e n tial   tec h n o lo g y   o f   C lo u d   C o m p u t in g   E n v ir o n m e n ts [ 4 ].   Vir t u a l   Ma ch i n es  ar e   t h e   s o f t w ar e  i m p le m en ta tio n   o f   th e   co m p u ti n g   e n v ir o n m en t   w h er e  a n   O S  o r   a  p r o g r a m   m a y   b e   in s ta lled   an d   r u n .   C u r r en tl y   f i x ed - p r ice  allo ca tio n   m ec h an is m   is   u s ed   b y   m o s t  o f   t h e  C SP s   to   allo ca te  Vir tu a l   Ma ch i n e  i n s ta n ce s   to   th e ir   u s er .   C lo u d   C o m p u ti n g   E n v ir o n m e n t  o f f er s   I aa S  ( I n f r astr u ctu r e  as  a   Ser v ice) ,   P aa S  ( P latf o r m   as  a  Ser v ice) ,   an d   SaaS  ( So f t w ar e  as  a  S er v ice)   o n   th e  b asis   o f   s u b s cr ip tio n   th at  h elp s   d if f er e n t  o r g an iza tio n s   in   d ec r ea s in g   o p er atio n al  ex p en s e s .   I n   f i x ed   p r ice  m ec h a n is m ,   clo u d   u s er   w h o   v al u e s   th e  V M  i n s ta n ce s   m o r e   m a y   o r   m a y   n o t  g et   ac ce s s   to   it.  He n ce   it   is   n o t  ec o n o m icall y   e f f i cien t[ 5 ] .   A ls o   f i x ed   p r ice  allo ca tio n   m ec h a n is m s   m a y   lead   to   g e n er ate  r ev e n u e   w h ic h   i s   les s   t h an   o p ti m al  r ev en u e  f o r   C SP [ 5 ] .  T h is   p r o b lem   ca n   b e  ad d r ess e d   b y   u s i n g   a u ct io n   b ased   VM   in s tan ce s   allo ca tio n   m ec h an i s m .   Secu r i t y   is   th e   m aj o r   co n ce r n   in   clo u d [ 6 ]   an d   p r iv ac y   p r eser v atio n   is   r eq u ir ed   to   ac h ie v e  th e  in te g r it y   o f   d ata[ 1 5 ] .   I n   th is   p ap er ,   w e   p r o p o s ed   a   p r iv ac y   p r eser v in g   a u ctio n   b ased   V M  in s ta n ce s   allo ca tio n   s ch e me   r u n   b y   C SP   w h ic h   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 4 5   –   2 6 5 0   2646   w il l   h elp   i n   s elec ti n g   t h e  w i n n er   o f   t h e  a u ctio n   w i th o u t  s ee i n g   t h e  i n d iv id u al  b id   v al u es   o f   p ar ticip an ts   o f   t h e   au ctio n   i.e ,   clo u d   u s er s .   Th is   p ap er   is   o r g an ized   as  f o llo w s :  Sect io n   2   d is cu s s e s   th e  e x is t in g   p r icin g   s c h e m es  i n   C C E .   Sectio n   3  p r o p o s es  a  p r iv ac y   p r eser v in g   a u ctio n   s ch e m e  f o r   VM   in s ta n ce s   al lo ca tio n .   Sect io n   4   d is cu s s es  t h e   ex p er i m e n tal  r es u lt a n a l y s is .   L astl y   s ec tio n   5   co n cl u d es t h e  w o r k   alo n g   w i th   it s   f u t u r e  s co p e.       2.   RE L AT E D  WO RK   T h r o u g h   C lo u d   C o m p u ti n g   E n v ir o n m e n t( C C E ) ,   i n d iv id u al  an d   s m all   to   lar g e   o r g an i za tio n s   ca n   f u lf i l  th eir   co m p u tatio n al  r eq u ir e m e n t s   w ith   m i n i m u m   co s t.  I t  is   b ec o m in g   cr itical  f o r   th e  s ev er al  C lo u d   S er v ice  P r o v id er s ( C SP )   to   d et er m in e   ap p r o p r iate  p r ice  f o r   u s er s .   T h er e  ex i s t  m a n y   p r icin g   s ch e m e s   f o r   C lo u d   Ser v ice  P r o v id er s   w h ic h   ar e  b r o ad ly   clas s i f ied   in to   f ix ed   a n d   d y n a m ic  p r ici n g   s ch e m e.   C C E   p r o v id es  t h e  r eq u ir ed   co m p u tat io n al  n ee d s   o f   t h e  clo u d   u s er   in   ter m s   o f   Vir tu a l  Ma c h in e s ( VM )   in   p a y   p er   u s e  b asis .   I n   cu r r e n t  s ce n ar io ,   th e  m aj o r ity   o f   C lo u d   Ser v ice  P r o v id er   f ix   th ei r   p r ice  b ased   o n   th e   s ize  o f   VM   i n s ta n ce s .   Fi x ed   p r icin g   s c h e m e   i s   o n e   o f   t h e   w id el y   u s ed   tec h n iq u e   in   C C E .   I n   f ix ed   p r ice   m ec h a n i s m ,   VM   i n s ta n ce s   ar e  allo ca ted   o n   a   f ir s t - co m e,   f i r s t - s er v e  b asi s   to   t h e  u s er s   t i l l  th e  r eso u r ce s   ar e   ex h a u s ted [ 7 ] . Use  o f   f i x ed   p r i ce   s ch e m e  m a y   te n d   to   lo w er   th e  r e v en u e   g en er atio n   f o r   th e  C SP   as  t h e  clo u d   u s er   p a y   les s   f o r   u s in g   th e   s a m e  r eso u r ce s   f o r   a  lo n g   p er io d .   So   to   ad d r ess   th e  p r o b lem   o f   h i g h   r e v en u e   g en er atio n   f o r   C SP ,   a u ctio n   b ased   p r icin g   s c h e m e  is   u s ed .   I n   d y n a m ic  p r ici n g   s ch e m e,   f in al  s er v ice  p r ice  is   d ec id ed   d y n a m icall y   t h r o u g h   a u ctio n s .   Au ctio n   b ased   p r icin g   s c h e m e  f o llo w s   d y n a m ic   p r icin g   p o lic y   w h er e  a  tar g e t  s er v ice  p r ice  is   ac h i ev ed   r es u lti n g   f r o m   d y n a m ic  s u p p l y   a n d   d e m an d   t h r o u g h   a u ctio n .   C o m b i n ato r ial  a u ctio n   i n   C C E   allo w s   th e   u s er   to   b u y   a  b u n d le   o f   VM   i n s tan ce s   t h r o u g h   a u c tio n   w h ic h   is   p r o f itab le  to   b o th   th e  b u y er   an d   s eller .   Fo r   th e  e n tire   b u n d le,   b id   is   s u b m itt ed   as a   s in g le  u n it.   Z a m an   an d   Gr o s u   [ 7 ]   p r o p o s e d   a  co m b in ato r ial  a u ctio n   m ec h an i s m   w h ic h   allo w s   t h e  clo u d   u s er s   to   b id   f o r   a   s u b s et  o f   a  VM   in s t an ce s   ( b u n d le) .   C lo u d   Ser v ice   P r o v id er   b ein g   th e   au ctio n ee r   s elec ts   th e  w in n er   h av i n g   th e  h ig h es t  b id   v alu e  f o r   th at  p ar ticu lar   b u n d le  o f   VM   in s ta n ce s .   I n   t h eir   w o r k ,   th e y   h av e  p r o p o s ed   CA - GR E E DY   an d   C A - L P   m e ch an i s m   to   p er f o r m   co m b i n at o r ial  au ctio n .   T h e y   a n al y s ed   t h e  p r o s   a n d   co n s   o f   th e  p r o p o s ed   m ec h a n i s m s   an d   p r o v id ed   th e  g u id eli n es  f o r   its   i m p le m en ta tio n .   P r asad   et  al.   [ 8 ]   p r esen ted   a  p r o cu r em e n t   au ctio n   a s   a  s o l u tio n   o f   r e s o u r ce   allo ca tio n   p r o b lem   in   clo u d .   I n   t h eir   p r o p o s ed   au cti o n   s c h e m e  t h e y   h av e   in tr o d u ce d   th e  co n ce p t  o f   au ct io n   b r o k er   w h ich   w il l  r u n   th e  au ctio n   m ec h an is m   in s te ad   o f   C lo u d   Ser v ice  P r o v id e r .   A s   a  r esu lt  o f   w h ich   clo u d   u s er s   w ill  co n tact   au ctio n   b r o k er   f o r   th eir   r eso u r ce   r eq u ir em e n t s   an d   d if f er en t  C lo u d   Ser v ice  P r o v id er s   w il l  p ar ticip ate  in   th e   au ctio n   r u n   b y   th e  b r o k er   f o r   th e  r eso u r ce   allo ca tio n .   T h eir   p r o p o s ed   au ctio n   s ch e m e  w as  b ased   o n   C o m b i n ato r ial  Au ctio n   B r an ch   o n   B id s ( C A B OB )   m o d el  an d   s u p p o r ts   m u ltip le   r eso u r ce   s elec tio n   b y   clo u d   u s er .   Gar g   et  al.   [ 9 ]   p r o p o s ed   a  d o u b le  au ctio n   m ec h a n is m   t h at  in v o l v es  b o th   b u y er   a n d   s elle r   to   s u b m it   th eir   b id s   to   th e   au ct io n ee r .   T h e  a u ctio n ee r   ta k e s   t h e  h elp   o f   m eta  s ch ed u ler   to   s o r t  th e   b id s   in   asce n d in g   a n d   d escen d in g   o r d er   an d   lo o k   f o r   a  m atc h .   I f   m a tch   f o u n d ,   th e   av er ag e  o f   th e  v alu e s   is   s et  a s   th e  au ct io n   p r ice  f o r   th e  r eso u r ce .   T h e  s a m e  p r o ce s s   co n ti n u ed   f o r   th e  u n m at ch ed   r eq u est.  B o th   s eller   a n d   b u y er   ar e  b en ef i tted   in   th is   a u ctio n   m ec h an i s m .   Z a m an   a n d   Gr o s u   [ 10 ]   p r o p o s ed   C A - P R OVI SIO N  m ec h a n i s m   to   ad d r ess   t h e  d y n a m ic  p r o v is io n in g   o f   VM   in s ta n ce s   to   g en er ate   m o r e   p r o f it  f o r   clo u d   w h ich   is   n o t  co n s id er ed   i n   t h eir   p r ev io u s   w o r k [ 7 ] . T h r o u g h   ex ten s i v e  ex p e r i m en t s   t h e y   h av e  p r o v ed   th at  i n   ca s e  o f   l o w   d e m a n d ,   C A - P R OVI SIO N  g en er ate s   h i g h er   r ev en u e  th a n   C A - GR E E DY.   Am az o n   E C 2   u s es  an   au c tio n   ca lled   as  Am az o n   s p o t  in s tan ce s   [ 1 1 ]   w h er e  th e  u s er s   b id   f o r   th e   u n u s ed   v ir tu a l  m ac h i n es.  User   h av i n g   h i g h er   p r ice  th an   s p o t p r ice  w h ic h   i s   s et  b ased   o n   d at a  ce n tr e  u til izatio n   b y   t h e  Am az o n   w il l g et  t h e  ac ce s s   to   th at  VM   i n s tan ce s .   C h o i  a n d   L i m   [ 1 2 ]   d is cu s s e d   th e  i m p o r ta n ce   o f   SLA  v i o latio n   co s t  to   i n cr ea s e  C lo u d   Ser v ic e   P r o v id er ' s   p r o f it.  T h ey   p r o p o s ed   a  s ch e m e  to   r ed u ce   t h e  p en alt y   co s t  f o r   SLA   v io latio n   d u r in g   co m b i n ato r ial   Au ctio n   co n s id er in g   u r g en c y   o f   j o b s .   T h ey   ca lc u lated   p r o b ab ilit y   o f   ea c h   j o b ' s   d ea d li n e  v io latio n   to   f in d   ex p ec ted   p r o f it  v alu e  f o r   th e  s er v ice  p r o v id er   to   s elec t  th e  u s er   w it h   lar g est  e x p ec ted   v alu e  as   th e  b id   w i n n er .   T h u s   d ec r ea s in g   SLA   v io l atio n   lead s   to   d ec r ea s e  p en alt y   co s t  w h ic h   in   tu r n   in cr ea s es  s er v ice   p r o v id er ' s   p r o f it.        3.   P RO B L E M   ST AT E M E NT   C lo u d   u s er   ca n   c h o o s e  a  w i d e  r an g e  o f   VM   in s ta n ce s   b ased   o n   t h e  p er f o r m an ce   h e/ s h e  w an t s .   Dep lo y m e n t  o f   m o r e  VM   i n s t an ce s   o r   r ep laci n g   th e   ex is ti n g   VM   in s ta n ce s   w it h   p o w er f u l  VM   i n s tan ce s   ca n   Bo tt o m   M a rg in   0 . 6   +   o n e   1 0 p t  l in e   sp a c e   a f ter p a g e   n u m b e r   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708       P r iva cy   P r eser vin g   A u ctio n   B a s ed   V ir tu a l Ma ch in e  I n s ta n c es A llo ca tio n   S ch eme   f o r   C lo u d   C o mp u tin g   E n viro n men t   ( S u n ee ta   Mo h a n t y )   2647   in cr ea s e  t h e  p er f o r m an ce   o f   th e  ap p licatio n .   Hen ce   to   g et   b etter   p er f o r m an c e,   clo u d   u s er   ca n   o p t  to   g e t   ap p r o p r i ate  VM   in s ta n ce s .   I n   ex is t in g   a u ctio n   m ec h an is m s ,   au ctio n ee r   k n o w s   t h e  b id   v al u es.  I t  m a y   lead   to   lo s s   o f   p r iv ac y   a n d   i n te g r it y   o f   b id   v alu e s   to   w in   t h e  a u cti o n   o r   to   g ain   m o r e   p r o f it .   He n ce   to   p r ev e n t   s u c h   k in d   o f   ac ti v ities ,   w e  h a v e  p r o p o s ed   an   au ctio n   s ch e m e   t h at  al lo w s   th e   u s er   to   p ar ti c ip ate  in   a  p r iv ac y   p r eser v in g   a u ctio n   to   g et  th e  b est  VM   in s ta n ce s   w i th o u t  r ev ea li n g   t h eir   b id   v alu es  to   t h e  au ctio n ee r   ( C SP .   T h e  V M  in s ta n ce s   ar e  a s s i g n ed   to   th e  clo u d   u s er   w it h   h i g h e s t   b id   v al u e .   Hen ce ,   g en er at in g   h ig h er   r ev e n u e  f o r   th e  C lo u d   Ser v ice  P r o v id er   ( C SP ) .   T h e  a u ctio n - b ase d   VM   in s ta n ce s   al lo ca tio n   s c h e m e  is   r u n   b y   th e  C SP .   L i k e  o th er   s ec u r e  co m p u tatio n ,   th e  p r o p o s ed   au ctio n   s ch e m e   c a n   d eter m i n e  t h e  w i n n er   o f   th e  a u ctio n   u s i ng  s ec u r e  m u ltip ar t y   co m p u tat io n   w h ic h   r elies  o n   a  s et  o f   cr y p to g r ap h ic  p r o to co ls   in clu d in g   Ob liv io u s   T r an s f er   ( OT )   p r o t o co l  an d   Yao ’ s   p r o to co l u s i n g   R S A   al g o r ith m .     3 . 1 .     Ya o ’ s   P ro t o co l   S ec u r e  m u lti - p ar t y   co m p u ta ti o n   allo w s   m u lt ip le  p ar ties   ea ch   h av in g   a   s ec r et  i n p u t  to   c o m p u te  a   f u n ctio n   w h ile  en s u r i n g   n o   p ar ty   w i ll  r ev ea l  t h e  in p u ts   to   ea ch   o th er   o r   to   a  tr u s ted   th ir d   p ar ty .   T h e  co m p u tatio n   r esu l t  w ill  b e  co m m u n icate d   to   all  p ar ties .   Ho w e v er ,   a  g iv e n   p ar t y   w ill  o n l y   b e  ab le  t o   co m p u te   w h at  ca n   b e  in f er r e d   f r o m   t h e  f i n al  r es u lt s   a n d   its   o w n   i n p u t.   I n   [ 1 3 ]   Yao   in tr o d u ce   th e   p r o b le m   o f   co m p u ti n g   th e  m a x i m u m   w i th   t h e  f o llo w i n g   p r o b le m :  T w o   m il lio n air es   w a n t  to   co m p ar e  th eir   r ich es,  b u t  d o   n o t  w an t  to   r ev ea l to   ea ch   o th er   w h ich   i s   t h e  ex ac t a m o u n t o f   t h eir   w ea lt h .     3 . 2 .     O bli v io us   T ra ns f er   ( O T )   pro t o co l   Ob liv io u s   T r an s f er   p r o to co l  [ 1 4 ]   is   ce n tr al  to   i m p le m en t  Y ao ' s   p r o to co l.  OT 1 2 ,   1 - o u t - of - 2   o b liv io u s   tr an s f er   en s u r es  t h at  o n e  p ar t y   ca n   o b tain   o n e  o f   t h e  t w o   m es s ag e s   f r o m   a  s ec o n d   p ar t y   an d   b o th   th e  p ar ties   co u ld   n o t  k n o w   w h ich   v al u es  ar e  s elec ted   b y   ea c h   o th er .   OT 1 k ,1 - o u t - of - k   o b liv io u s   tr a n s f er ,   is   t h e   f u n ctio n alit y :  OT 1 k ((σ 1,   σ 2, . . . ,   σ k  ) , i)   =  ( λ ,   σ i )   w h er e  σ 1,   σ 2, . . . ,   σ k  ϵ   {  0 , 1 }  an d   i  ϵ   {   1 , . . . . , k   }. Her e,   th e  f ir s t  p ar t y   ( A lice)   h a s   k   s ec r et  b its   σ 1,   σ 2, . . . ,   σ k.   B o b   h as  a  s ec r et  in d ex   i.  A t  t h e  en d   o f   t h e  p r o to co l,  B o b   lear n s   o n l y   σ i   an d   A lice  lear n s   n o t h i n g   ( λ ) .   I n   p ar ticu lar ,   A l ice  d o es  n o t  k n o w   w h ic h   o f   h er   b its   w as  l ea r n ed   b y   B o b ,   an d   B o b   d o es  n o t  lear n   σ j   f o r   an y   j   ≠   i.  Ob li v io u s   tr an s f er   is   ce n tr a l  to   m a n y   o f   th e   co n s tr u ctio n s   f o r   s ec u r e   m u ltip ar t y   co m p u tatio n .       4.   T H E   P RO P O SE D  P RIVA C Y  P RE S E RVI NG   A UCT I O N  SCH E M E   T h e  s y s te m   m o d el  o f   t h e  p r o p o s ed   s ch e m e,   w h ich   i n clu d e s   ' n '  o r g a n izatio n s   ( C lo u d   Us er 1 ,   C lo u d   User 2 . . . ,   C lo u d   User n )   a n d   a  C lo u d   Ser v ice  P r o v id er   is   il lu s tr ated   in   Fi g u r e1 .   T h e  p u b lic  k e y   ( d ata  en cr y p tio n )   an d   p r iv ate  k e y   ( d ata  d ec r y p ti o n )   ar e  m a n a g ed   b y   th e  C lo u d   Ser v ice  P r o v id er   to   p e r f o r m   p r iv ac y - p r eser v i n g   a u ctio n   a m o n g   a  n u m b er   o f   o r g an iza tio n s .         Fig u r e  1 .   S y s te m   m o d el  o f   th e   p r o p o s ed   p r iv ac y   p r eser v i n g   au ctio n   s ch e m e       Al l  p ar ticip an t s   o f   th is   s c h e m e   w o r k   in   a  s e m i - h o n est  e n v i r o n m e n t,  w h er e  th e y   m a y   tr y   to   d e d u ce   ad d itio n al  in f o r m atio n   d u r i n g   th e  p r o to co l  ex ec u tio n .   T h e  w o r k f lo w   o f   t h e  p r o p o s ed   s ch e m e  is   s u m m ar ized   in   T ab le  1   as g iv en   b elo w :           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 4 5   –   2 6 5 0   2648     T ab le  1 .   W o r k f lo w   o f   th e  p r o p o s ed   s y s te m   S tep   1 - Ke y   Ge n e ra ti o n   A lg o rit h m   u se d   b y   CS P   1 . 1               Ch o o se   p   a n d   q :  tw o   d isti n c t  p rime   n u m b e rs   1 . 2   Co m p u te N = p × q ,   W h e re   N i s  u se d   a s th e   m o d u l u s f o r  p u b li c   a n d   p riv a te k e y s   1 . 3   Co m p u te Φ   (N) = (p - 1 )× (q - 1 ),   W h e re   Φ  is  th e   Eu li e r  f u n c ti o n   1 . 4   Ch o o se   e n c ry p ti o n   k e y   w h ich   is  a n   in teg e r  ' e '   su c h   th a t,   1   <   e   <   Φ  ( N) an d   g re a tes t   c o m m o n   d iv iso r  o f   (e ,   Φ  (N)) =  1   1 . 5   De ter m in e   th e   d e c ry p ti o n   k e y   d   = (  1 /e) m o d   Φ  (N)   1 . 6   A ll   th e   a b o v e   v a lu e s o f   p u b li c   k e y ( e , N= p × q )  a n d   p r iv a te k e y (d )  m u st b e   k e p t  se c re t  b y   CS P   S tep   2 -   Co ll e c ti o n   o f   re q u e st f ro m   p a rti c ip a n ts  a n d   p re p a ra ti o n   o f   li st b y   CS P   2 . 1   f o r  j  =   1 ,   .   .   .   ,   n   d o   2 . 2   Re c e iv e   (r j 1 , . . . , r j m   )  f ro m   u se r  u j   2 . 3   e n d   f o r   2 . 4   S o rt  u se rs ac c o rd in g   t o   th e ir   ti m e   o f   p lac in g   th e   re q u e st,  f ro m   e a rli e st t o   late st   (He re   w e   a ss u m e   u 1 ,   u 2 ,   .   .   .   ,   u n   a s th e   o rd e r. )   S tep   3 -   W in n e r  se lec ti o n   b y   th e   C lo u d   S e rv ice   P ro v id e r   3 . 1   L e t  u s  a ss u m e   f irst  a n d   se c o n d   p a rti c ip a n t   in   th is  p r o t o c o l  a re   d e n o ted   b y   A li c e   a n d   B o b   re sp e c ti v e l y   3 . 2   CS P   w il l  se n d   e , N t o   B o b   a n d   N t o   A li c e   3 . 3   Bo b   p ick s ran d o m   in teg e r  ' X '   o f   N b it   a n d   c a lcu late   C  =   X e   m o d   N   3 . 4   Bo b   c a lcu late s C -   I t   +   1 ,   w h e re   I t   is  th e   se n siti v e   d a ta o f   Bo b   a n d   se n d   i t  to   CS P   3 . 5   CS P   w il l  g e n e ra te Y 1 ,Y 2 ,Y 3 ......,Y 10   su c h   t h a t  Y 1  is  t h e   d e c i p h e rm e n t  o f   C -   I t   + 1 ,   Y 2   is  th e   d e c ip h e rm e n t  o f   C -   I t   + 2   a n d   so   o n .   u si n g   th e   f o rm u la :   Y 1 =   (C -   I t   + 1 ) d   m o d   N , Y 2 =   (C -   I t   + 2 ) d   m o d   N.. . Y 10 =   (C -   I t   + 1 0 ) d   m o d   N   3 . 6   CS P   se n d s Y 1 , . . . Y 10   t o   A li c e   3 . 7   A li c e   g e n e ra tes   a   p ri m e   n u m b e r  P   w h ich   is  N/2   b it   a n d   │Z i - Z j │≥   2   f o r  i≠ j  a n d   c a lcu late s  Z i =Y i   m o d   P   w h e re   i, j  ∈   [ 1 . . 1 0 ]   3 . 8   A li c e   a d d s 1   to   Z i   v a lu e s  f o r  a ll   i  > I k   w h e re   I k   is  th e   se c re t  v a lu e   o f   A li c e   3 . 9   A li c e   s e n d s  P ,   Z   v a lu e s to   CS P   3 . 1 0   CS P   se n d s  P ,   Z   v a lu e s to   B o b   3 . 1 1   Bo b   c a lcu late s G =   X   m o d   P   a n d   c h e c k s   If   (Z n   ≡   G   m o d   P )   S e t  W =   0     El se   S e t  W =   1   3 . 1 2   Bo b   se n d s W   to   CS P   3 . 1 3   CS P   c h e c k s     if (  W = = 0 )     A li c e   is  th e   w in n e r     e lse       Bo b   is  th e   w in n e r   3 . 1 4   T h e   sa m e   p ro c e ss   w il l  b e   r e p e a te d   f o r  th e   w in n e r  a n d   n e x t  p a rti c ip a n t  ti ll   n   n u m b e r  o f   u se r  to   d e term in e   th e   w in n e r  o f   th e   A u c ti o n   S tep   4 -   V M   i n sta n c e   a ll o c a ti o n   4 . 1   W in n e r  p a y s th e   CS P   4 . 2   CS P   w il l  a ss ig n   V M   in sta n c e s to   th e   w in n e r        5.     RE SU L T   A NALY SI S     I n   th i s   s ec tio n ,   w e  f o cu s   o n   e v alu a tin g   t h e  p er f o r m an ce   o f   o n e  o f   th e  ex is ti n g   au ctio n   s c h e m e  a n d   th e  p r o p o s ed   au ctio n   s c h e m e  in   ter m s   o f   ex ec u tio n   ti m e.   T h e  tec h n ical   s p ec if icat io n   o f   C P U,   OS  a n d   R A M   co n s id er ed   f o r   o u r   ex p er i m e n t al  s etu p   ar e  as  f o llo w s :  C P U:  I n tel  C o r e  i5   2 . 7 GHz ,   OS:  Ub u n t u ,   R AM :  8 GB .   I n   o u r   e x p er i m e n t, w e  h a v e  i n cr ea s ed   th e  n u m b er   o f   p ar tici p an ts ( C lo u d   User s )   f r o m   2 , 4 , 8   to   1 6   an d   r ec o r d e d   co r r esp o n d in g   ex ec u tio n   ti m e s   in   m illi   s ec o n d s ( m s )   to   s ele ct  th e  w i n n er   u s i n g   C A - G R E E DY  alg o r ith m [ 7 ]  an d   o u r   p r o p o s ed   p r iv ac y   p r eser v in g   au ctio n   s c h e m e   w h ic h   ar e  s h o w n   in   F ig u r e  2   an d   Fig u r e  3   r esp ec tiv el y .   As  s h o w n   i n   Fi g u r e   2 ,   C A - G R E E DYa l g o r ith m   ta k e s   5 8 m s   f o r   t w o   u s er s ,   6 2 m s   f o r   f o u r   u s er s ,   6 5 m s   f o r   eig h t   u s er s ,   6 6 m s   f o r   1 6   u s er s   to   s elec t  th e  w i n n er   o f   t h e  au c ti o n .   As  s h o w n   i n   Fi g u r e  3 ,   th e  p r o p o s ed   au ctio n   s ch e m e  ta k e s   9 9 5 m s   f o r   t w o   u s er s ,   1 5 8 2 m s   f o r   f o u r   u s er s ,   2 9 4 6 m s   f o r   eig h t  u s er s ,   5 6 3 8 m s   f o r   1 6   u s er s   to   s elec t th e  w i n n er   o f   t h e  au ctio n .   Evaluation Warning : The document was created with Spire.PDF for Python.
I J E C E     I SS N:  2 0 8 8 - 8708       P r iva cy   P r eser vin g   A u ctio n   B a s ed   V ir tu a l Ma ch in e  I n s ta n c es A llo ca tio n   S ch eme   f o r   C lo u d   C o mp u tin g   E n viro n men t   ( S u n ee ta   Mo h a n t y )   2649     Fig u r e  2 .  E x ec u tio n   T im e  v s .   No .   o f   p ar ticip an ts   f o r   C A - G R E E DY [ 7 ]   A lg o r it h m         Fig u r e  3 .  E x ec u tio n   T im e  v s .   No .   o f   p ar ticip an ts   f o r   th e  p r o p o s ed   au ctio n   s ch e m e       T h e  r esu lt  o b tain ed   s h o w s   t h at  th e   e x ec u t io n   ti m e  o f   o u r   p r o p o s ed   au ctio n   s c h e m e  i n c r ea s es  b y   1 . 1 7 %  th an   th e  ex is ti n g   CA - G R E E DY  alg o r it h m   [ 7 ]   b y   co n s id er in g   t h e  p r iv ac y   is s u e s   o f   b id   v alu es  w h ic h   is   m is s i n g   i n   C A - GR E E D Yalg o r ith m .   Ho w ev er ,   t h e  co m p u ti n g   ab ilit y   o f   C SP   is   m u ch   m o r e  t h an   o u r   si m u lat io n   P C   to   ca r r y   o u t  t h e s e  au ctio n   m ec h an is m s .   He n c e  th e  co m p u ta tio n   ti m e  w ill  b e   co m p ar ati v el y   le s s   th an   o u r s   in   r ea l  C C E .   He n ce ,   th i s   al g o r ith m   ca n   b e  u s ed   as   a  p r iv ac y   p r eser v i n g   a u ct io n   s ch e m e  to   ac h ie v e   pr iv ac y   o f   b id   v al u es  f o r   a  f air   au ctio n   i n   C lo u d   C o m p u ti n g   E n v ir o n m e n t .       6.   CO NCLU SI O N   I n   t h is   p ap er ,   w e  p r ese n ted   o n e  s c h e m e  to   f ac i litate  p r i v ac y   p r eser v i n g   a u ctio n   f o r   VM   in s tan ce s   allo ca tio n   w h er e  all  p ar ticip an ts   f o llo w   t h e  p r o to co l  an d   n o t h in g   ca n   b e  i n f er r ed   f r o m   o n e 's  i n p u t  a n d   o u tp u t.   T h is   p r o p o s ed   s ch e m e   ca n   b e   u s ed   to   g e n er ate  h ig h er   r ev e n u e  f o r   C SP   w it h o u t  d i s clo s i n g   t h e  b id   v al u e s   o f   d if f er e n t  u s er s   p ar ticip ated   i n   th e  a u ctio n   to   th e   au c tio n ee r   ( C SP ) .  Ou r   p r o p o s ed   a u ctio n   s ch e m e   w o r k   i n   t h e   s e m i - h o n e s t  m o d el  alo n g   w it h   t h e  ass u m p tio n   th at  a ll  p ar ticip an ts   ar e  f o llo w i n g   th e  p r o to co ls   th at  n ee d   f u r t h er   in v es tig a tio n .       RE F E R E NC E S     [1 ]   S a ra th y   V ,   Na ra y a n   P ,   M ik k il in e n i  R .   Ne x t  g e n e ra ti o n   c lo u d   c o mp u ti n g   a rc h it e c tu re   - e n a b li n g   re a l - ti me   d y n a mism   fo r  sh a re d   d istrib u ted   p h y sic a l  in fra stru c t u re .  1 9 t h   IE EE   I n tern a ti o n a l  W o rk sh o p s  o n   En a b li n g   T e c h n o lo g ies :   In f ra stru c tu re s f o r  Co ll a b o ra ti v e   En terp ris e s (W ET ICE’1 0 ),   L a rissa ,   G re e c e .   2 0 1 0 ;  4 8 - 53 .   [2 ]   Bu y y a a   R,   Ye o a   CS ,   V e n u g o p a l a   S ,   Bro b e rg a   J,  a n d   Bra n d icc   I .  Clo u d   c o m p u ti n g   a n d   e m e rg in g   IT  p latf o r m s:   V isio n ,   h y p e ,   a n d   re a li ty   f o r  d e li v e rin g   c o m p u ti n g   a s  th e   5 th   u ti li ty .   Fu tu re   Ge n e ra ti o n   Co mp u ter   S y ste ms .   2 0 0 9 ;   V o l u m e   2 5 (6 ) :  5 9 9 - 61 6 .   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 4 5   –   2 6 5 0   2650   [3 ]   T   S u ti k n o ,   D  S ti a w a n ,   IM I  S u b ro to ,   " F o rti fy in g   b ig   d a ta  in f ra s tru c tu re s  to   f a c e   se c u rit y   a n d   p riv a c y   is su e s , ”     T EL KOM NIKA  T e lec o mm u n ic a ti o n   C o mp u ti n g   El e c tro n ics   a n d   Co n tro l .,  v o l.   1 2 ,   n o .   4 ,   p p .   7 5 1 - 7 5 2 ,   2 0 1 4 .   [4 ]   M o h a n ty   S ,   P a tt n a ik   P K,  M u n d   G B.   Fra me wo rk   fo r   Au d it in g   i n   Clo u d   Co mp u ti n g   En v iro n me n t.   P ro c e e d i n g s   Jo u rn a l  o f   T h e o rit ica l  a n d   A p p l ied   In f o rm a ti o n   T e c h n o lo g y .   2 0 1 4 ;  V o l u m e   6 5 (1 ):   2 6 1 - 2 6 7 .   [5 ]   W a n g   R.   A u c ti o n s   v e rsu s p o ste d - p rice   se ll in g .   T h e   Ame ric a n   Ec o n o mic   Rev iew ,  1 9 9 3 ;  v o l.   8 3 ( 4 ):  8 3 8 – 8 5 1 .   [6 ]   S a str y   KN ,   Ra o   B T ,   G u n a s e k h a r  T .   No v e l  a p p ro a c h   f o r  c o n tro l  Da ta  T h e f t  A tt a c k   in   Cl o u d   C o m p u ti n g .   In ter n a t io n a l  J o u rn a l  o f  E lec trica l  a n d   C o mp u ter   En g in e e rin g   ( IJ ECE ) .   2 0 1 5 ;  V o l.   5 (  6 ) :  1 5 4 5 - 1 5 5 2 .   [7 ]   Zam a n   S,  G ro su   D.  Co m b in a to r ial  a u c ti o n - b a se d   a ll o c a ti o n   o f   v irt u a l  m a c h in e   in sta n c e s  in   c lo u d s.   J o u r n a l  o f   p a ra l lel  a n d   d istri b u ted   c o mp u ti n g .   2 0 1 3 ;  1 - 14 .   [8 ]   P ra sa d   V ,   Ra o   S ,   P ra sa d   A .   A   Co mb in a t o ria l   Au c ti o n   me c h a n ism  fo r  M u lt i p le  Res o u rc e   Pro c u r e me n t  in   Cl o u d   Co mp u t in g .   P ro c e d i n g s  o f   1 2 t h   I n tern a ti o n a l  C o n f e re n c e   o n   I n telli g e n t  S y s te m   D e sig n   a n d   A p p li c a ti o n .   2 0 1 2 ;  3 3 7 - 3 4 4 .   [9 ]   G a r g   S K,  V e n u g o p a l   S,  Bro b e rg   J,  Bu y y a   R.   Do u b le  a u c ti o n - in s p ired   m e tas c h e d u li n g   o f   p a ra ll e l  a p p li c a ti o n s  o n   g lo b a l  g rid s.  J o u rn a l  o f  P a ra ll e l   a n d   Distrib u ted   C o mp u ti n g .   2 0 1 3 ;  4 5 0 - 4 6 4 .   [1 0 ]   Zam a n   S,  G ro su   D.  A  Co m b in a to rial  A u c ti o n - Ba se d   M e c h a n ism   f o r  D y n a m ic  V M   P r o v isio n i n g   a n d   A ll o c a ti o n   in   Clo u d s.  IEE E  T ra n sa c ti o n s O n   Cl o u d   Co m p u ti n g .   2 0 1 3 ;  Vo l. 1 (2 ):  1 2 9 - 1 4 1 .   [1 1 ]   I  Ir m e il y a n a ,   I   In d ra w a ti ,   F M   P u sp it a ,   J  Ju n iw a ti ,   " M o d e l  a n d   o p ti m a l  so lu ti o n   o f   sin g le  li n k   p ricin g   sc h e m e   m u lt ise rv ic e   n e t w o rk , ”   T EL KOM NIKA  T e lec o mm u n ica t io n   Co mp u ti n g   E lec tro n ics   a n d   C o n tr o l. ,    v o l.   1 2 ,   n o .   1 ,   p p .   173 - 1 7 8 ,   2 0 1 4 .   [1 2 ]   Ch o i   Y,   L im   Y.  Op ti m i z a ti o n   A p p ro a c h   f o r  Re so u rc e   A ll o c a ti o n   o n   C lo u d   C o m p u ti n g   f o r  Io T .  In ter n a ti o n a l   J o u rn a l  o f  Distrib u ted   S e n so r Ne t wo rk s ,  2 0 1 6 ;   1 - 6 .     [1 3 ]   Ya o   A .   Pr o to c o ls   f o r  S e c u re   C o m p u tatio n s.   Pro c e e d in g s  o f  t h e   I EE E  S y mp o si u m  o n   f o u n d a ti o n s  o f   c o mp u ter   sc ien c e .   1 9 8 2 .   [1 4 ]   Ra b in   M O.  Ho w   to   Ex c h a n g e   S e c re ts  w i th   Ob li v io u s  T ra n sfe r.   T e c h n ica l  Rep o rt  T e c h . M e mo   T R - 8 1 , Ai k e n   Co mp u t a ti o n   L a b o r o to ry .   1 9 8 1 .   [1 5 ]   M o h a n ty   S ,   De   R.   S u rv e y   o n   P ri v a c y   P re se rv a ti o n   M e th o d o l o g y   i n   Kn o w led g e   Disc o v e r a b le  Clo u d   E n v iro n m e n t .   In ter n a t io n a l  J o u rn a l  o f   I n n o v a ti v e   a n d   Eme rg in g   Res e a rc h   i n   E n g in e e rin g .   2 0 1 7 ;  Vo lu m e   4 (3 ):  1 2 0 - 1 2 3 .     Evaluation Warning : The document was created with Spire.PDF for Python.