# Lamport-Diffie + attempting to invert OWF

I am studying Lamport-Diffie signature scheme and in my lecture present the follow algorithm for attempting to invert the one way function $f$, where $f$ is used to compute the public key of this signature from the private key $sk=\left(\begin{array}{rrrrrr} x_{1,0} & x_{2,0} & \cdots & x_{l,0} \\ x_{1,1} & x_{2,1} & \cdots & x_{l,1} \end{array}\right)$. My question is Why will be possible execute the sentence 2, if $x_{i,b}$ are part of private key? • Could you add a reference to your copied image? Jul 6, 2013 at 11:20
• yes Introduction to Modern Cryptography of Jonathan Katz and Jehuda Lindell Jul 6, 2013 at 21:01

The only requirement is $i,b \neq i^*,b^*$ where $i^*$ is a random value from $1$ to $l$ and $b^* \gets\{0,1\}$ So if $b^*=0$ then $b=1$.

Don't get confused by the $x$, it has nothing to do with the secret key, it's just a variable that later becomes $y_{i,b}=f(x_{i,b})$. It could as well be called $a$.

• Is then every bit-string $x_{i,b}$ choosen randomly? Jul 4, 2013 at 15:22
• "For all $i \in \{1,...,l\}$", with $i \neq i^*$. I do believe every $x_{i,b}$ is chosen arbitrarily but I may be missing something
– rath
Jul 4, 2013 at 17:55
• understand and another question. Why the algorithm need the verification "if ${m_i^{*}}^{'}=b^{*}$"? Jul 4, 2013 at 18:24
• $x_{i,b}$ are all chosen randomly except when both $i=i*$ and $b=b*$ (at the same time). And these $x_{i,b}$ are chosen as secret key for a Lamport-Diffie signature scheme.
– tylo
Jul 30, 2013 at 14:57
• About the condition "if $m_^{i^*}' = b^*$, stop.": We play the role of the signing oracle for the algorithm $\mathcal{A}$. But we can not answer those queries, because the public key was defined in a way, that this query can only be answered with a preimage of $y$ under $f$.
– tylo
Jul 30, 2013 at 15:01

This is the algorithm from your other question Lamport-Diffie + Security Proof , I guess.

What happens here is this:

• We create a special public and secret key for a LD-Sign Scheme: We choose $x_{i,b}$ randomly for all but one single entry (which is $x_{i^*,b^*}$) and this is our secret key. In the public key we just apply $f(x)$ to all randomly chosen values. And the one empty entry is set to our challenge $y$.
• We assume that the algorithm $\mathcal{A}$ exists, which gets the public key and can ask the oracle for signatures.
• We play the role of the oracle. This is no problem for half of the queries: If creating a signature does not require the preimage of $y$, we can do this. If we would have to answer with the preimage of $y$, we just start over.
• We hope the final forgery of the attacker $\mathcal{A}$ contains the preimage of $y$, which has a chance of 50%.

This PPT is able to answer preimage queries for $f$, but it depends on the existance of $\mathcal{A}$. There is nothing else involved: If $\mathcal{A}$ exists, so does $\mathcal{I}$. However, if we assumpe, that $f$ is one-way, then $\mathcal{I}$ must not exist. And therefore $\mathcal{A}$ must not exist.