All 1 entries tagged Multiplication Laws

No other Warwick Blogs use the tag Multiplication Laws on entries | View entries tagged Multiplication Laws at Technorati | There are no images tagged Multiplication Laws on this blog

September 12, 2017

Secret–sharing and independence

The following remarkable procedure is entirely feasible: if I have a class of n students then I can distribute n different binary images, one to each student, such that each student's image looks like white noise,

typical image distributed to a student: just white noise!

and yet if all images are combined together in the right way then a meaningful picture emerges.

result of combining all images using multiplication (if black pixels are coded as -1 and white pixels are coded as -1)

What's more, I can arrange matters such that if any strict subset of the n students tried to collaborate, then all they would get would be more white noise, no matter how they manipulated their n-1 images!

So any strict subset of the students would possess no information at all about the butterfly picture, but combined all together they would be in a position to produce a perfect reproduction of the image.

How can this be done?

  1. Code each black pixel of each image as -1, each white pixel as +1, and view each distributed image as a long vector sequence of +/-1 values.
  2. Let X0 be the vector encoding the target image (the butterfly above). Generate entirely random independent vectors X1, X2, ..., Xn-1 and distribute the corresponding white noise images to the first n-1 students.
  3. Student n is given an image corresponding to the vector Xn obtained by multiplying (coordinate-wise) all the other vectors:
    Xn = X0* X1 * X2 * ... * Xn-1
    where "*" denotes coordinate-wise multiplication.
  4. It is simple arithmetic that X0 = Xn* X1 * X2 * ... * Xn-1. So all students working together possess the information to recover the butterfly image.
  5. On the other hand one can use elementary probability to show that, if one selects any subset of size n-1 of the vectors X1, X2, ..., Xn, then this subset behaves as if it is a statistically independent collection of vectors corresponding to white-noise images. (It suffices to consider just one pixel at a time, and show that the corresponding sequence of n-1 random +/-1 values obey all possible multiplication laws.) So no strict subset of the students has any information at all about the butterfly image.

There are many other ways to implement secret-sharing (Google/Bing/DuckDuckGo the phrase "secret sharing"). But this one is nice for probabilists, because it provides a graphic example of why pairwise independence (independence of any two events taken from a larger collection of events) need not imply complete independence.

April 2020

Mo Tu We Th Fr Sa Su
Mar |  Today  |
      1 2 3 4 5
6 7 8 9 10 11 12
13 14 15 16 17 18 19
20 21 22 23 24 25 26
27 28 29 30         

Search this blog


Most recent comments

  • The paper includes a nice example of application of a log–normal distribution, which is used to mode… by Wilfrid Kendall on this entry
  • See also their webapp by Wilfrid Kendall on this entry

Blog archive

RSS2.0 Atom
Not signed in
Sign in

Powered by BlogBuilder