## 3 Information Leakage Analysis of Merkle Tree-Based Authentication Schemes
### Previous Schemes and Their Vulnerabilities
#### 3.2.4 Merkle Tree-Based Authentication with Transmission in Encrypted Form
Theorem 1: **(Security of Merkle tree-based authentication)** _Given a randomly chosen leaf index, the probability that an adversary without knowledge of the entire tree (data) can forge a valid sibling path is negligible if a cryptographic (specifically, preimage-resistant) hash function is used to construct the tree._

Proof: Suppose that there is an adversary who knows the number of leaf nodes and the value of the root node in the Merkle tree generated from the target data. For the adversary to pass validation, it has to find a preimage of the root node with a bit-length twice that of the hash value. Regarding each half of the discovered preimage as children of the target node, the adversary has to repeatedly search for preimage of each half until the preimage corresponds to the leaves (i.e., \(\lceil\log n\rceil\) times, where \(n\) is the number of leaf nodes in the tree). However, this contradicts the assumption that each hash value is an output of the cryptographic hash function. Therefore, the probability of the adversary forging a valid proof is negligible as long as a cryptographic (specifically, preimage-resistant) hash function is used to build the Merkle tree. Formal security model and proof of unforgeability for Merkle tree-based authentication can be found in [20; 34; 35; 36]. ### Security of the Proposed Scheme

The data authentication process can be completely bypassed if eavesdropping is performed on the initial transmission of the underlying data. As noted in [35], the reliability of online authentication is weakened through extra information gathered by eavesdropping unless the Merkle tree is combined with private keys. In short, one-time online authentication is reliable only when a Merkle tree is used without modification. However, since this data transmission is performed at most once and subsequent data authentication can be conducted several times, the general assumption that the initial data is transmitted through a secure channel if necessary is reasonable. #### 5.2.1 Security of One-time Secret Delivery

One simple way to improve security and reliability is to have the prover \(\mathcal{P}\) and the verifier \(\mathcal{V}\) agree on an extra shared secret additional to the Merkle tree itself. To achieve this, we devise a one-way secret delivery mechanism following Definition 2. Definition 2: **(One-way secret delivery)** Let two parties, say \(\mathcal{A}\) and \(\mathcal{B}\), share secret information shared of bit-length \(\lambda\). \(\mathcal{A}\) can send another secret value toShare to \(\mathcal{B}\) by embedding toShare in shared such that

\[transmitted=shared\oplus\text{toShare}\]

where \(\oplus\) represents a bitwise exclusive-or (XOR) operation and transmitted is data transmitted via a public channel. The recipient \(\mathcal{B}\) can then recover the secret key such that

\[toShare=transmitted\oplus shared.\]Specifically, every time the prover \(\mathcal{P}\) tries to convince the verifier \(\mathcal{V}\), \(\mathcal{P}\) can choose a uniform random mask and securely send it to \(\mathcal{V}\) by exploiting the one-way secret delivery mechanism in the proposed scheme. This can be achieved by embedding the mask in the shared value, which is the value of the root node in the Merkle tree such that \(transmitted=mask\oplus MT_{D}^{root}\), where \(mask\) and \(MT_{D}^{root}\) are a mask randomly chosen by \(\mathcal{P}\) and the value of root node shared between \(\mathcal{P}\) and \(\mathcal{V}\), respectively. The one-way secret delivery mechanism can be thought of as a one directional password-authenticated key exchange (PAKE), in which the previously shared information is considered to be a password [37]. Prior to examining the security of the proposed scheme, notice that the result of the bitwise-exclusive (XOR) operation of a random value is also random regardless of other operands. Let \(X,Y\in\{0,1\}\) be random variables, where \(Pr[X=0]=Pr[X=1]=1/2\) and \(Y\) is drawn from any distribution.