[updwpzxm] Puzzles known to be solvable

Factoring integers and computing discrete logarithms are two types of puzzles in which the person attempting to solve it (the attacker) can know for sure there is a solution, can know for sure that he or she has found the correct solution when found (complexity class NP: checking a candidate solution can be done efficiently), yet the puzzle remains difficult.  What else has these properties?

SAT, for example, does not have these properties: it is difficult to tell if an instance has any solution.

For the RSA problem, can the attacker quickly determine that a given ciphertext number actually is some perfect cube (or perfect 65537th power) mod N?  Actually, I think all ciphertext numbers can be deciphered: the decryption exponent can be applied to any number.

The key recovery problem for a symmetric cipher typically will not have the properties listed above.  Given a plaintext-ciphertext pair, there could be no key which makes it, but an attacker cannot tell.  Maybe the puzzle was miscopied.

For integer discrete logarithm, use a safe prime so that the attacker can quickly verify that the base of the exponentiation is a generator for the finite group.  Is there an analogous procedure for ECC discrete logarithm?

Inspired by futile efforts to solve flawed puzzles which had no solutions.