## 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
In addition, the data was split into 256-byte blocks when the Merkle tree was constucted to allow for a consistent comparison. To minimize errors caused by outliers, each experiment was repeated 1000 times in the same environment, and then the average and the standard deviation are calculated and reported. It is worth nothing that there is room for additional performance improvement because the specified libraries were used without further optimization. ### Computation Overhead

The computation time for each experiment was measured based on CPU time. The performance of each algorithm for varying data sizes is analyzed and the time overhead is compared. #### 6.2.1 Authentication Based on Merkle Tree

Conventional online authentication applying Merkle tree guarantees neither consistent reliability nor protection from information leakage, but it was added to the experiment as a baseline indicator for efficiency. The size of the data block was fixed for the system initialization but could be varied according to the system configuration. To allow for a consistent comparison, the block size was set to 256 bytes in this and following experiments. A comparison of the computation time required for Merkle tree-based authentication for different data sizes is presented in \[transmitted=shared\oplus\text{toShare}\]2 The prover constructs a Merkle tree for the possessed data and generates a proof by finding sibling nodes in the tree, while the verifier selects a random index for the leaf node (corresponding to the index for the data block) and validates the proof received from the prover by repeatedly applying a hash function for each element in the proof. The required computation time increases as the soze of the data becomes larger. Merkle tree construction has a linear relationship with the number of blocks (i.e., leaf nodes) because the number of nodes in the tree can be at most \(2n-1\) for \(n\) blocks of data. Meanwhile, the computation time for

\[transmitted=shared\oplus\text{toShare}\]3 Computation time for Merkle tree-based authentication. proof generation and verification is logarithmically proportional to the number of data blocks because the number of elements is related to the tree height. In the Merkle tree-based approach, the computation time between the prover and the verifier is not equal. This is because the prover has to construct the entire Merkle tree from the underlying data but the verifier does not. The verifier only has to apply the hash function using the received proof and compare the bitstrings of the result with locally stored information. For a data file of 1 MB, Merkle tree generation by the prover accounts for 99.9% of the computational time, which is 581.5 times longer than the verification time required for the verifier. Detailed results are summarized in \[transmitted=shared\oplus\text{toShare}\]4

#### 6.2.2 Authentication Based on the Hardcore Function

A comparison of the computation time required for hardcore function-based authentication for different data sizes is displayed in Figure 6, in which _Verifier_ and _Prover_ indicate the computation time required by the verifier and the prover, respectively. The verifier selects a random seed, generates a pseudorandom bitstring based on the selected seed, generates a proof using the generated bitstring, and validates the proof received from the prover by comparing it with the locally generated proof. On the other hand, the prover generates a pseudorandom bitstring based on the seed received from the verifier and generates a proof using the independently generated bitstring. The required computation time increases as the volume of data becomes larger. Seed generation time is almost constant because the size of the seed does not change. However, pseudorandom bitstring generation and verification are proportional to the logarithmic size of the data because they are closely related to the size of the proof. Proof generation is linearly proportional to the size of the data.