Mathematicians Encrypt Images Using Mathematics of Sudoku | Hacker News Reader

Mathematicians Encrypt Images Using Mathematics of Sudoku

technologyreview.com

32 pointsColinWright18 comments

This seems silly. They "use Sudoku to tackle a different problem--how to encrypt images before sending them".

You know what else works for encrypting images before sending them? Any other encryption algorithm.

Who cares if your "encrypted" image is still an image? Doesn't that kind of defeat the point of encryption? It's obviously just a scrambled image, leaving only the question of what the unscrambled image is. If someone was planning on sending illegal or sensitive images with this, you could probably still easily guess what the nature of the original image was.

It's not like steganography where you don't know there's a message there, or normal encryption where you have no guess as to what produced the cyphertext or what the payload is.

Yes - I couldn't believe it when I read the article. This is like - "Create any random permutation matrix. Use it to permute all the pixels. Done."

Or, use any encryption algorithm and set the key to be your Sudoku grid.

I'm not sure why the authors are concentrating on 'Sudoku' (which would perhaps better be called a Latin square in this context) because I can't see that they need the property that each 'number' appears once per row and column.

If they want in place image scrambling using grids, can't they just generate a random grid that mixes up the pixels in a square from any (x,y) to some other (x',y') in the same square? They can still arrange for this to be a bijection, it's trivial.

Perhaps they could Google 'permutation matrix'.

The interesting thing is how you generate the grids, and for that to be secure you'd need some cryptographic method. In which case you might just as well encrypt in the first place.

I'm certain that the Sudoku part is a hook, to bring in more viewers and then keep them for a bit. And although the site is called technology review, it is basically just a general audience site so concepts like permutation matrix would be lost on the audience and massacred by the time pressed journalists. This comes down to a trade off.

You want to draw people in and show them how cool modern tech is, but if you make it too much like a lecture you don't reach as many people. I think this trade off is okay, people who are attracted and care will unlearn and those who don't care will forget but still have a general idea of science as awesome. E.g. I used to read NewScientist although now I see much of it is garbage. That stuff can't be much more damaging than non-hard scifi and comics IMO. The only site that makes me angry is ScienceDaily and not for their horrid site design.

Color me extremely skeptical until I see a rigorous security proof. Fun little schemes like this are a dime a dozen, and often are essentially useless for any real application.

FTA: "Wu and co make no claims about its potential security but there is clearly room for further exploration here. "

They need to be more careful about using the word 'cryptography' then. Sure, crypto people and informed laypersons know this is hopelessly insecure, but all it takes is one overzealous intern implementing this in a banking application to cause a huge problem.

The only word I see is "encrypt", but regardless, this IS cryptography - converting to a code. You can encrypt with a Ceaser cipher, though it's not terribly secure.

Indeed. It's a clever convolution filter, but all you have to do is look at the resulting image to see some weaknesses. The naive tiling approach is even worse. So let's say I wanted to find the image on the Internet that most likely represented the original of some "sudoku encrypted" image?

1. Throw out any images that are strictly smaller than the cipher image. This technique doesn't do any compression

2. Throw out any images that are larger or of a significantly given aspect ratio than the cipher image, based on how many more pixels could have possibly been added to complete the sudokus on each edge

3. Compare the color histogram or some precise additive hash of color values from the cipher image to some candidate image. If the values differ, reject the candidate. This should work because the algorithm as described only seems to shuffle pixels locally in a tile. So the convolution should still have the exact same overall color frequencies. Edges where some pixels might have been filled in may have to be treated differently.

4. Continue this process until you have a reasonably short result of candidate images

You could easily solve many of these issues by using the filter to shift both space and color values and by recursively applying the shuffling process to larger and larger blocks of the image, but certainly the procedure as described in the linked article sounds suspect.

I could actually see this being researched for compression as well as encryption. Maybe try some sudoku convolutions and see if they compress better. If so, compress that image along with the sudoku solution. I doubt it would work but it might be worth a look.

Since a sudoku puzzle implies it's solution, it is a highly compress(able) representation of the solution. I wonder if it might be possible to leverage this sort of rule based matrix to improve compression algorithms, or if compression algorithms are already more optimal than this.

That was my thought as well (see my comment elsewhere in the thread). I wonder if this could be used as some kind of fixed sparsity encoding?

I'm no expert but just an thought:

A sodoku puzzle(requiring only 17 digits for an unique solution) which has an single solution isn't exactly useful for compression.

How I am thinking about this? The article states:

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

Compression would make sense if the number of puzzles was something like 1684, but it is here 2^1684!! Which is quite a lot and to be decoded would be even worse than the image itself.

The sodoku puzzle's compression would not be of any practical use not only because they give the data more problems to account for but also because the data would need to be interpreted.

Also anything that uses encryption generally does the complete opposite of compression.

For sure it increases the computational power required to decompress, but that does not preclude its usefulness. Sometimes computation is cheap and bandwidth is expensive, as perhaps when sending messages to distant stars.

This is really cool to me. But it makes sense. It just uses a unique numbering system. I suppose instead of adding a new tens or thousands placeholder to increase the number, you just add a new grid reference. Pretty cool really.

edit: I guess it's basically a base-9 numbering method, yes?

If I'm understanding the technique correctly, it seems very likely that you could use statistical properties of natural images to guess at partial unscramblings, progressively rebuilding the image in far better than brute force time.

A bit of Googling also reveals that some Sudoku puzzles are invertible, so it sounds like in addition to this problem, you'd better pick your sudoku solution carefully, as it might be possible to recover the key if the number of candidate images is small.

One could exploit the continuity of the image regions. (The similarity of neighbors in intensity and colors). Also the output is an image with the same histogram ...

Wow this is quite stupid for this application. When I read the title I thought along the lines of compression by 'solving' the sudoku.

Reply on news.ycombinator.com