On-Line score - how to prevent cheating ?

In addition to encryption, it might be a good idea to send additional information along, which lets you verify if the score is likely to be valid. This would depend on the game of course, but things such as which level the player has reached or how long they played etc. is an easy way of checking if a score is valid.

And that if people cheat, then at least it's within the limits of what it is possible to score in the game.