## 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
This prevents the adversary from inferring the upper bound of the leaf node index during a repeated verification process as long as the verifier chooses different uniform random challenges with each execution, unlike typical Merkle tree-based authentication. Further, the sibling path generated using the Merkle tree is reduced or enlarged according to the requested proof length, which is also chosen uniformly at random by the verifier as another component of the challenge. As a result, there is no relationship between the size of the final proof and the size of the actual Merkle tree, making it impossible for the adversary to infer the size of the underlying data by calculating how the proof size corresponds to the number of leaf nodes in the tree. Upon closer inspection, the proof generated in the proposed scheme includes the value of the root node in the tree in masked form, which differs from typical Merkle tree-base authentication. Using this feature, it may be possible to uncover the mask when the number of data blocks is known to the adversary. In this case, the adversary can identify the starting position of the meaningful portion (i.e., the location of \(MT_{D}^{root}\) in Figure 3(b)) of the proof sent by the prover to the verifier. All they need to do is to uncover this mask value. **Theorem 4**: _(Reliability of the proposed authentication) An adversary who knows the number of blocks within the underlying data cannot obtain any meaningful information from the proposed authentication protocol._

Even if it were possible to track the location of the beginning portion (excluding bitstrings filled with random values) of the meaningful proof from the total number of blocks and the requested proof length, the adversary cannot recover the value of the root node in the tree from the masked proof in Theorem 2. Consequently, the probability of recovering the value of a root node is identical to finding the mask value, which is \((1/2)^{\lambda}\), where \(\lambda\) is the bit-length of the security parameter (or the hash value). It is notable that the prover chooses different random mask values on every proof generation. Therefore, the reliability of the challenge-response protocol remains the same as long as the adversaries cannot uncover the value of the root node. In this context, the increased security of the proposed scheme exploiting Merkle tree is dependent on the secrecy of the value of the root node of the tree. We define an experiment to show the formal security of the proposed scheme in the presence of eavesdropping adversary. **Definition 3**. : _The experiment is defined for the proposed Merkle tree-based authentication \(\Pi\) for the security parameter \(\lambda\) and an adaptive adversary \(\mathcal{A}\) who only receives oracle accesses to the prover. The oracle access to the prover is again divided into access to the proof \(\mathcal{O}_{\text{P}}^{\text{proof}}\) and access to the corresponding data \(\mathcal{O}_{\text{P}}^{\text{data}}\)._

_The indistinguishability experiment \(\text{Priv}K_{\mathcal{A},\Pi}(\lambda)\):_

_1. (Init) The adversary \(\mathcal{A}\) is given input \(1^{\lambda}\) and the hash function \(h\) used to construct a Merkle tree._

_2. (QueryI-I) \(\mathcal{A}\) requests oracle acces to \(\mathcal{O}_{\text{P}}^{\text{proof}}\), with challenging index \(\text{chal}_{i}\) and required proof length \(L_{i}\) each chosen randomly and independently, polynomially many times. The oracle randomly creates and stores data \(D_{i}\) locally, generates obfuscated proof \(\text{proof}_{i}\) (by performing \((n_{i},h_{i},MT_{D_{i}})\leftarrow\Pi\). **ContructMerkleTree**\((D_{i})\), \(\text{proof}_{i}^{{}^{\prime}}\leftarrow\Pi\). **GenerateProof**\((MT_{D_{i}},\text{chal}_{i},L_{i})\), and \(\text{proof}_{i}\leftarrow\Pi\). **ObfuscateProof**\((MT_{D_{i}},L_{i})\) successively), and sends it to \(\mathcal{A}\)._

_3.