## 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 proof corresponds to a series of hash values and is logarithmically proportional to the number of all of the data blocks, where the size of the hash value is 384 bits (i.e., 48 Bytes). _Authentication based on Merkle tree_ requires the additional transmission of a partial key generated by the prover that is 3072 bits (i.e., 384 Bytes) in size. The comparison of the data transmission from the prover to the verifier is presented in Figure 11.

Recall that the size of a proof, which is embedded in the challenge, is determined by the verifier. Therefore, the transmitted proof size is independent of the actual data size. As specified in Table 5, the average requested proof length (which is proportional to the number of hash values) of 51 is much longer than the sibling path in the Merkle tree approach. For example, 1 MB of data has a sibling path length of 13 and 1 GB of data has a sibling path length of 23. The communication overhead when the requested proof length is fixed at 25 is also illustrated as the last bar in Figure 11. In this case, the communication overhead is almost the same as that of 100 MB of data in conventional _authentication based on Merkle tree_ even for 1 GB of data. This characteristic of the proposed scheme is positive in that it provides flexibility for the verifier in setting the proof length regardless of the actual data size. \begin{table}
\begin{tabular}{l c c c c} \hline \hline \multirow{2}{*}{**Features**} & \multicolumn{4}{c}{**Authentication Based on**} \\ \cline{2-5}  & **Merkle Tree** & **Hardcore Function** & \
\begin{tabular}{c} **Merkle Tree with** \\ Encrypted Communication \\ \end{tabular} &
\begin{tabular}{c} **Proposed** \\ **Scheme** \\ \end{tabular} \\ \hline Resilience against size information leakage & X & X & X & O \\ Resilience against replay attacks & X & O & O & O \\ Requirement for an additional trusted authority & X & X & O & X \\ \hline \hline \end{tabular}
\end{table} 
Table 6: Average computation time (ms) for Merkle tree-based encrypted authentication by data size (standard deviation in parentheses). Figure 11: Comparison of trasmitted data on prover side with varying data size. On the other hand, in the transmission from the verifier to the prover, only a constant amount of transmission is required regardless of the data size, because only the challenge is transmitted in all schemes except _authentication based on a hardcore function_. The comparison of the data transmission from the prover to the verifier is presented in Figure 12.

In terms of storage, there is no additional overhead because the random sources can be removed from the local storage immediately after the hash evaluations. ## 7 Conclusions

At the present time, when data storage and maintenance costs can be reduced due to advances in information and communication technologies, it is easy to overlook whether data is correctly and legitimated managed when outsourced to remote repositories. In this paper, we investigated the types of information leakage that can occur when data integrity is compromised between physically separate entities and reviewed representative approaches to handling this issue. A simple but efficient approach is presented to improve the security and reliability of data integrity validations, something which has been neglected in previous research. Providing rigorous security analysis, the effectiveness of the proposed scheme is examined in terms of resilience against the leakage of size information and replay attacks. Performance analysis shows that our method provides the highest efficiency in terms of computation load and improves security and reliability. [PERSON] contributed the ideas and wrote the paper; [PERSON] and [PERSON] designed and conducted the experiments; [PERSON] performed the security analaysis and supervised the whole paper including paper organization and proofread. This work was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIT) (No. 2017R1C1B5077026) for [PERSON].