It seems to me as if the returned results have to be sorted alphabetically, which is not stated in the instructions.

This could be just a side-effect of how you generate the list of possible deciphered strings, but I have to sort in order to pass the tests.

Typo in template code - missing ':' at the end of the first line. Which took a while to spot.

The random tests fail if you remove "import string" from the template code.

Not exactly a duplicate, as this version allows spaces and punctuation in the strings, which spices things up a bit.

Looks good. Only thing would be to explicitly say what should be done with a key bigger than 26. (This is obvious from the test cases, but not mentioned in description, so I initally rejected such keys as invalid).

What to return if the value passed to the function is not a valid character name?

Otherwise, a good simple example of using a dictionary. Should solutions that do not use a dictionary be accepted as correct?

Make it clear in the description that spaces do not matter, so it is not simply a case of "is this string the same when reversed". Also make it clear that capitalisations do not matter.

These are both clear from the third test case given, but making them explicit would be good.