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?

  • $\begingroup$ Could you add a reference to your copied image? $\endgroup$ – Paŭlo Ebermann Jul 6 '13 at 11:20
  • $\begingroup$ yes Introduction to Modern Cryptography of Jonathan Katz and Jehuda Lindell $\endgroup$ – juaninf Jul 6 '13 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$.

| improve this answer | |
  • $\begingroup$ Is then every bit-string $x_{i,b}$ choosen randomly? $\endgroup$ – juaninf Jul 4 '13 at 15:22
  • $\begingroup$ "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 $\endgroup$ – rath Jul 4 '13 at 17:55
  • $\begingroup$ understand and another question. Why the algorithm need the verification "if ${m_i^{*}}^{'}=b^{*}$"? $\endgroup$ – juaninf Jul 4 '13 at 18:24
  • $\begingroup$ $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. $\endgroup$ – tylo Jul 30 '13 at 14:57
  • $\begingroup$ 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$. $\endgroup$ – tylo Jul 30 '13 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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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