## 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 return value \(True\) indicates successful authentication. Otherwise, verification has failed
```
(\(n,h,MT_{D}\)) \(\leftarrow\)ConstructMerkleTree(\(D\)): Split \(D\) into \(|B|\)-bit blocks as \(\tilde{D}=(B_{1},B_{2},\ldots,B_{n})\), where \(n\) is the number of blocks that make up \(D\) Construct Merkle tree \(MT_{D}\) with \(\tilde{D}\) as leaf nodes \(prf\leftarrow\)GenerateProof(\(MT_{D}\),\(\mathit{chal}\),\(L\)): Put the values for the siblings of the nodes that lie on the path from the \(\mathit{chal}\)-th leaf node to the root node in \(MT_{D}\) (including the root) into \(prf\) while\(prf>L\): \(prf\leftarrow(\mathcal{H}(prf_{1},prf_{2}),prf_{3},\ldots,prf_{[prf]})\) endif
```
_res_\(\leftarrow\)VerifyProof(\(prf,MT_{D}^{\text{root}}\)): Set \(\mathit{vt}\) to be the first element in \(prf\) Compute verification term \(\mathit{vt}\) by evaluating hash function \(\mathcal{H}\) of \(\mathit{vt}\) and an element in \(prf\) from second element to the last one.5 min a recursive manner if\(\mathit{vt}=MT_{D}^{\text{root}}\): _res_\(\leftarrow\)_True else: _res_\(\leftarrow\)_False
```
**Algorithm 5** Merkle tree-based online authentication with randomized input

**6. ** Prove **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. The return value \(True\) indicates successful authentication. Otherwise, verification has failed
```
(\(n,h,MT_{D}\)) \(\leftarrow\)ConstructMerkleTree(\(D\)): Split \(D\) into \(|B|\)-bit blocks as \(\tilde{D}=(B_{1},B_{2},\ldots,B_{n})\), where \(n\) is the number of blocks that make up \(D\) Construct Merkle tree \(MT_{D}\) with \(\tilde{D}\) as leaf nodes \(prf\leftarrow\)GenerateProof(\(MT_{D}\),\(\mathit{chal}\),\(L\)): Put the values for the siblings of the nodes that lie on the path from the \(\mathit{chal}\)-th leaf node to the root node in \(MT_{D}\) (including the root) into \(prf\) while\(prf>L\): \(prf\leftarrow(\mathcal{H}(prf_{1},prf_{2}),prf_{3},\ldots,prf_{[prf]})\) endif
```
_res_\(\leftarrow\)VerifyProof(\(prf,MT_{D}^{\text{root}}\)): Set \(\mathit{vt}\) to be the first element in \(prf\) Compute verification term \(\mathit{vt}\) by evaluating hash function \(\mathcal{H}\) of \(\mathit{vt}\) and an element in \(prf\) from second element to the last one.5 min a recursive manner if\(\mathit{vt}=MT_{D}^{\text{root}}\): _res_\(\leftarrow\)_True else: _res_\(\leftarrow\)_False
```
**Algorithm 6** Merkle tree-based online authentication with randomized input

**7. ** Prove **PostoreProof**(\(prf,h,MT_{D}^{\text{root}}\)): Set \(\mathit{vt}\) to be the first element in \(prf\) Compute verification term \(\mathit{vt}\) by evaluating hash function \(\mathcal{H}\) of \(\mathit{vt}\) and an element in \(prf\) from second element to the last one.5 min



#### 4.3.1 Authentication Initiation

First of all, the verifier \(\mathcal{V}\) constructs a Merkle tree for data \(D\) to be verified following the generic Merkle tree construction process (**Step** 1). Notice that \(\mathcal{V}\) needs to construct this tree only once (usually before verification) to store the number of leaf nodes and the root node value in the tree, and then discards all remaining information about the tree. As for specifying the data to be verified, the verifier and the prover can use \(\mathcal{H}(\mathcal{H}(D))\) as an identifier. Due to the collision-resistant property of the cryptographic hash function, we assume that the probability that different data files produce the same hash tree is negligible. #### 4.3.2 Randomized Challenge Generation

In this phase, the verifier \(\mathcal{V}\) generates a random challenge for the claim that prover \(\mathcal{P}\) manages the data properly as \(\mathcal{V}\) desires.