I was reading about a Polly Cracker encryption scheme based on the graph 3-coloring problem. Aren't Latin squares just a form of the same problem? If so, does this mean Sudoku can be used for public/private key encryption?

  • 1
    Yes, and I am sure it is even used as an example in one of the crypto materials that I read - I'll be danged if I know the source though. Of course, a 9x9 Sudoku would not work; you'd have to greatly expand the dimensions. My Sudoku solver program can solve any evil rated 9x9 Sudoku in 0.1 seconds, and that's just the startup time of the Java VM - not the calculation itself. – Maarten Bodewes Sep 24 at 14:03
  • Dang, I would have liked to read your source :( – Meler Lawler Sep 24 at 18:41
up vote 5 down vote accepted

Sure. How efficient vs secure is another matter.

Look up Merkle's puzzles, as well. A latin square as a higher dimensional object can be related to differential properties of good mappings.

  • Would you have any sources that describe how to actually implement a Sudoku (or any Latin square) as an asymmetric encryption scheme? I only have a vague notion of how it would work. – Meler Lawler Sep 24 at 18:46

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.