1
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ Could you add a reference to your copied image? $\endgroup$
    – Paŭlo Ebermann
    Jul 6, 2013 at 11:20
  • $\begingroup$ yes Introduction to Modern Cryptography of Jonathan Katz and Jehuda Lindell $\endgroup$
    – juaninf
    Jul 6, 2013 at 21:01

2 Answers 2

Reset to default
3
$\begingroup$

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
$\endgroup$
5
  • $\begingroup$ Is then every bit-string $x_{i,b}$ choosen randomly? $\endgroup$
    – juaninf
    Jul 4, 2013 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, 2013 at 17:55
  • $\begingroup$ understand and another question. Why the algorithm need the verification "if ${m_i^{*}}^{'}=b^{*}$"? $\endgroup$
    – juaninf
    Jul 4, 2013 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, 2013 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, 2013 at 15:01
2
$\begingroup$

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
$\endgroup$

Your Answer

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

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