## 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
(QueryI-II) \(\mathcal{A}\) requests oracle access to \(\mathcal{O}_{\text{P}}^{\text{data}}\) by sending the received proof \(\text{proof}_{i}\) to obtain the corresponding underlying data. The oracle retrieves the underlying data \(D_{i}\) used to generate the proof \(\text{proof}_{i}\) and sends it to \(\mathcal{A}\)._

_4. (Challenge) The challenger creates random data \(D\) that is not already queried and generate an obfuscated proof \(\text{proof}_{1}\) following the specified protocol in \(\Pi\). It also generates an arbitrary bitstring \(\text{proof}_{2}\) of the same length as \(\text{proof}_{1}\). Then, according to the result of the fair coin toss \(b\in\{0,1\}\), \(\text{proof}_{b}\) is delivered to \(\mathcal{A}\)._

_5. (QueryII-I) The step 2 is repeated in polynomial time._

_6. (QueryII-II) The step 3 is repeated except for \(\text{proof}_{b}\) as necessary in polynomial time._

_7. (Guess) \(\mathcal{A}\) guesses the value of \(b\). If \(\mathcal{A}\)'s guess is correct, \(\mathcal{A}\) wins the game. Otherwise, it loses._

**Theorem 5**. : _(Consistent reliability of the proposed authentication with repeated requests) An adversary who knows the number of blocks within the underlying data cannot obtain any meaningful information by repeatedly running the proposed authentication protocol._

Proof. : Note that the random mask used in Step 2 presented in the Definition 3 is randomly selected in the uniform distribution for each proof generation. Although the adversary \(\mathcal{A}\) can verify the validity of the received proof (by performing \(\text{proof}_{i}^{{}^{\prime}}\leftarrow\Pi\). **RestoreProof**\((\text{proof}_{i},h_{i},MT_{D_{i}}^{\text{root}})\) and \(\text{res}_{i}\leftarrow\Pi\). **VerifyProof**\((\text{proof}_{i}^{{}^{\prime}},MT_{D_{i}}^{\text{root}})\) successively) in Step 3, \(\mathcal{A}\) cannot distinguish whether \(\text{proof}_{b}\) received in Step 4 is valid proof or not by Theorem 3. Furthermore, \(\mathcal{A}\) cannot know the mask value used to generate the proof \(\text{proof}_{b}\) by Theorem 2 so that the prior knowledge does not help to break the proposed authentication mechanism. In the same context, Steps 5 and 6 also only give at most negligible advantage to determine the validity of the proof \(\text{proof}_{b}\) given by the challenge. This means the leakage resilience of the proposed authentication scheme even in the presence of adaptive adversary. Now, we consider another adversary who has knowledge of both the number of blocks in the tree and the value of the root node in the Merkle tree. However, it make sense to assume that this kind of adversary has no knowledge of the underlying data without loss of generality (e.g., when an adversary is delegated to audit data integrity held in remote storage by a valid data owner, while the actual content is kept private). Nevertheless, even though the above two pieces of information are known to the adversary, the proposed scheme provides security that is as strong as that of typical Merkle tree-based authentication (Section 5.1). ## 6 Efficiency Analysis

In this section, the efficiency of the proposed scheme is evaluated based on the experimental implemention of related schemes. ### Experimental Environment

According to the Commercial National Security Algorithm (CNSA) Suite [39] recommended by the National Security Agency (NSA), we used SHA-3 384-bit as a cryptographic hash function, a Diffie-Hellman key with a 3072-bit modulus, and AES-256 for key agreement and a secure encryption algorithm when implementing comparison schemes. All experiments were performed on a single machine with a 3.5 GHz CPU (Intel i7-7800x) and 64 GB RAM (3600 MHz 4 \(\times\) 16 GB) running Windows 10. Each algorithm was implemented as a singrypto version 2.6.1) [40] for AES and Diffie-Hellman key agrele-threaded 32-bit Python [41] program, using the Python cryptography toolkit (pycement and the SHA-3 wrapper for Python (Pysha3 version 1.0.2) [42] for SHA-3, respectively.