What is a Trapdoor in Merkle Signature?

Question

Merkle signature (pag. 40) use than public key (verification key) the root of the Merkle Tree and than private key (to sign) the set of pre-images of the $g(Y_i)$ where $Y_i$ is the verification key of a choose One Time Signature. My question is What's is a trapdoor between these two keys?

Answer 1

As I already outlined in this answer, hash trees in combination with any one-time signature scheme gives the so called Merkle signature scheme. I assume there is some misunderstanding and therefore I sketch merkle signatures subsequently:

The idea is to produce $n$ key pairs $(X_i,Y_i)$ of a one-time signature scheme and then to take the hash values $g(Y_i)$ of the public keys $Y_i$ (where $g:\{0,1\}^*\rightarrow \{0,1\}^n$ is a cryptographic hash function as described in your reference) and to assign the hash values $g(Y_i)$ to the leaves of a complete binary tree with $n$ leaves.

Then, you recursively compute up the hash tree (by computing hash values of inner nodes as the hash value of the concatenation of the child nodes) and finally as root hash you obtain your "public key" which is then given to a receiver. Let's call this public key $PK$ and observe that this is a "virtual" public key as it is not directly used for signature verification of the one-time signature scheme (I will come back to that soon). The private key is $(X_1,\ldots,X_n)$, i.e., the sequence of signing keys of the one-time signature scheme.

Then, this public key $PK$ allows the verification of $n$ one-time signatures. Each of these one-time signatures is produced using the private signing key $X_i$ of the one-time signature scheme.

Now, the basic idea is that you use signing key $X_i$ for the $i$'th signature and the $i$'th signature for message $m_i$ is composed of:

• the signature $\sigma_i$ obtained by signing $m_i$ with the signing algorithm of the chosen one-time signature scheme and signing key $X_i$.
• the authentication path $A_i$ in the hash tree for the leave $i$ with label $g(Y_i)$. This path consists of all the siblings on the unique path from the leaf $g(Y_i)$ to the root. This allows you given the public key $Y_i$ required to verify the one-time signature on $m_i$, to recompute the root hash of the hash tree (which is the public key $PK$) and compare it to the public key $PK$ which you received.

A signature $s$ for a message $m_i$ is then $s=(i,\sigma_i,Y_i,A_i)$. Note that when given $(s,m_i)$ and being in possession of $PK$, for verifiying one checks whether:

• $\sigma_i$ is a valid one-time signature for $m_i$ under public key $Y_i$
• and the recomputation of the hash tree using the hashed public key $g(Y_i)$ (by hasing the public key $Y_i$ from the signature $s$) and the authentication path $A_i$ results in a root hash that is equal to $PK$.

I hope this answers your question and you see that there are no trapdoors involved with $g$ and $Y_i$. Essentially, the hash tree is used to aggregate $n$ public keys of a one-time signature scheme into a single "virtual" public key $PK$. Thus, this public key $PK$ allows to verify $n$ signatures. How the values $X_i$ and $Y_i$ are related depends on the used one-time signature scheme, but has nothing to do with the hash tree.