## 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 \hline  & **100 B** & **1 KB** & **10 KB** & **100 KB** & **1 MB** & 10 MB & **100 MB** & **1 GB** \\ \hline Parameter & 9468.19790 & 9538.16482 & 9794.65946 & 9532.98866 & 9452.51795 & 9727.44050 & 9064.76798 & 9633.54744 \\ generation & (8493.82876) & (8975.20449) & (9175.01323) & (8829.14856) & (8759.71474) & (9374.65954) & (7981.16155) & (8863.74385) \\ \hline Partial key & 4.80688 & 4.79883 & 4.78975 & 4.79192 & 4.80195 & 4.80006 & 4.81253 & 4.96501 \\ generation & (0.18776) & (0.18395) & (0.18719) & (0.18367) & (0.18475) & (0.18142) & (0.19221) & (0.2943) \\ \hline Key & 4.57732 & 4.57399 & 4.56398 & 4.56755 & 4.57577 & 4.57745 & 4.57501 & 4.57433 \\ agreement & (0.13962) & (0.14449) & (0.14221) & (0.15151) & (0.15099) & (0.14848) & (0.14461) & (0.14200) \\ \hline Challenge generation & 0.00087 & 0.00098 & 0.00091 & 0.00088 & 0.00100 & 0.00087 & 0.00099 & 0.00087 \\ generation & (0.00018) & (0.00020) & (0.00020) & (0.00016) & (0.00021) & (0.00016) & (0.00023) & (0.00018) \\ \hline Encryption of the challenge & 0.02674 & 0.02647 & 0.02668 & 0.02702 & 0.03341 & 0.03457 & 0.03739 & 0.05227 \\ the challenge & (0.00145) & (0.00140) & (0.00117) & (0.0013) & (0.00210) & (0.00235) & (0.00323) & (0.00281) \\ \hline Decryption of the encryption of the challenge & 0.01458 & 0.01567 & 0.01597 & 0.01776 & 0.01967 & 0.02292 & 0.02444 & 0.02568 \\ the challenge & (0.00068) & (0.00065) & (0.00042) & (0.00088) & (0.00118) & (0.00097) & (0.00064) & (0.00066) \\ \hline Merkle tree & 0.00324 & 0.01570 & 0.11664 & 1.05112 & 10.55169 & 106.34833 & 1072.881132 & 11.196.73308 \\ generation & (0.00024) & (0.00043) & (0.00184) & (0.03182) & (0.08447) & (0.36833) & (6.69879) & (33.06858) \\ \hline Stilting path generation & 0.00271 & 0.00429 & 0.00655 & 0.00808 & 0.01018 & 0.01172 & 0.01773 & 0.02247 \\ generation & (0.00033) & (0.00042) & (0.00047) & (0.00054) & (0.00079) & (0.00047) & (0.00100) & (0.00101) \\ \hline Encryption of the sibling path & 0.01639 & 0.01751 & 0.01866 & 0.02067 & 0.02978 & 0.04813 & 0.05219 & 0.05405 \\ the sibling path & (0.00061) & (0.00043) & (0.00089) & (0.00117) & (0.00323) & (0.00177) & (0.00118) & (0.00357) \\ \hline Decryption of & 0.01782 & 0.01776 & 0.01895 & 0.01714 & 0.01790 & 0.01957 & 0.02026 & 0.02090 \\ the sibling path & (0.00061) & (0.00071) & (0.00062) & (0.00085) & (0.00058) & (0.00102) & (0.00080) & (0.00129) \\ \hline Verification & 0.00130 & 0.00454 & 0.00981 & 0.01408 & 0.01836 & 0.02378 & 0.02848 & 0.03252 \\  & (0.00018) & (0.00041) & (0.00078) & (0.00091) & (0.00112) & (0.00121) & (0.00088) & (0.00041) \\ \hline \hline \end{tabular}
\end{table} 
Table 4: Average computation time (ms) for Merkle tree-based encrypted authentication by data size (standard deviation in parentheses). Figure 7: Computation time for Merkle tree-based authentication with encrypted communication. #### 6.2.4 Authentication Based on the Proposed Approach

Similar to Merkle tree-based authentication after encryption, the proposed mechanism obfuscates the transmitted data (i.e., challenges from the verifier and proofs from the prover). Notice that, however, unlike the other scheme, ours does not require an additional trusted authority to generate public parameters for key agreement as a preprocessing stage before the challenge-response process. In addition, the proposed scheme hides the size information by randomizing the proof size regardless of the Merkle tree structure. Specifically, the verifier requests an arbitrary proof length in terms of the hash values and the prover generates and obfuscates (and truncates if necessary) the sibling path according to the requested proof length, followed by padding with a random bitstring when the generated proof is shorter than the specified length.