## 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
The distribution for \(X\oplus Y\) is also random as long as \(Y\) is independent of \(X\) such that

\[Pr[Y=y|X=x]=Pr[Y=y]\]

for any fixed bits \(x,y\in\{0,1\}\). Proof. : Let \(b\in\{0,1\}\) be a fixed bit. Then,

\[Pr[X\oplus Y=b] =Pr[X\oplus Y=b|X=0]\cdot Pr[X=0]+Pr[X\oplus Y=b|X=1]\cdot Pr[X=1]\] \[=Pr[0\oplus Y=b|X=0]\cdot(1/2)+Pr[1\oplus Y=b|X=1]\cdot(1/2)\] \[=Pr[Y=b|X=0]\cdot(1/2)+Pr[Y=b\oplus 1|X=1]\cdot(1/2)\] \[=Pr[Y=b]\cdot(1/2)+Pr[Y=b\oplus 1]\cdot(1/2)\] \[=(Pr[Y=b]+Pr[Y=b\oplus 1])\cdot(1/2)\] \[=1/2.\]

Therefore, the result of XORing a certain bit with a random bit is also random. Let \(X^{\prime}=(X_{1},X_{2},\ldots,X_{r})\in\{0,1\}^{r}\) be a random variable where \(Pr[X_{i}=0]=Pr[X_{i}=1]=1/2\) and \(X_{i}\) and \(X_{j}\) are independent of each other for any positive integer \(r\), \(1\leq i,j\leq r\), and \(i\
eq j\). The distribution for \(X^{\prime}\oplus Y^{\prime}\) is also random as long as \(Y^{\prime}\) is independent of \(X^{\prime}\) regardless of the distribution \(Y\) is drawn from. Proof. : Let each bit of \(X^{\prime}\) and \(Y^{\prime}\) be \(X_{i}\) and \(Y_{i}\) for \(1\leq i\leq r\), respectively. The probability that the XOR result of \(X_{i}\) and \(Y_{i}\) becomes any of \(\{0,1\}\) is thus \(1/2\) according to Lemma 1. Because \(X_{i}\) and \(X_{j}\) for \(1\leq i,j\leq r\) and \(i\
eq j\) are independent variables, the probability of \(Pr[X^{\prime}\oplus Y^{\prime}=bs]\) is \((1/2)^{r}\) for any fixed bitstring \(bs\in\{0,1\}^{r}\). Therefore, the result of XORing a certain bitstring with a random bitstring is also random. Using Lemma 2, the one-time security of the one-way secret delivery mechanism can be proven. (One-time Security of One-way Secret Delivery) The one-way secret delivery protocol in the proposed scheme is one-time secure against adversaries as long as the mask value is drawn independently and uniformly at random. Proof. : Following the definition of entropy [38], the random mask has maximum uncertainty because it is chosen independently and uniformly at random from \(\{0,1\}^{\lambda}\), where \(\lambda\) is the bit-length of the hash value. According to Lemma 2, the XORed value with this random mask is also unpredictable (i.e., indistinguishable from other random bitstrings). #### 5.2.2 Security of the Proposed Scheme

In the proposed approach, the size of the proof generated by the prover \(\mathcal{P}\) can be either shorter than, exactly equal to, or longer than that of the typical Merkle tree-based approach. Typical types of proof according to proof size are presented in \[transmitted=shared\oplus\text{toShare}\]0

First, consider a passive adversary who does not affect the designated protocol but collects proof information leaked by eavesdropping on a public channel. (Cases in which the prover and the verifier collude are not considered in this paper because this action invalidates the effectiveness of the authentication process and is beyond the scope of our discussion.) Because this kind of adversary has no knowledge of the underlying data used to construct the Merkle tree, it can be assumed not to have all of the necessary information in advance before the attack. \[transmitted=shared\oplus\text{toShare}\]1 Classification of the proofs in the proposed scheme. **Theorem 3**: _(Resilience to the leakage of size information) An adversary who knows neither the number of blocks nor the value of the root node in the Merkle tree (nor the original data used to construct the tree) cannot obtain any meaningful information through eavesdropping on the proposed authentication protocol._

The proposed protocol allows the verifier to randomly select the proof length regardless of the Merkle tree structure. In the proposed scheme, the verifier sends a uniform random value as part of the challenge and the prover obtains the index value of the leaf node by taking the remainder after dividing the value by the number of blocks already known.