Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
Could you add a reference to your copied image? – Paŭlo Ebermann Jul 6 '13 at 11:20
yes Introduction to Modern Cryptography of Jonathan Katz and Jehuda Lindell – juaninf Jul 6 '13 at 21:01
up vote 3 down vote accepted

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$.

share|improve this answer
Is then every bit-string $x_{i,b}$ choosen randomly? – juaninf Jul 4 '13 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 '13 at 17:55
understand and another question. Why the algorithm need the verification "if ${m_i^{*}}^{'}=b^{*}$"? – juaninf Jul 4 '13 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 '13 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 '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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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