## 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
In the latter case, the adversary acts as a more active attacker by passing a set of random challenges of its choosing to an oracle and collecting a valid proof set for the upload-requested data. In other words, valid prover \(\mathcal{P}\) can be an oracle for the target data and the adversary attempts to circumvent the authentication process by manipulating the obtained proofs. Without loss of generality, we assume that the adversary has no prior knowledge about the data to be challenged (proved). Specifically, we assume that the adversary is unable to extract size information from eavesdropping on interactions during the authentication process, except for initial upload. The goal of these adversaries is to weaken the reliability of the authentication process by exploiting information gathered through wiretapping. ### Goal

In order to minimize information leakage when a Merkle tree is used for online data authentication, the proposed scheme needs to satisfy the following requirements:

* Prevention of size information leakage: The authentication mechanism should block the outflow of information about the size of the target data, which can be used by adversaries to select and predict the required number of authentication proofs. * Prevention of replay attacks: The protocol should not allow adversaries to launch replay attacks, in which a collected valid set of authentication proofs are used in subsequent authentication requests. In other words, the adversary cannot learn any information from the disclosed information via public channels during the authentication process. * Minimal reuctions in efficiency: The effective handling of side channels should be achieved with acceptable computation and communication overhead, maintaining the advantages of the Merkle tree-based approach. * Compatability: Given that the Merkle tree-based approach is widely deployed in industry and academia due to its intuitive nature and ease of utilization, the proposed approach should be applicable to existing uses. This includes adaptability to lightweight devices with limited resources and restrictions on the installation of additional libraries depending on the system architecture, such as IoT terminal devices and sensors. ### Construction

To be resistant against information leakage regardless of the number of authentication attempts, the transmitted authentication proof (i.e., sibling paths) needs to be randomized so that an eavesdropping adversary cannot gather any valuable information from the transcript. In this section, we present a simple amendment that inserts random inputs and significantly increases the reliability of online authentication. The overall process is illustrated in Algorithm 3, with example data composed of four blocks. Associated notations are summarized in Table 1.
```
Verifier \(\mathcal{V}\) Prover \(\mathcal{P}\) \(\mathcal{D}\) \(\mathcal{D}=(B_{1},\ldots,B_{4})\)
```
**Algorithm 3** Merkle tree-based online authentication with randomized input

**1. ** Given data \(D\), invoke **ConstructMerkleTree**(\(D\)) to obtain number of blocks \(n\), Merkle tree \(MT_{D}\) for \(D\), and its height \(h\)  Keep \(n,h,MT_{D}^{\text{root}}\) in local storage privately, where \(MT_{D}^{\text{root}}\) is the value of the root node extracted from the Merkle tree \(MT_{D}\)  Choose random index(es) \(\mathit{chal}\in\mathbb{N}\) and the length of sibling path(s) \(L\in\mathbb{N}\) (e.g., \(\mathit{chal}=100,L=7\) for \(D=(B_{1},\ldots,B_{4})\))
```
**Algorithm 4** Merkle tree-based online authentication with randomized input  
**2. ** Choose random index(es) \(\mathit{chal}\in\mathbb{N}\) and the length of sibling path(s) \(L\in\mathbb{N}\) (e.g., \(\mathit{chal}=100,L=7\) for \(D=(B_{1},\ldots,B_{4})\))
```
**6. ** Invoke **RestoreProof**(\(prf,h,MT_{D}^{\text{root}}\)) to obtain the restored original sibling path of \(\mathit{chal}\) as proof \(prf\) (e.g., \(prf=(H^{\prime}_{1},H^{\prime}_{2},H^{\prime}_{3-4})\))
```
**7. ** Invoke **VerifyProof**(\(prf,MT_{D}^{\text{root}}\)) to validate the proof.