Download
swarming secrets n.
Skip this Video
Loading SlideShow in 5 Seconds..
Swarming Secrets PowerPoint Presentation
Download Presentation
Swarming Secrets

Swarming Secrets

87 Views Download Presentation
Download Presentation

Swarming Secrets

- - - - - - - - - - - - - - - - - - - - - - - - - - - E N D - - - - - - - - - - - - - - - - - - - - - - - - - - -
Presentation Transcript

  1. Swarming Secrets ShlomiDolev (BGU), Juan Garay (AT&T Labs), NivGilboa (BGU) Vladimir Kolesnikov (Bell Labs) Allerton 2009

  2. Talk Outline • Objectives • Adversary • Secret sharing • Membership and thresholds • Private computation in swarms • Perfectly oblivious TM • Computing transitions

  3. Objectives • Why swarms • Why secrets in a swarm • Dynamic membership in swarms • Computation in a swarm

  4. Adversary • Honest but curious • Adaptive • Controls swarm members • Up to a threshold of t members • What about eavesdropping? • We assume that can eavesdrop on the links (incoming and outgoing) of up to t members

  5. Secret sharing Y Share of Player i Bivariate Polynomial P(x,y) i P(x,i) P(i,y) Share of Player i j P(i,j) X i

  6. Join Hey Guys, can I play with you? I’m J! PA(J,y), PA(x,J) D C PC(J,y), PC(x,J) J PB(J,y), PB(x,J) PA(J,y), PA(x,J) Sure! B A

  7. Leave • Problem: • Member retains share after leaving • Adversary could corrupt leaving member and t current members • Refreshing (Proactive Secret Sharing) • Each member shares random polynomial with free coefficient 0

  8. Additional Operations • Merge • Split • Clone

  9. Increase Threshold • Why do it? • How – simple, add random polynomials of higher degree with P(0,0)=0

  10. Decrease Threshold- t to t* B, C, D, … also share random polynomials D C Choose random, Degree t* QA(x,y) J Share of QA(x,y) Share of QA(x,y) B Share of QA(x,y) Share of QA(x,y) A

  11. Decrease Threshold- t to t* Add local shares Add local shares D C Remove high degree terms Interpolate Add local shares Add local shares J B P(x,y) + QA(x,y) + QB(x,y) +… R(x,y) Add local shares A

  12. Decrease Threshold- t to t* Compute reduced P D C Compute reduced P High mon. Of P High mon. Of P High mon. Of P High mon. Of P Compute reduced P J B Compute reduced P Compute reduced P A

  13. Computation in a Swarm • A distributed system • Computational model • Communication between members • Input – we can consider global and non-global input • Changes to “software” • “Output” of computation when computation time is unbounded

  14. What is Hidden • Current state • Input • Software • Time What is not Hidden? • Space

  15. How is it Hidden? • Secret sharing • Input • State • Universal TM • Software • Perfectly oblivious universal TM • Time

  16. Architecture of a Swarm TM

  17. Perfectly Oblivious TM Perfectly Oblivious TM Tape head     Oblivious TM – Head moves as function of number of steps Perfectly Oblivious TM – Head moves as function of current position

  18. Perfectly Oblivious TM Perfectly Oblivious TM     Tape shifts right, copy  that was in previous cell Tape        Orig. Tape Head N N Y N Transition: (st, )(st3,,left) Transition: (st, )(st1,,left) Transition: (st, )(st2,,right) Tape shifts right, head shifts left, Y stays in place, copy  Insert result of “real” transition, 

  19. TM Transitions States Transition Table st1 1 …  … st2 st1 … ns … … st st ns, … …     … Tape head Tape

  20. Encoding States & Cells States st1 10…0 st2 01…0 … 0…010…0 st 0…010…0 … index  index st    … Tape

  21. Computing a Transition • Goal, Compute transition privately in one communication round • Method, Construct new state/symbol unit vector, ns/n, from • Current state - st • Current symbol -  • ns[k]=st[i] [j], for all i, j such that a transition of (i, j) gives state k • Construct new symbol vector in analogous way n[k]= st[i] [j], for all i, j such that a transition of (i, j) gives symbol k

  22. Encoding State Transitions Current Transition Transition Table 0 … 1 0  …   0 0*0 0*1 0*0 st1 ns, st1, St1, 0*0 0*1 0*0 ns, st1, St1, … … 1 1*0 1*1 1*0 st St2, ns, ns, 1*0 1*1 1*0 St2, ns, ns, 0 0*0 0*0 0*1 0*1 0*0 0*0 st2 ns, ns, St2, St2, st2, st2, 0*0+0*1=0 … 0*0+0*0+1*1+1*0=1 1*0+0*1+0*0=0 0…010…0 New state is ns

  23. Encoding Symbol Transitions Current Transition Transition Table 0 … 1 0  …   0 0*0 0*1 0*0 st1 ns, st1, St1, 0*0 0*1 0*0 ns, st1, St1, … … 1 1*0 1*1 1*0 st ns, ns, 1*0 1*1 1*0 St2, St2, ns, ns, 0 0*0 0*1 0*1 0*0 0*0 st2 ns, ns, St2, St2, st2, st2, 0*0 0*0+0*1=0 … 1*0+0*0+0*0+1*0=0 0*1+1*1+0*0=1 0…01 New symbol is 

  24. What about Privacy? • Goal: compute transitions privately • Method • Compute new shares using the st[i] [j], • Reduce polynomial degree

  25. Sharing States & Symbols • Initially • Encode 1 by P(x,y), P(0,0)=1 • Encode 0 by Q(x,y), Q(0,0)=0 • Share bivariate polynomials for state and symbol • Step • Compute 0*0+ 1*0+ 1*1… by • Multiplying and summing local shares • Running “Decrease” degree protocol

  26. Thank You!!!