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.

## No comments :

Post a Comment