## 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
Unlike previous Merkle tree-based authentication approaches in which the challenge is selected from within a limited range (i.e., \(\{1,2,\ldots,n\}\)), the verifier \(\mathcal{V}\) selects a random integer without restriction. \(\mathcal{V}\) also specifies the length of the proof to be received and sends this value and the challenge to the prover (**Step** 2). The length of the proof can be an arbitrary number when it is greater than 2. In our approach, the proof length does not depend on the Merkle tree structure, unlike the original Merkle tree-based verification process. Specifically, the value of the sibling nodes in the Merkle tree may not be used in the proposed scheme when the requested proof length is shorter than the length of the sibling path from the leaf (challenged) node to the root. For a detailed description, see Section 4.3.4. #### 4.3.3 Original Challenge Restoration

Upon receipt of the challenge and proof length specification, the prover \(\mathcal{P}\) restores the intended challenge index _chal_ (**Step** 3). The prover \(\mathcal{P}\) can specify the data block to which the challenge points, on the assumption that the prover \(\mathcal{P}\) and the verifier \(\mathcal{V}\) have common knowledge about the number of data blocks constituting the data \(D\). The index of the challenged block becomes the remainder after dividing the challenge by the total number of data blocks. #### 4.3.4 Proof Generation

Using the restored challenge and proof length specification, the prover \(\mathcal{P}\) generates the corresponding proof \(prf\). Unlike the typical Merkle tree-based approach, the proposed protocol requires the value of root node to be appended to the end of the proof (**Step** 4). \begin{table}
\begin{tabular}{r l} \hline \hline
**Notation** & **Description** \\ \hline \(\mathcal{H}(\cdot)\) & Cryptographic hash function \\ \(||\mathcal{H}||\) & Size of the hash value (in bits) \\ \hline \(n\) & Number of data blocks for the entire data \(D\) \\ \(MT_{D}\) & Merkle tree constructed from data \(D\) \\ \(MT_{D}^{prot}\) & Root node in the Merkle tree \(MT_{D}\) \\ \(h\) & Height of the Merkle tree \\ \(L\) & Required length of the sibling path in the authentication proof \\ \(valN\) & Value of the given node \(N\) \\ \(sib(N)\) & Sibling node in the sibling path for the given node \(N\) \\ \hline \(A_{i}\) & \(i\)-th element in sequence \(A\) (cardinality) \\ \(|A|\) & Number of elements in set \(A\) \\ \(a\in_{R}A\) & Random selection of element \(a\) in set \(A\) \\ \(b\gets B\) & Assignment of the result of the deterministic algorithm (operation) \(B\) to \(b\) \\ \(b\xleftarrow{\epsilon}B\) & Assignment of the result of the probabilistic algorithm (operation) \(B\) to \(b\) \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Notations. It is worth noting that the proposed protocol does not depend on the Merkle tree structure for concealing size information. In other words, a proof that is shorter than the length of the sibling nodes is possible, thus making the data look smaller than its actual size. (In this case, the values of the nodes closest to the leaf node in the certificate must be removed in order, but the value remaining at the end after this removal (corresponding to the leaf node in the certificate) must be derived from the removed values.) In addition, a proof longer than the length of the sibling nodes is also possible, making the data look larger than its actual size, as described in the following subsection. #### 4.3.5 Proof Obfuscation

In this phase, the prover \(\mathcal{P}\) obfuscates the proof, prepends a random bitstring to the proof if necessary for the purpose of concealing the size information (making the data appear larger than the actual size), and then passes the resulting proof to the verifier \(\mathcal{V}\) (**Step 5**). Based on the algorithm **ObfuscateProof**, the prover \(\mathcal{P}\) first selects a random bitstring \(s\) with a length equal to the hash value.