The number-placement puzzle, Sudoku, consists of a 9 x 9 grid which must be filled using the digits 1 to 9.
However, there are several additional constraints. Each digit can only appear once in each column, once in each row and once in each of the nine 3 x 3 blocks that make up the grid. A Soduko solution grid is shown below. Players are given a number of digits from the solution to get the game started.
Today, Yue Wu at Tufts University in Medford and a couple of buddies use Sudoku to tackle a different problem–how to encrypt images before sending them.
These guys say that the special properties of Sudoku grids lead to an entirely new type of matrix mathematics that they’ve exploited to scramble images.
First, a little background about matrices. A matrix is simply a rectangular array of numbers. Each element in the array is uniquely identified by a grid reference–its column and row number.
But Wu and co say it is possible to identify elements in an array in other ways if you think of it as a Sudoku grid. In that case, each element contains a digit from 1 to 9 that satisfies the rules of Sudoku. In other words, in addition to the row and column, each element also has a digit.
So in the above grid, the element in the first row and first column (1,1) is also associated with the digit 8, element (1,2) is associated with 7, element (1,3) with 4 and so on.
What’s more each element is also associated with a 3 x 3 block, numbered as shown in the grid above. So element (1,1) is associated with block 1, element (2,8) with block 7 and element (8,5) with block 6 and so on.
That makes it possible to identify each element in other ways. So the element in block 5 containing the digit 9 is element (4,5) in conventional notation; the element in column 3 containing digit 7 is (8,3) in conventional notation and the element in row 6 containing 2 is (6,9).
Advertisement
In total, there are six different ways of representing each element, say Wu and co. Each of these systems is equivalent and it is possible to convert the coordinates from one system to another using a set of simple mathematical conversion functions.
These conversion functions are the key to scrambling images. Begin with an image made up of 9×9 pixels. Next superimpose a Soduko solution onto this grid so that each pixel can now be represented by the new coordinate systems.
Now, applying one of the conversion functions to the grid, swaps the position of pixels, jumbling up the image.
What Wu and co have discovered is how to apply a short sequence of conversion functions that completely scrambles the image. That’s useful because it’s entirely deterministic and yet produces a seemingly random result (as shown in the top image).
This is equivalent to a kind of encryption in which the original Sudoku solution is the key. (For larger images you simply tile the image with several Sudoku grids.)
Wu and co have done some initial comparison between their method and other image scrambling algorithms and say it matches or outperforms them.
And since for a 256 x 256 image, there are at least 256!=2^1684 possible Sudoku matrices, it’s not easy for an adversary to hit on the solution by accident or even by brute force.
Wu and co make no claims about its potential security but there is clearly room for further exploration here.
Advertisement
Amazing what Sudoku can do for humankind!
Ref: arxiv.org/abs/1207.5856: Sudoku Associated Two Dimensional Bijections for Image Scrambling
