All entries for Tuesday 12 September 2017

September 12, 2017

The secret of success?

This TED talk makes a lot of sense to me, and chimes in with more than 35 years of lecturing experience. Have a look and see what it suggests to you.


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.


September 2017

Mo Tu We Th Fr Sa Su
Aug |  Today  | Oct
            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

Galleries

Most recent comments

  • More recently I have noticed the following elementary fact about convergence in probability. Suppose… by Wilfrid Kendall on this entry
  • Thanks to Martin Emil Jakobsen for pointing out a typo in the example of conditioning on a single ev… by Wilfrid Kendall on this entry
  • 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 https://045.medsci.ox.ac.uk/ by Wilfrid Kendall on this entry

Blog archive

Loading…
Not signed in
Sign in

Powered by BlogBuilder
© MMXXIV