*Multiplication Laws*

#
All 1 entries tagged

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,

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
*X*_{0}be the vector encoding the target image (the butterfly above). Generate entirely random independent vectors*X*,_{1}*X*_{2}, ...,*X*_{n}_{-1}*n*-1 students.

- Student
*n*is given an image corresponding to the vector*X*obtained by multiplying (coordinate-wise) all the other vectors:_{n}

*X*_{n}=*X*_{0}**X**_{1}*X*_{2}* ... **X*_{n}_{-1 }where "*" denotes coordinate-wise multiplication. - It is simple arithmetic that
*X*_{0}*=**X*_{n}**X**_{1}*X*_{2}* ... **X*_{n}_{-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*X*,_{1}*X*_{2}, ...,*X*, 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}*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.