## 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}{c c c c c c c c c} \hline \hline  & **100 B** & **1 KB** & **10 KB** & **100 KB** & **1 MB** & 10 MB & **100 MB** & **1 GB** \\ \hline \multirow{2}{*}{Requested proof length} & 49.04100 & 50.84400 & 52.70/00 & 52.58500 & 52.22300 & 51.67100 & 50.86000 & 50.81600 \\  & (27.97269) & (28.63403) & (27.93591) & (28.83915) & (28.47626) & (28.3989) & (27.28825) & (28.78824) \\ \hline \multirow{2}{*}{Merkle tree generation} & 0.00299 & 0.01417 & 0.11407 & 1.04286 & 10.53377 & 106.27209 & 1081.34281 & 11,178.68500 \\  & (0.00098) & (0.00324) & (0.03135) & (0.29979) & (3.02505) & (30.96492) & (320.58949) & (354.27592) \\ \hline \multirow{2}{*}{Challenge generation} & 0.00216 & 0.00226 & 0.00247 & 0.00243 & 0.00216 & 0.00240 & 0.00243 & 0.00238 \\  & (0.00068) & (0.00067) & (0.00062) & (0.00053) & (0.00070) & (0.00056) & (0.00059) & (0.00068) \\ \hline \multirow{2}{*}{Sibling path generation} & 0.00000 & 0.00000 & 0.00000 & 0.00000 & 0.00002 & 0.00002 & 0.00003 & 0.00002 \\  & (0.00000) & (0.00000) & (0.00000) & (0.00000) & (0.00000) & (0.00000) & (0.00000) & (0.00000) \\ \hline \multirow{2}{*}{Sibling path obfuscation} & 0.04547 & 0.06643 & 0.10507 & 0.13948 & 0.17899 & 0.23363 & 0.26413 & 0.29186 \\  & (0.00596) & (0.00338) & (0.01607) & (0.01782) & (0.02655) & (0.03630) & (0.04581) & (0.06181) \\ \hline \multirow{2}{*}{Random bitstring padding} & 0.89665 & 0.87894 & 0.85868 & 0.78980 & 0.72994 & 0.66017 & 0.59333 & 0.55448 \\  & (0.54933) & (0.53655) & (0.53474) & (0.53037) & (0.51176) & (0.49959) & (0.46923) & (0.47786) \\ \hline \multirow{2}{*}{Mask removal} & 0.02384 & 0.04487 & 0.08232 & 0.11417 & 0.14501 & 0.17849 & 0.20863 & 0.23202 \\  & (0.00310) & (0.00207) & (0.01486) & (0.01715) & (0.02501) & (0.03532) & (0.04438) & (0.0690) \\ \hline \multirow{2}{*}{Verification} & 0.00886 & 0.01602 & 0.01936 & 0.02576 & 0.02953 & 0.03799 & 0.04319 & 0.04763 \\  & (0.00358) & (0.08621) & (0.00421) & (0.05892) & (0.00504) & (0.01028) & (0.00676) & (0.00924) \\ \hline \hline \end{tabular}
\end{table} 
Table 5: Average computation time (ms) of the proposed authentication scheme by data size (standard deviation in parenthesis). Considering the features of the related schemes summarized in Table 6, the verifier in _authentication based on a hardcore function_ allows anyone to know the size of the underlying data (because the bit-length of the transmitted seed is logarithmically proportional to the data volume) even though the transmitted data is randomized. _Authentication based on Merkle tree with encrypted communication_ (the third bar) is resilient to replay attacks that let the adversary reuse previously successful validation, but is still susceptible to size information leakage. In short, none of the comparison algorithmsare able to reduce information leakage to the same extent as the proposed scheme. Nevertheless, the proposed scheme requires the least computation overhead for both the prover and the verifier (except for Merkle tree-based authentication, which does not consider information leakage). Figure 10: Comparison of computation overhead on the verifier side. Figure 9: Comparison of computation overhead on the prover side. ### Communication Overhead

For all of the compared schemes, the proof is generated using all of the data, but the final proof transmitted to the verifier is proportional to the log of the data bit-length. Looking closely at the amount of data for each entity, however, there are noticible differences between approaches. In the transmission from the prover to the verifier, _authentication based on a hardcore function_ generates and sends a proof of bit-length (\(|M|+\log(M)-1\)) for data \(M\). Therefore, the size of the generated proof becomes very small. Specifically, the proof size is only 1 Byte when the data is 100 Bytes in size, 2 Bytes for data between 1 KB and 10 KB in size, 3 Bytes for 100 KB-10 MB of data, and 4 Bytes for 1 GB of data. On the other hand, the other approaches generate and send a proof.