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
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,
and yet if all images are combined together in the right way then a meaningful picture emerges.
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?
- 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.
- 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.
- 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.
- It is simple arithmetic that X0 = Xn* X1 * X2 * ... * Xn-1. So all students working together possess the information to recover the butterfly image.
- 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.