## 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 bit string \(s\) is then masked iteratively by applying a bitwise XOR operation to each element of the sibling path _sib_. To obtain the bit-length of the resulting proof \(L\cdot|\mathcal{H}|\) when the requested proof length is longer than the obfuscated proof, a randomly selected bitstring \(R\) of length \((L-h-2)\cdot|\mathcal{H}|\) is prepended to the proof \(prf\) (when \(L>h+2\)). Note that, before generating the proof, the prover \(\mathcal{P}\) can derive the height \(h\) of the Merkle tree that is to be constructed because \(\mathcal{P}\) knows the total number of leaf nodes (i.e., data blocks). Thus, \(\mathcal{P}\) calculates the length of hash values to be appended as \(L-h-2\) (\(h\) for the number of siblings on the path from the challenged node to the root, \(1\) for the challenged node, and another \(1\) for the root node). From this calculation, prover \(\mathcal{P}\) generates an arbitrary bitstring \(R\) with a length equal to \((L-h-2)\) hash values. The key to this phase is allowing individual provers to insert random sources into the verification proof in a non-deterministic manner. #### 4.3.6 (Original) Proof Restoration

When the verifier \(\mathcal{V}\) receives the masked authentication proof from the prover \(\mathcal{P}\) on the challenge _chal_ with a bit-length equal to \(L\cdot|\mathcal{H}|\), \(\mathcal{V}\) restores it to the generic form of a sibling path (**Step 6**). First, the unnecessary heading \((L-h-2)\cdot|\mathcal{H}|\)-bit bitstring is removed from the obfuscated proof \(prf\). The last element in \(prf\), corresponding to the masked value of the root node \(MT_{D}^{root}\) is then XORed with \(\mathcal{V}\)'s value of \(MT_{D}^{root}\) to obtain the masking factor _mask_. For the remaining elements, _mask_ is recursively XORed for each one in reverse order. #### 4.3.7 Proof Verification

In this phase, the restored proof \(prf\) is validated by the verifier \(\mathcal{V}\) in the same way as in the typical approach (**Step 7**). The hash value corresponding to the root node of the tree is obtained by repeating the process of re-hashing two neighboring hash values from the first hash value of the proof. If the calculated hash value is the same as the value stored by the verifier \(\mathcal{V}\), the authentication succeeds. Otherwise, validation is considered a failure. ## 5 Security Analysis

In this section, the security of the proposed scheme is analyzed in detail. First, the security of Merkle tree-based online authentication, which is assumed to be conducted only once, is discussed. Using this as a baseline, the security of the proposed method and its ability to improve reliability are then examined. ### Security of Merkle Tree-based Authentication

The primitive used to construct a Merkle tree is a cryptographic hash function that satisfies preimage resistance, second preimage resistance, and collision resistance properties. Definition 1: **(Preimage-resistant hash function)** Given image \(y\) of a hash function \(h\), for all pre-defined outputs, the function is preimage-resistant if it is computationally infeasible to find any preimage \(x\) such that \(y=h(x)\)[33]. In the verification of data integrity stored in remote storage, the Merkle tree-based approach begins with the assumption that the verifier and the prover share the same information (i.e., the value of the root node and the number of leaf nodes in the tree). Otherwise, the verifier can neither generate a valid challenge nor validate the correctness of the proof. Under this assumption, when online authentication is performed only once, its security can be summarized as Theorem 1.