Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
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.
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.
