I am studying reductions to prove security of crypto systems. Generally "games" are used for the proofs. For example, the next image was extracted from the page 91 of the book Post-Quantum Cryptography. Here, an adversary is constructed against Lamport-Diffie signature using a Forger with access to an oracle.

My question is why is it permitted to the adversary to generate keys? I make this question because the step 1 of this Algorithm calls the key generation process.

enter image description here


2 Answers 2


The adversary is permitted to generate the keys
because we're not restricting the adversary's internals.

(For example, the adversary is also permitted to compute the parity of y,
and to generate a random element of {45,56,62,68}.)


The problem is that you do not get the idea of a reduction. The goal of the reduction is to prove that we can use a forger against LD-OTS to find preimages in the used hash function. I.e. the reduction is an algorithm that finds preimages using the forger as a subroutine. Now, as we know how hard preimage search is (we assume for a secure n-bit hash function that it takes $2^n$ queries to that function), we know that the reduction algorithm cannot do better than this. Consequently, if the reduction has approximately the same runtime as the forger and approximately the same success probability, this also tells us that the forger cannot be more efficient than a generic preimage finder.

So, the reduction is not breaking the signature scheme but the one-wayness of the scheme and hence, there is no problem with the reduction knowing the used key pair. Indeed, the reduction has to generate a valid key pair to run the forger.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.