Skip to Content
Uncategorized

Mathematicians Encrypt Images Using Mathematics of Sudoku

State-of-the-art image scrambling algorithm uses a new type of matrix mathematics based on Sudoku puzzles

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. 

Sudoku has thrown up a number of interesting challenges for mathematicians. Earlier this year, for example, we looked at how mathematicians had solved the ‘minimum Sudoku problem’ to find the smallest number of clues that leads to a unique solution (answer, 17).  

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).

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 9x9 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. 

Amazing what Sudoku can do for humankind!

Ref: arxiv.org/abs/1207.5856: Sudoku Associated Two Dimensional Bijections for Image Scrambling 

Keep Reading

Most Popular

A view of clouds illuminated by sunlight
A view of clouds illuminated by sunlight

We can’t afford to stop solar geoengineering research

It is the wrong time to take this strategy for combating climate change off the table.

conceptual illustration showing various women's faces being scanned
conceptual illustration showing various women's faces being scanned

A horrifying new AI app swaps women into porn videos with a click

Deepfake researchers have long feared the day this would arrive.

Death and Jeff Bezos
Death and Jeff Bezos

Meet Altos Labs, Silicon Valley’s latest wild bet on living forever

Funders of a deep-pocketed new "rejuvenation" startup are said to include Jeff Bezos and Yuri Milner.

ai learning to multitask concept
ai learning to multitask concept

Meta’s new learning algorithm can teach AI to multi-task

The single technique for teaching neural networks multiple skills is a step towards general-purpose AI.

Stay connected

Illustration by Rose WongIllustration by Rose Wong

Get the latest updates from
MIT Technology Review

Discover special offers, top stories, upcoming events, and more.

Thank you for submitting your email!

Explore more newsletters

It looks like something went wrong.

We’re having trouble saving your preferences. Try refreshing this page and updating them one more time. If you continue to get this message, reach out to us at customer-service@technologyreview.com with a list of newsletters you’d like to receive.