I thought yesterday that I’d invented a whole new use for cellular automata in cryptography…but of course there is already an entire discipline devoted to this idea.
My non-invention was that you start with a pixel pattern (binary works best because without colours, neighbours aren’t correlated). Use this as the start field for a CA (like Conway’s Game of Life, except that the rules can be run backwards as well as forwards. In Life, you can end up with only a few blinking pixels which can’t ever be used to regenerate the original field, so it’s not reversible. A reversible one is something like a model of an ideal gas in which a sequence of collisions can be traced backwards and forwards forever with perfect precision). Run the reversible CA for 100,000 cycles or so. Send the scrambled image to someone who knows the reversible rules (which can be ultra hard to guess). Tell them how many cycles to run it backwards for and they can regenerate the original image/text.
Sadly, today’s invention is just a small-scale application of this approach. I imagine ‘a spot the ball’ competition, run as an online, viral campaign. You send your friend a link to an applet. This contains a scrambled image -with one pixel inverted from black to white. The applet will allow the friend to darken one pixel of their choice and run backwards by a large number of steps automatically. Only if they choose the correct pixel to turn on will the original screen, “You have won $1M,” appear.
