All 1 entries tagged Multiplication Laws

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,

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?

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 X₀ be the vector encoding the target image (the butterfly above). Generate entirely random independent vectors X₁, X₂, ..., X_n-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 X_n obtained by multiplying (coordinate-wise) all the other vectors:
   X_n = X₀* X₁ * X₂ * ... * X_n-1
   where "*" denotes coordinate-wise multiplication.
4. It is simple arithmetic that X₀ = X_n* X₁ * X₂ * ... * X_n-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 X₁, X₂, ..., X_n, 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.

Wilfrid Kendall : 12 Sep 2017 16:12 |  Tags: Encryption Independence Motivation Multiplication Laws St220 |  Comments (0) |  Close comments |  Report a problem