## 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
\begin{table}
\begin{tabular}{l c c c c c c c c} \hline  & **100 B** & **1 KB** & **10 KB** & **100 KB** & **1 MB** & **10 MB** & **100 MB** & **1 GB** \\ \hline \multirow{3}{*}{Merkle tree generation} & 0.00461 & 0.01748 & 0.11897 & 1.05451 & 10.67579 & 107.07319 & 1134.07592 & 11,191.59684 \\  & (0.00062) & (0.00080) & (0.00247) & (0.00723) & (0.09199) & (1.07465) & (19.51252) & (33.31233) \\ \hline \multirow{3}{*}{Challenge generation} & 0.00086 & 0.00086 & 0.00099 & 0.00101 & 0.00100 & 0.00100 & 0.00087 & 0.00087 \\  & (0.00019) & (0.00017) & (0.00020) & (0.00021) & (0.00021) & (0.00023) & (0.00017) & (0.00016) \\ \hline \multirow{3}{*}{Sibling path generation} & 0.00201 & 0.00389 & 0.00662 & 0.00863 & 0.01101 & 0.01258 & 0.02032 & 0.02273 \\  & (0.00024) & (0.00066) & (0.00048) & (0.00038) & (0.00059) & (0.00054) & (0.00159) & (0.00168) \\ \hline \multirow{3}{*}{Verification} & 0.00127 & 0.00417 & 0.00937 & 0.01398 & 0.01836 & 0.02369 & 0.02840 & 0.03294 \\  & (0.00034) & (0.00030) & (0.00077) & (0.00075) & (0.00096) & (0.00149) & (0.00085) & (0.00096) \\ \hline \end{tabular}
\end{table} 
Table 2: Average computation time (ms) for authentication based on Merkle tree by data size (standard deviation in parentheses). Figure 6: Computation time for hardcore function-based authentication. There is little difference in the computation time between the prover and the verifier. This is because both the verifier and the prover generate their own proofs based on the self-generated pseudorandom bitstring, which requires the most computation time, although the verifier aditionally conducts the initial seed generation and proof validation through a simple comparison, which requires relatively little time. For 1 MB of data, proof generation accounts for 98.2% of computation time for both the verifier and the prover. The detailed experiment results are summarized in Table 3.

#### 6.2.3 Authentication Based on Merkle Tree with Transmission in Encrypted Form

This approach requires the encryption and decryption of data transmitted between the prover and the verifier using a key agreed upon by both entities in addition to the typical Merkle tree-based authentication. Therefore, there is an additional need for a trusted authority in order to set the parameters to create an environment for key agreement. In this experiment, a Diffie-Hellman key agreement mechanism was adopted with a modulus of 3072 bits. (If communication parties require data authentication and continuous communication, the computation time for key agreement may be excluded from computation overhead. However, in this paper, we experimented with parameter setting for the same security level on the assumption that only communication for online data authentication is done.) Additionally, the data to be transmitted to the other party is encrypted with the agreed key and decrypted on the recipient's side, leaving the rest of the process the same as in the typical Merkle tree-based approach. In other words, the verifier encrypts and transmits a random challenge and decrypts the proof received from the prover. The prover decrypts the challenge received from the verifier to generate the proof, and then encrypts that proof. If the parties communicate and perform data authentication continuously, the computation time for key agreement may be excluded from computation overhead. In this case, however, there is a possibility that an adversary can bypass authentication from eavesdropping of repeated authentication process, and there is still a leak in size information. In practice, since most of the authentication is done by a large number of independent users, individual users need to establish a new session (using a new session key) and perform authentication. Therefore, in this paper, we only measured communication overhead for online data authentication in encrypted form after a key agreement on the same security level.