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