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